// Name : Matthew Reeves
// This is a program to identify sexy primes

import java.util.Scanner;

public class mdreeves_Sieve
{
	public static int upper;
	public static int lower;
	public static boolean[] primes=new boolean [50001];

	public static void main ( String args[] )
	{
		initializeSieve();
		processSieve();
		getBoundaries();
		showPrimes();
	}
	
	public static void initializeSieve()
	{
		primes[0]=false;
		primes[1]=false;
		
		for(int x=2;x<50001;x++)
		{
			primes[x]=true;
		}
	}

	public static void processSieve()
	{
		for (int x=2;x<=Math.sqrt(50000);x++)
		{
			if (primes[x]==true)
			{
				for (int y=2;y<50001;y++)
				{
					if (y%x==0 && y!=x)
					{
						primes[y]=false;
					}
				}
			}
		}
	}

	public static void getBoundaries()
	{
		System.out.println("Please enter a lower boundary and an upper boundary and I will print all of the sexy prime pairs between those boundaries.");
	
		Scanner input = new Scanner (System.in);

		do
		{
			do
			{
				System.out.print("Please enter the lower boundary (between 1 and 50000): ");
				lower=input.nextInt();
			} while (lower<=0 || lower>50000);
			
			do
			{
				System.out.print("Please enter the upper boundary (between 1 and 50000): ");
				upper=input.nextInt();
			} while (upper<=0 || upper>50000);
		
			if (upper<lower)
			{
				System.out.println("Your upper boundary cannot be smaller than your lower boundary. Please try again.");		
			}
		} while (upper<lower);	
	}
	
	public static void showPrimes()
	{
		int count=0;

		System.out.printf("Here are all of the sexy prime pairs in the range %d to %d, one pair per line: \n", lower, upper);		

		for (int x=lower; x<=upper-6; x++)
		{
			if (primes[x]==true && primes[x+6]==true)
			{
				System.out.printf("%d and %d\n", x, x+6);
				count++;
			}
		}
		
		System.out.printf("There were %d sexy prime pairs displayed between %d and %d.\n", count, lower, upper);
	}
}