Re: finding primes
- From: websnarf@xxxxxxxxx
- Date: 27 Oct 2006 18:30:37 -0700
dcorbit@xxxxxxxxx wrote:
Digital Puer wrote:
Got this on an interview question: given two integers A and B,
find all primes between them.
I basically wrote an initial function, bool isPrime(int i), which
loops over all numbers between 2 and sqrt(i) to see if i%num == 0,
in which case the number is not a prime. With this function I loop
between A and B, calling isPrime() on each value.
Is there a better way to do this? I looked at the Sieve of
Eratosthenes,
which didn't seem to be much better.
None of the methods listed here in this thread is the right method.
If the numbers are small (e.g. 33002 and 40000) then any method that
works will be good enough (they will finish in an eyeblink). If the
numbers are large (e.g. 4611686018427387904 and 4611686018427389999)
then none of the methods listed in this thread will work unless you
have a lot of patience. And if the numbers are even larger (e.g.
1418571425390253304739712446169831673 and
1418571425390253304739712446169839997) then the methods listed have no
hope of solution. Typically, where these questions are of importance
is where the numbers are stupendously large (IOW one hundred digits or
more).
The best real answer would be to use a hybrid technique with brute
force (all the mentioned solutions in this thread are brute force) for
small problems and more efficient methods for large numbers.
For bigger numbers, I would do something like this:
for (test_number = smallest_value; test_number <= largest_value;
test_number++)
{
bool maybe_prime = miller_rabin_pseudo_prime_test(test_number);
if (maybe_prime) {
bool is_prime = APR_CL_TEST(test_number);
if (is_prime) display_number(test_number);
}
}
Well you can do better by doing a hybrid of sieve of eratostenese and
the above algorithm. In fact I would do it as follows:
int table[large_value+1-small_value];
int i
if (large_number < firstprimes[NSMALLPRIMES-1]) goto
simplerAlgorithm;
/* Initialize partial sieve */
for (j=small_value; j < large_value; j++) table[j-small_value] = 1;
for (i=0; i < NSMALLPRIMES; i++) {
remainder = ((-small_value-1) % firstprimes[i]) +
firstprimes[i]+1;
for (j=small_value + remainder; j < large_value; j +=
firstprimes[i])
table[j-small_value] = 0;
}
for (test_number = small_value; test_number <= large_value;
test_number++) {
/* Eliminate something like 97% of the numbers */
if (0 == table[test_number-small_value]) continue;
/* Skip the first primes in the division tests, and rather than
picking completely random base primes, just go a ahead and
pick from the firstprimes table */
if (performance_optimized_strong_pseudoprime_test
(test_number)) {
/* This should bring you to 99.9999% or better */
if (APR_CL_TEST(test_number)) display_number(test_number);
}
}
The point being that you want to use the sieving to avoid the division
cost from the prescreening with division tests. Then rather than
paying the full cost of the Miller-Rabin test (which requires *random*
primes be chosen for the bases, and that you perform many many test to
bring your reliability up to a very good level) you can start breaking
the assumptions and go for things that will have bottom-line
micro-optimization performance. In this way you are only paying the
high cost of running the real primality test for numbers which are
already almost certainly prime. For the vast majority of numbers you
are just paying sieve costs, but this overhead is basically nothing, so
the remaining majority cost will likely be found in the pseudoprime
screening test. The problem is that the full miller-rabin test is a
little onerous and "essentially redundant" with the ACLR test. So
instead we can relax it down to any old cheesy strong pseudo-prime
test, with some tiny prime number bases that might not even be all that
randomly chosen. This can reduce the correctness all the way down to,
say, 99.9999%, which only increases the number of times you call ACLR
by 0.0001% or so, while potentially radically improving the performance
of the pseudo-prime test.
Obviously for memory reasons, if the range of small_number ...
large_number is too large (leading to too large of a sieve table), then
you would break this down into a sequence of calls to sequential
ranges.
--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
.
- References:
- finding primes
- From: Digital Puer
- Re: finding primes
- From: dcorbit
- finding primes
- Prev by Date: Re: Depth First Search in Binary Search Tree?
- Next by Date: Re: Unit Testing in C++
- Previous by thread: Re: finding primes
- Next by thread: Unit Testing in C++
- Index(es):
Relevant Pages
|
