There are many different algorithms to generate prime numbers and they're really interesting.
Check out this page for a whole lot of them: http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm
This one is a short simple algorithm which is not so efficient but still useful for general purposes(generates 10 million primes in a little more than 6 seconds on an AMD Dual core 2.6 Ghz)
First some information which will be useful to understand the algorithm:
1. Factors of a number "converge" to the square root of the number
e.g Let's say we have the number 1024:
The factors of 1024 are:
32*32=1024
16*64=1024
8*128=1024
4*256=1024
2*512=1024
1*1024=1024
As you'll notice as you go from bottom to the top, the factors converge towards the square root of 1024, i.e 32.
The point here that if we need to check if 1024 is a prime number, 1024 should not be divisible by any number from 1 up to 32 (sqrt(1024)). For example if we see that 1024 is divisible by 8 (1024=8*128), in order to save calculations we don't need to check that 1024 is divisible by 128.
2. Every number can be broken down into prime factors
e.g 345=3*5*23 (3,5,23 are all prime numbers)
This 2nd idea is more interesting. Since a number can be broken down into prime factors(which are smaller than the number itself), then if a number is a prime number, it should not be divisible by any prime number smaller than itself.
This means that to determine if a number is prime, we just compare it with a list of primes smaller than itself and see if it is divisible by any one of them. If it's not then it's prime.
These 2 ideas can be combined together to form the following idea:
If a number is prime, it should not be divisible by prime numbers starting from 2 up to the square root of the number.
For example to determine if 23 is prime:
sqrt(23)=4.796
Prime numbers before 4.796= 2,3
Is 23 divisible by 2? no
Is 23 divisible by 3? no
So 23, is prime and it's added to the primes list.
Here's some C code which illustrates the above concept.
//sniper11
#include <stdlib.h>#include <stdio.h>
#include <math.h>
#define PMAX 20000000 /*max number of primes to generate*/
int n;
int c=0;
unsigned int primes[PMAX]; int primeptr=0;
int add_prime(int i)
{
primes[primeptr]=i;
primeptr++;c++;
}
int gen_primes()
{
int i,j,prime;
add_prime(2);//add 2 to the list
for(i=3;i<=n;i+=2)//skip even numbers
{
prime=1;
int maxfactor=sqrt(i);
for(j=1;j<primeptr;j++){
if(primes[j]>maxfactor)
break;
if(i%primes[j]==0){
prime=0;
break;
}
}
if(prime==1){
add_prime(i);
}
}
}
int output_primes()
{
int i;
for(i=0;i<primeptr;i++)
{
printf("%d\n",primes[i]);
}
}
int main()
{
printf("Number of primes to generate: ");
scanf("%d",&n);
gen_primes();
printf("Count: %d\n",c);
output_primes();
}
