OVERVIEW OF PRIME NUMBERS In mathematics, a prime number (or a prime) is a natur

Question

OVERVIEW OF PRIME NUMBERS

In mathematics, a prime number (or a prime) is a natural number greater than one whose only positive divisors are one and itself.

A natural number that is greater than one and is not a prime is called a composite number. The numbers zero and one are neither

prime nor composite. The property of being a prime is called primality. Since 2 is the only even prime number, the term odd prime

refers to all prime numbers greater than 2. -- Definition taken from http://en.wikipedia.org/wiki/Prime_number.

In mathematics, a sexy prime is a pair (p, p + 6) of prime numbers that differ by six. The name "sexy prime" stems from the Latin

word for six: sex. -- Definition taken from http://en.wikipedia.org/wiki/Sexy_prime.

Some examples of sexy prime pairs are 5 and 11, 7 and 13, and 461 and 467.

For this program, you are first going to calculate the prime numbers between 1 and 50000 using an algorithm known as the Sieve of

Eratosthenes and then display the sexy prime pairs within a range specified by the user.

TEMPLATE TO START YOUR PROGRAM: NetID_Sieve.java

To get you started for this assignment, you will be given a main() method. You will need to type this in as you see it here, without

modifications other than to put in your on NetID and leave out the comments if you don

OVERVIEW OF PRIME NUMBERS

Explanation / Answer

import java.util.Scanner;

public class NetID_Sieve
{
public static void main ( String args[] ) {
final int HOWMANY = 50000;
boolean[] sieve = new boolean[HOWMANY+1];
int lower = 1, upper = HOWMANY;
// The range of numbers
// Boolean array of true/false
// Setting initial boundaries
// the following method call will implement the Sieve algorithm
processSieve( sieve );
// the following method call will print all 1419 sexy pairs of primes
showPrimes( sieve, lower, upper );
// the following method call gets the lower boundary for printing
lower = getLower( HOWMANY );
       // the following method call gets the upper boundary for printing
       upper = getUpper( lower, HOWMANY );
       // the following method call prints sexy pairs in the new lower-upper range
       showPrimes( sieve, lower, upper );
}
  
// implement method processSieve here
  
static void processSieve(boolean [] sieve)
{
   int N = 50000;
  
for (int i = 2; i <= N; i++) {
   sieve[i] = true;
}

for (int i = 2; i*i <= N; i++) {

if (sieve[i]) {
for (int j = i; i*j <= N; j++) {
   sieve[i*j] = false;
}
}
}

}
// implement method showPrimes here
static void showPrimes(boolean[] sieve, int lower, int upper)
{
  
      
   System.out.println("Here are all of the sexy prime pairs in the range "+lower+" to "+upper+", one pair per line:");
   int prime = 0;
  
   for(int i=lower; i<upper-6; i++)
   {
       if(sieve[i] && sieve[i+6])
       {
           ++prime;
           System.out.println(i+" and "+(i+6));
       }
   }
  
   System.out.println("There were "+prime+" sexy prime pairs displayed.");
}
  
// implement method getLower here
  
static int getLower(int n)
{
   Scanner in = new Scanner(System.in);
   int lower=1;
  
   while(true)
   {
       System.out.print("Please enter the lower boundary (between 1 and "+n+"):");
       lower = in.nextInt();
      
       if(lower >= 1 && lower <= n)
           break;
   }
  
   return lower;
}
  
// implement method getLower here
static int getUpper( int lower, int n )
{
   Scanner in = new Scanner(System.in);
   int upper=n;
  
   while(true)
   {
       System.out.print("Please enter the upper boundary (between "+lower+" and "+n+"):");
       upper = in.nextInt();
      
       if(upper > lower && upper <= n)
           break;
   }
  
   return upper;
}
}
  
  

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.