Sunday, December 25, 2011

Efficient Algo to generate Prime numbers

After doing some little research for a prime number generation in Project euler. Just come to the conclusion that the below algorithm is the Most efficient algo for generating prime numbers.

Considerations:
1.Except 2 and 3 , all primes can be represent in the form of 6n+1 or 6n-1. [This leads to the conclusion that all primes are odd and it is not divided by  3.
2.And if a number is not divided by all the numbers below sqrt(number) then its a prime.
So it leads to the following pseudo code..

// Generating prime after 2 and 3
1.Read n
2.Divide it by the all odd numbers(above 3) less than sqrt(n).


P.s: Its 3 times faster than the usual code.If you know an efficient code other than this . Do comment that algo.

No comments:

Post a Comment