| You want primes that will fit in a 32 bit unsigned integer?
For this, a simple program that does trial division by primes
less le sqrt(n) will suffice.
In fact, I'm sure I have one laying around, as do other folks.
For larger primes (say, 64 bits) there are better primality programs
that others have.
Note there are no "functions" that generate general primes, but there
are some efficient ways to test numbers for primality, as well as
ways to test a number for possibile primality with a very small
probability of failure (by repeated testing this probability can
be made arbitrarily small.)
- Jim
|
| Things like Mersenne Numbers dont make good prime generators. Although
they are good at finding primes they choose a very sparse subset of
them !
The easy way to provide a function that returns primes is to generate a
list of all primes up to the square root of the max value you want.
Then generate a random integer in the range you are interested in and
test whether it is prime or not.
The following program illustrates the idea (but is not guaranteed to be
correct !)
Andrew
#include <stdio.h>
#include <ctype.h>
#include <fcntl.h>
#include <locale.h>
int main (argc, argv)
int argc;
char *argv[];
{
int primes[10000];
int nprimes=0;
unsigned int i,j;
/* first generate the table of known primes */
for(i = 3 ; i < 100000 ; i += 2)
{
for (j = 0 ; j < nprimes ; j++)
{
if ( i % primes[j] == 0)
goto non_prime;
}
primes[nprimes++] = i ;
non_prime:;
}
/* now find some random primes */
while (1)
{
/* Note that this probably doesn't generate numbers in the required range */
i = rand()*2 +1;
if (i >= 1000000 && i < 4000000000)
{
for (j = 0 ; primes[j] * primes[j] < i ; j++)
{
if (i % primes[j] == 0)
goto non_prime2;
}
printf("%u\n",i);
}
non_prime2:;
}
}
|
| Probably the best way to go is as has been suggested, generate and
test for primality by repeated divisions.
You can speed things up by generating random numbers in one 30th the
range (30 equals the product of the first three primes) and then
multiply by 30. Add 1 to the first number you generate, 7 to the
second, 11 to the third, and so on through 13, 17, 19, 23 and 29
(non-composites less than 30 excluding the factors of 30). Repeat
the series.
7/10 of the numbers you would generate in a more conventional way would
be divisible by 2, 3 or 5 and would be rejected. This will prevent
generating those numbers, which should speed things up a bit (not as
much as you might wish, though, since it these are the numbers which
are eliminated by the first three test divides).
This will not add any bias to the numbers chosen (which is important in
some applications, for example, if the primes are being used in
selecting a key for a cryptographic application). If such a bias is
not important you can add the same value (e.g., 1) to all the numbers
generated. In that case all the primes you generate will be equal
to each other modulo 2, 3 and 5.
Topher
|