Think you could write a program that checks the outcome of at most 500 divisions in less than a second?

JavaFan,
And after testing 2, you can exclude all the other even numbers. Which leaves with at most 500 numbers to check.

After testing 3 and 5, you can use the 2/4 trick (see Re^3: a close prime number) to skip all multiples of 3 leaving you with about 333 numbers to check. I agree that for a single number under 1 million a pure perl function can be created that does the job without resorting to anything more advanced. I have yet to find a simple (by my own subjective definition) method though that does better than testing 1/3 sqrt (N) numbers to determine if a number is prime. I guess it could be argued that using Math::Pari's primality test function is simple but I meant my own implementation.

Cheers - L~R

For Project Euler problems I already needed an iterator that iterates over primes. (Under the hood it uses the sieve of Eratosthenes to calculate blocks of primes and then returns them.)

If you already have that iterator, dividing by the primes up to and including the square root is quite easy.

Well, you could create a simple sieve that finds all primes between less than 500 (or just use brute force - square root of 500 is less than 23, and you'll know the primes up to 23 I presume), and use them.

But that sounds like too much work to me. It's only worthwhile to use really efficient prime searching algorithms if the numbers involved are much bigger than what a Perl integer can hold.

In it I had 2 prime testing algorithms. The first, is_prime, generates all of the primes up to a given one then does a binary search. On my laptop it generates all of the primes up to a million in under half a second, and after that I can do about 70,0000 primality tests/second on numbers 1..1_000_000. The other one, is_prime2, generates the primes up to the square root of a given one and does trial division. It is avoids the up front load but can only do about 25,000 primality tests per second on numbers 1..1,000,000. My laptop may be faster or slower than your computer, but either should be more than fast enough for your purposes.

I use integer so neither primality test will work past 2 billion. If you want to test primality for larger numbers, I highly recommend Math::Pari which pushes it down to a highly optimized C library. I sometimes find it amusing to watch it factor random 100 digit numbers in the blink of an eye.

Anyways here is my Perl library. Be warned it has a lot of irrelevant stuff in it and was only meant for personal use. (Hence no documentation.) However it has a lot of goodies for anyone trying to do project Euler problems.

There was a Perl Monks node a while back that discussed several different methods of calculating large numbers of primes. The one that seemed to be most efficient (based on my own trials) was an implementation of the Sieve of Eratosthenes using vec attributed to merlyn. See Re: To Findout Prime number.

Best, beth

That's a rather inefficent sieve. Inefficient in the sense that it wastes a lot of memory - it uses a single bit for every number, including all the even ones. That's half the memory usage for numbers you know cannot be prime. I've done sieves based on vec as well, and I've found that the limit on how far you can feasibly go is the memory consumption. Note that any prime number (except the first few) are of the form 30 * n + k with k one of 1, 7, 11, 13, 17, 19, 23, 29. (All other numbers are either divisible by 2, 3 or 5). Which means you need only 8 bits for every 30 numbers. Of course, more efficient packings exist as well.

That was also my first reaction, but merlyn's algorithm is lightening fast. As is often the case, one trades speed for memory. On modern computers the amount of memory needed to find primes between 1 and 1 million is rarely an issue. The OP is satisfied with the primes < 1 million. If you are looking for very, very large primes (10's of digits) I'm sure other slower algorithms might be better.

Best, beth

I agree with the other monks who have suggested the Sieve of Eratosthenes. It is The Way to find all prime numbers between 1 and some upper limit.

For another discussion of prime finding, see ulam's spiral too slow

Don't calculate when you can lookup! This will test almost a million numbers per second:

c:\test>perl Math\Primes\First_1e6.pm
Found 122571 primes from 1000000 tries in 1.145 seconds (873362/s)
[download]