Although to write a code for a basic Prime number generator is considered a trivial task, but still ignoring little properties of prime numbers can result in a slow program, especially when dealing with large numbers. In this post I am not going to tell you about any new extra ordinary super complex algorithm to boost up your program, instead I am just going to remind you about some basic properties of prime numbers which many of you would already be knowing, but still don't take their advantage while programming. Although these properties are basic, but with their use one can attain a significant performance improvement in their prime number generator program.
In the most basic approach to write a Prime number generator code, one generally makes use of the necessary and sufficient condition for a number to be prime. As prime number has only two factors, first is '1' and other is the number itself, so in this kind of approach the program checks for a number (let call this number be N) to be prime by checking for the availability its factors, i.e. for every N the program iterates from 2 to (N-1) and checks if the N is divisible by any of the iterator values (or we can say it checks whether any iterator value is a factor of N). Thus if the program fails to find any factor of N (between 2 and N-1), the number N is declared prime.
Optimization 1: The first optimization at this stage can be applied, when we find factors of N in [2, (N-1)] (In above mentioned approach). Instead of searching for factors of N in whole range of [2, N-1], the program should only check for the potential factors in the prime numbers generated previously, i.e. while searching for the factors of N, the program should iterate in the list of previously generated prime numbers only. This approach can be considered as doing prime factorization of the number N, all the consonants themselves are the product of several smaller primes, so rechecking for them to be a factor is kind of redundant step for our purpose, and hence if no prime number P (P < N) is a factor of N, then the number N is a prime number.
Optimization 2: As we all know that 2 is the only even-prime number, so it help us eliminating half of the potential candidates which were going to be tested for being prime. As after 3 no even number is going to be a prime number, so to generate prime numbers up to N the checking of a number for being prime should be done skipping all the even numbers.
In the most basic approach to write a Prime number generator code, one generally makes use of the necessary and sufficient condition for a number to be prime. As prime number has only two factors, first is '1' and other is the number itself, so in this kind of approach the program checks for a number (let call this number be N) to be prime by checking for the availability its factors, i.e. for every N the program iterates from 2 to (N-1) and checks if the N is divisible by any of the iterator values (or we can say it checks whether any iterator value is a factor of N). Thus if the program fails to find any factor of N (between 2 and N-1), the number N is declared prime.
Optimization 1: The first optimization at this stage can be applied, when we find factors of N in [2, (N-1)] (In above mentioned approach). Instead of searching for factors of N in whole range of [2, N-1], the program should only check for the potential factors in the prime numbers generated previously, i.e. while searching for the factors of N, the program should iterate in the list of previously generated prime numbers only. This approach can be considered as doing prime factorization of the number N, all the consonants themselves are the product of several smaller primes, so rechecking for them to be a factor is kind of redundant step for our purpose, and hence if no prime number P (P < N) is a factor of N, then the number N is a prime number.
Optimization 2: As we all know that 2 is the only even-prime number, so it help us eliminating half of the potential candidates which were going to be tested for being prime. As after 3 no even number is going to be a prime number, so to generate prime numbers up to N the checking of a number for being prime should be done skipping all the even numbers.
Optimization 3: The further improvement can be to reduce the list of smaller prime numbers to be used for testing N as a prime (as stated above in Optimization 1). The program should use only the prime numbers smaller or equal to the square-root of N, while checking N to be a prime number. This technique would be effective since primes larger than the square root of N will be complementary factors of at least one prime less than the square root of N, by this I am trying to say, consider N = p.q and q >= square-root(N), then p should be less then equal to square root of N (i.e. p <= square root(N)).
Optimization 4: The next optimization which I am going to mention seems small, but can still save a significant computation in long run. As we have applied the optimization 2 (mentioned above), we are not going to check any even number further , so when we check for their factors from the list of previously generated prime numbers, no further value of N is going to have '2' as their factor, so we can avoid checking for '2' as their factor.
No comments:
Post a Comment