Use the Sieve Method to Identify primes by a process of elimination. For odd int

Question

Use the Sieve Method to Identify primes by a process of elimination. For odd integers (3 < N <1,000,000) progressively cross-out (or label) numbers that are not prime by virtue of being divisible by 3, then 5, then 7 and so on for all possible prime factors less than SQRT(N). No need to slow down to see if a number was already marked. Just mark again. Finally sort out the remaining unmarked (prime) numbers with no prime factors. Note: To sieve primes less than 1,000,000 this method requires a list of primes up to SQRT(1000000) = 1000. Use any method to obtain this starting list, but I suggest that you create the list using the sieve method up to 1000 starting with the known primes up to 31. If the logic works for primes up to 1000, the same logic should work for large N. For example for the range from 1000 < N < 1000000. Divisible by 3: mark 1005, 1011, 1017,...., 999993, 999999 as not prime Divisible by 5: mark 1005, 1015, 1025, ...., 999985, 999995 as not prime etc, etc Divisible by 313: mark 97969, 98595, 99221, 99847 ... as not prime etc. Note: The first prime number is 2, the second prime number is 3, etc.

Explanation / Answer

/* This is a complete program
showing steps of seive to compute primes upto N=1000000.
The program takes a input as positive integer x
and output whether it is prime or not.

Language used :C++
*/
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int main()
{
   // declare an array upto N
   bool isprime[1010000];
  
   //set all the elements in array as true
   memset(isprime,true,sizeof(isprime));
  
   // number 0 and 1 are not prime
   // hence they are done false
   isprime[0]=false;
   isprime[1]=false;
  
  
   int N = 1000000;
  
   // loop from 2 to sqrt(N) , here N=1000000;
   //check if isprime[i]==true, then cancel all its multiples
  
   for(int i=2;i<sqrt(N);i++)
   {
       if(isprime[i]==true)
       {
      
           for(int j=i*i; j<1000001;j+=i)
               isprime[j]=false;
       }
   }
  
  
   // to identify that a number is prime or not
   // check the corresponding value of isprime
   // isprime[x] = true , then x is prime
   int x;
   cin>>x;
   if (isprime[x]==true) cout<<"PRIME"<<endl;
   else cout<<"NOT PRIME"<<endl;

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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