06-09-2003, 05:45 AM
Oracle:
This is a different problem than finding all primes up to a number.
AFAIK, to check if a number is prime you must check if it's divisible by some prime from 2 to the suare root of the number.
It means if your number is 2^62 you must have all the primes from 2 to 2^31 in a table. There are aproximately 100 million primes in that range. You coud calculate them previously and save them in a table. Rich Geldreich's progam generates in 1 hour such a table and stores it in a compressed format, 1 byte per prime but be aware the table is 100 Meg in size...
A less bloated approach would be to divide by every number from 2 to square root of n, it would work but it would be very inefficient.
This is a different problem than finding all primes up to a number.
AFAIK, to check if a number is prime you must check if it's divisible by some prime from 2 to the suare root of the number.
It means if your number is 2^62 you must have all the primes from 2 to 2^31 in a table. There are aproximately 100 million primes in that range. You coud calculate them previously and save them in a table. Rich Geldreich's progam generates in 1 hour such a table and stores it in a compressed format, 1 byte per prime but be aware the table is 100 Meg in size...
A less bloated approach would be to divide by every number from 2 to square root of n, it would work but it would be very inefficient.
Antoni