Prime Sieve A prime number is an integer greater than 1 that has no positive div

Question

Prime Sieve A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself. For example, 3 is a prime since 1 and 3 are its only positive divisors. However, 6 is not prime since it is divisible by 2 (i.e. 6 2x3). Here are the list of prime numbers that are less than or equal to 20. 2 3 57 11 13 17 19 Given a positive number n, your task is to create a program named countPrimes.java that counts the number of prime numbers less than or equal to n (inclusive) Sieve of Eratosthenes A brute force technique to test if a number p is prime is to loop through all numbers less than p and test if any of them divides p. To count the number of primes less than or equal to n, we can use this naive approach to test all numbers between 2 and n inclusive. Of course, this would work, but it will take a long time to test large numbers like n >100o000. Below is a faster technique that is known as the Sieve of Eratosthenes. Given a positive number n, you can check that it will return the correct list of all prime numbers between 2 and n inclusive. Your task is to code the Sieve of Eratosthenes and use it to count the prime numbers between 2 and n inclusive. Maintain a boolean array to record which integers are prine . Repeat for 1-2 to VN o if i is not still marked as prine is is not prine since we previously found a factor o if is narked as prime is prine since it has no snaller factors mark all nultiples of to be non-prime (e: 2,3, 4

Explanation / Answer

/*
* The java program that prompts user to enter n value
* then find the number of prime numbers between 2 and n inclisive
* Then find the prime numbers and then print the number of prime
* numbers on console.
* */
//CountPrimes.java
import java.util.Scanner;
public class CountPrimes
{
   public static void main(String[] args)
   {
       /*Declare two integer variables*/
       int n;
       int numPrimes=0;
       /*Create an instance of Scanner class*/
       Scanner scanner=new Scanner(System.in);
       System.out.println("Enter n-value :");
       n=Integer.parseInt(scanner.nextLine());
      
       //Create a boolean array of size,n
       /**Set size to n+1 since we are starting to count from 1, raise
       * the size to n+1*/
       boolean prime[] = new boolean[n+1];
       //Assume all numbers are prime, so set boolean value ,true
       for(int i=0;i<n;i++)
           prime[i] = true;
      
       /*Run for loop from starting p=2
       * to until the square root of p value*/
       for(int p = 2;p<=Math.sqrt(n); p++)
       {
           // If prime[p] is not changed, then it is a prime
           if(prime[p] == true)
           {
               /*Set to false all the multiples of p to false
               * For 2, set all multiples of 2 are false
               * For 3, set all multiples of 3 are false
               * and so on
               * so that the all the value which have multiples are set to false from the
               * prime boolean array*/
               for(int i = p*2; i <= n; i =i+ p)
                   prime[i] = false;
           }
       }
       // Print all prime numbers
       for(int i = 2; i <= n; i++)
       {
           if(prime[i] == true)
           {
               System.out.printf("%-3d",i);
               numPrimes++;
           }
       }
       System.out.println(" Number of primes between 1 to "+n+" = "+numPrimes);
   }
}//end of the class,CountPrimes.java

Sample Output:

Enter n-value :
20
2 3 5 7 11 13 17 19
Number of primes between 1 to 20 = 8

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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