Primes: Primality Testing,Generating Primes ( Sieve of Eratosthenes)

Prime Numbers:
All numbers greater than 1 and having only two divisors (1 and the number itself) is called prime numbers.
Such that 2,3,5 are prime. 4,8,10 are not.

Primality Testing:

In this section we will discuss how to check whether a number is prime or not.

We can iterate from 2 to n-1 and checks if the number can be divided by any of these numbers.But these approach has a complexity of O(n).
We can notice that for every number it is impossible to have a divisor greater than n/2 besides the number itself. So it is enough to iterate over 2 to n/2. But though the complexity does not improve a much.

So we will discuss about a property that will allow us to reduce the complexity upto square root of n,Using the knowledge from discrete math- " if a number is not prime then there exists at least one prime divisor of that number which is less than square root of n."

So using this property we only need to iterate over 2 to sqrt(n). Thus our approach is reduced to the complexity of O(sqrt(n)).

Code:
bool isPrime(int n)
{
int f=1;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
f=0;
break;
}
}
return f;
}

Here I use i*i<=n which is an alternate to i<= sqrt(n).
But sqrt(n) function has a complexity of O(sqrt(n)),
So i will suggest not to use the function in loop, 
which will unnecessarily increase the run time
of the code. Besides there can also be a floating
point precision error if written like that. So better 
way to compute the square root of n in a variable before 
and then use that variable or simply use the above method
I used in the code.

Generating Prime:

Ok for Generating primes, a very good article was
written by Jane Alam Jan in Lightoj. The article is so enriched,
I found no need of writing
anything else :) .

Code I Used:

#define M 1000000 bool marked[M]; vector <int> primes; void sieve(int n) { primes.push_back(2); for (int i = 3; i * i <= n; i += 2) { if (marked[i] == 0) { primes.push_back(i); for (int j = i * i; j <= n; j += i + i) { marked[j] = 1; } } } }

Complexity:

The algorithm has run time complexity of O(Nlog(logN))