The task is to find all the primes between 1 to N.Numbers are called prime if they do not have any factors other than 1 and the number itself.
Brute Force-
Each number from 1 to N is checked if it is prime or not.
To check if a number is prime or not,check its divisibility by each number less than or equal to N.
[cpp]
int IsPrime(int N) {
int i;
for (i=2; i<N; i++)
{
if (N % i == 0)
return 0; //N is divisible by i.
}
return 1; //not divisible by any of the numbers (2,3….N-1) and thus prime.
}
for(i=1;i<=N;i++)
{
if(IsPrime(i))
printf("%d\n",i); // prints the number if it is a prime.
}
[/cpp]
Optimized Code-
To check if a number is prime or not,check its divisibility by
each number less than or equal to sqrt(N).
[cpp]
int IsPrime(int number) {
int i;
for (i=2; i*i<=number; i++) //less number of iterations compared to above code.
{
if (number % i == 0)
return 0;
}
return 1;
}
for(i=1;i<=N;i++)
{
if(IsPrime(i))
printf("%d\n",i); // prints the number if it is a prime.
}
[/cpp]
Sieve of Eratosthenes-
Above methods are inefficient for large values of N,since we would be repeating the same calculations.
In this situation it is best to use a method known as the Sieve of Eratosthenes.
The Sieve of Eratosthenes will generate all the primes from 2 to a given number n.It begins by assuming that all numbers are prime. It then takes the first prime number and removes all of its multiples. It then applies the same method to the next prime number.This process is continued till sqrt(n).
Illustration-
Initially,the list is
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2 is the first prime and all its multiples are removed from the list.
So,the new list is
2 3 5 7 9 11 13 15 17 19
3 is the first prime and all its multiples are removed from the list.
So,the list is
2 3 5 7 11 13 17 19
Thus,we get all the primes between 1 to 20.
Code-
[cpp]
//prime[i]=1 if i is prime and
// prime[i]=0 if i is not prime.
prime[0]=0;
prime[1]=1;
m=sqrt(N);
for (int i=2; i<=m; i++)
{
if (prime[i])
{
for (int k=i*i; k<=N; k+=i)
{
prime[k]=false;
}
}
}
[/cpp]
