Re: Prime Numbers

On May 22, 8:22 am, rossum <rossu...@xxxxxxxxxxxx> wrote:
On Thu, 22 May 2008 14:05:42 GMT, Wojtek <nowh...@xxxxx> wrote:
Arne Vajhøj wrote :
Wojtek wrote:
j1mb0jay wrote :
I am now trying to improve upon the way in which i calculate if a number
is prime.

I once did this as a C example, though I would use different constructs in
Java

Upon initialization calculate each prime and store it in a HashMap.

When testing for a prime, see if it is in the HashMap.

HashMap is array backed.

You can not store all the primes within the range of long
in a HashMap.

Arne

There are more than 2^31-1 primes within 2^63-1?

The incidence of primes drops as the numbers get larger. Without
actually running a test, I think that there cannot be more then
Integer.MAX_VALUE primes within a Long.MAX_VALUE space.

According to Wikipedia:

(http://en.wikipedia.org/wiki/Prime_counting_function)

There are 234,057,667,276,344,607 prime numbers less than 10^19, which
is about the same size as Long.MAX_VALUE. That is a lot larger than
Integer.MAX_VALUE.

rossum

Check prime number in wikipedia, it will point you to some primality
tests, but the AKA test discovered in 2002 was a surprising
breakthrough as I recall so don't expect to find a deterministic test
that is faster unless you are willing to hold a seive with all
relevant primes in memory.

Primes are surprisingly dense. If you pick an n digit number at random
the odds that it is prime are of the order 1/n. Actually this fact is
very important for cryptography as it means you can pick 100 digit
numbers at random and after testing something on the scale of 100 of
them you can expect to find a prime.

.