[Math] Best method to calculate an unknown prime

prime numbers

I'm struggling with primes…
I want to create a calculation program which need to check a number to be prime.
No problem so far!

The problem starts when this number exceeds 48 million.
The way my programming will start calculating primes is as following:

  1. Skip 0 and 1.
  2. Print 2, as it is the only even prime number
  3. Start counting from 3 and skip all even numbers.

So far I used this method:

  1. Get the root of the number to check
  2. Get the remainder of the number when diving by all odd numbers till the root has been reached.

As you can guess this is pretty slow…

The reason I do not use sieves is because they are limited! I bet no one can calculate a number higher then 250 trillion to be prime with the sieve of eratosthenes. No computer can create a list counting till that number and start strikethrough numbers…

There is one choice I still have to make… Am I going to store the primes or not.
If I do I can use them to quicken the calculation process, but it will reach it limit after a few million numbers…

I was thinking of using the sieve of eratosthenes till 20 million has been reached and then jump over to another method.

The main goal is to be able to calculate primes starting at any given number till eternity.

I founded out myself that I won't be able to use the following methods for my main goal:

  • Sieve of eratosthenes (only partially)
  • Sieve of Atkin (only partially)
  • Miller-Rabin
  • Mersenneprime with Lucas-Lehmertest

Please correct me if I'm wrong! And tell me then why I can use these methods.

So my question is:
How to calculate an unknown prime (since it has no limit).

Thanks in advance,
Mixxiphoid

UPDATE
I will check out the combination of Miller-Rabin with AKS.

Best Answer

I bet no one can calculate a number higher then 250 trillion to be prime with the sieve of eratosthenes

That is just false. Are you going all the way to $n$ instead of $\sqrt{n}$ when looking for factors?

The first time I ever used java, (which usually isn't noted for its computational prowess) for fun I wrote a silly program that would factor a number $n$ by checking all the odd numbers up to $\sqrt{n}$. (This is my version of "Hello World!")

This is strictly worse then the eratosthenes sieve, and took longest for prime numbers, but it was able to detect primality for numbers up to $9\times 10^{19}$ in less than a second. The only reason it couldn't check larger numbers was because java's "long" only goes up to $9\times 10^{19}.$

So if this trivial program on a old computer using java can check numbers that are $12$ orders of magnitude larger than yours, and $5$ orders of magnitude larger than your theoretical upper bound, there must be a problem with how you are implementing these methods.

Fun note: I never have forgotten that from this program, the number $1234567898765432111$ is prime.

Related Question