That might require a very large table. There are 203 million primes
less than 2^32. Because a hash function is usually established once
and then used many times, computing a whole table of primes is not
necessary. Finding the one next prime can be done faster using trial
division, because the overhead in setting up a sieve is actually more
work than just finding the one next prime with trial division, if the
numbers are not huge.
The function below will find the next prime for numbers less than 100
million in about half the time it takes to use a sieve. Again, trial
division is not the best way to find a stream of many prime numbers,
but it is just fine for finding one.
Don
int nextPrime(int n)
{
++n;
if (n % 2 == 0) ++n;
if (n % 3 == 0) n += 2;
int step = "XEC"[n%3] - 'A';
while(1)
{
for (int i = 5; i*i <= n; i += 6)
{
if (n%i == 0) break;
if (n%(i+2) == 0) break;
}
if (i*i > n) return n;
n += step;
step ^= 6;
}
}
On Aug 27, 3:59 am, saurabh modi <saurabhmodi102...@gmail.com> wrote:
> use sieve.then make a list of primes.
>
> A binary search can work well to find the next greater prime number.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
