Re: Find prime number between 1 to 1000000

A number is prime if it doesn't have any divisors other than 1 and itself. Note that if such a divisor exists, one exists which is at most the square of the number. Given that N is less than 1000000, you only have to check less than 1000 numbers. And after testing 2, you can exclude all the other even numbers. Which leaves with at most 500 numbers to check.

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

Comment on Re: Find prime number between 1 to 1000000

Replies are listed 'Best First'.
Re^2: Find prime number between 1 to 1000000 by Limbic~Region (Chancellor) on Jul 29, 2009 at 14:58 UTC
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	[reply]
Re^3: Find prime number between 1 to 1000000 by tilly (Archbishop) on Jan 24, 2011 at 05:19 UTC
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.	[reply]
Re^3: Find prime number between 1 to 1000000 by JavaFan (Canon) on Jul 29, 2009 at 15:10 UTC
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.	[reply]