3
$\begingroup$

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.

  • 1
    [This](http://math.stackexchange.com/questions/29747) and [this](http://math.stackexchange.com/questions/15134) are relevant to your needs I think.2011-04-28
  • 0
    @J.M. your hint pointed be to the AKS method. I'll check it out.2011-04-28
  • 1
    I don't remember AKS being practical already. Granted, it's been a while since I last looked into it...2011-04-28
  • 1
    If you are checking an arbitrary number for primality, why are you printing 2? It sounds like you are creating a list of primes. These two problems have different solutions. In particular the Lucas-Lehmer test only applies to finding Mersenne primes, which is why the largest known primes are all found by GIMP and are all Mersenne primes! Many non-mersenne primes are not accounted for between the largest primes and those found by more alternative methods.2011-04-28
  • 0
    @Joshua Shane Liberman: You're right indeed. I do not need the two :). Don't know why I wrote that down.2011-04-28
  • 3
    Are your numbers really arbitrary? If the number is even half the time you test it, a quick pass is important. Otherwise, extra information can always be used to improve the process.2011-04-28

5 Answers 5

0

Instead of:
"2.Get the remainder of the number when dividing by all ODD NUMBERS till the root has been reached."

Try testing for divisibility of 2 and 3 and then numbers of the form (6n ± 1). This way you will not only skip the even numbers, you will also skip the numbers divisible by 3.

5

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.

  • 2
    1234567898765432111 is prime indeed.2011-04-28
  • 0
    About the sieves... read my comment on the answer of @mixedmath.2011-04-28
  • 2
    @Mixxiphoid: That is not my point. What I am saying is, your code must be doing something wrong because the trivial implementation can print out a list of all primes up to $100$ billion without much trouble, and check primality for numbers up to bascially $10^{20}$. _And_ all of this is in Java...2011-04-28
  • 0
    Part of my problem was the same issue with the limits of the programming language. C# and Java now know the BigInteger, which is theoretically unlimited. A problem that comes with BigInteger is that it hasn't a root function. Calculating the root of a number without a root function takes much more time... When I use a sieve it will calculate big numbers in a matter of seconds too.2011-04-28
  • 0
    @Mixxiphoid: Which are you trying to do? Be able to print a list of all the primes up to a certain point, or create a program which can efficiently check whether any (small enough) number is prime?2011-04-28
  • 0
    As stated clearly in my question, I need to check a number to be prime. The number may be an unpronounceable high number. A number like (10^16543 + 1) is to big for a sieve, so I need a different method which is 100% secure.2011-04-28
  • 0
    @Mixxiphoid: This isn't making any sense to me. Why can you only go up to 48 million? That exact implementation should go up to _at least_ $10^{20}$. Also, taking the square root is one of the cheapest and fastest things you can do, and was known to the Babylonians. See http://en.wikipedia.org/wiki/Methods_of_computing_square_roots . Also I think it would be obvious (for many reasons) that no method can work for arbitrarily large numbers, so the game is _always_ going to be "how large can we get?"2011-04-28
  • 0
    @Eric Naslund: Please read my question. I noticed you didn't read it well. I DO use the root of a number. 48 million is NOT my limit. The limit I seek does not exist (unlimited). Read the fat line, it is important.2011-04-28
  • 0
    @Mixxiphoid: Yes, but you are obviously doing something completely wrong. And this is exactly what I asked previously. The line "The main goal is to be able to calculate primes starting at any given number till eternity." implies you want a list. I ask this, and you say clearly you don't want a list. Maybe you didn't write it too well. Lastly, I would hope that it is completely clear that you cannot possibly go on forever for trivial computational reasons. (At the very least, the size of the number you want to check will be too large to store)2011-04-28
  • 2
    @Mixxiphoid: When you say "As stated clearly in my question" and then state multiple different things, then it is obviously not clear....2011-04-28
  • 0
    @Mixxiphoid: I have been interpreting this as the generation of a list. If that is wrong, then please clarify the statement 'be able to calculate primes starting at any given number till eternity.'2011-04-28
2

Did you read this http://en.wikipedia.org/wiki/Primality_test [*1] especially the chapter "Probabilistic tests" which is the most practical method. Then asking qestion about specific points from *1.

  • 0
    The chapter Probabilistic tests is using the Miller-Rabin test. the method (as I interpreted it) is not 100% to be trusted. There is a small chance the number is not prime, though the test says it is.2011-04-28
  • 0
    @Mixxiphoid: quote "so k repetitions reduce the error probability to at most 2^−k, which can be made arbitrarily small by increasing k." unquote. Do you realise wat is probability, for example, of 2^-64 ? it is approximately 2^32 times smaller than probability your computer giving nonsense results because of hardware error.2011-04-28
  • 0
    A chance is a chance right? Even a small chance can happen, or else the chance wouldn't be there. I need to be 100% sure, not 99,9...999%. And computers were still made be humans, so, they contain errors :). I appreciate your help, but I need a method which ensures me to be 100% sure.2011-04-28
  • 1
    @Mixxiphoid: Even then, you could do the so-called [AKS Algorithm][1] on any number that the Miller-Rabin says is prime after say, 10 iterations. This would lead to huge time-savings, and still allow you to be 100% sure. [1]: http://en.wikipedia.org/wiki/AKS_primality_test2011-04-28
  • 0
    Thanks for pointing out to combination of using them both! :) That might work and still saves time. Now I got to found out how to do it =/... Thanks a lot, I'll see if it work.2011-04-28
  • 2
    @mixedmath: "This would lead to huge time-savings." Not really. The primes are too dense, so at best we gain a factor of $\log x$.2011-04-28
  • 0
    @Eric: Do you not consider that huge? I'm just saying, that if we are going 'to eternity' then maybe log time savings allows us to get a little further ;p.2011-04-28
1

I am going to expand upon my previous comment and the answer of Andrei. There have been many questions on StackExchange. Recently, there was this thread which was about finding primes of a given size quickly. We also had this question, which I think directly ties into yours.

It was pretty quickly accepted that running through numbers with a couple of Miller-Rabins, and then performing the AKS algorithm on those that got through. Here, there is more information on such tests. In particular, it seems that you want to generate arbitrarily long lists of primes, and thus Miller-Rabin + AKS seems like a great start.

On the other hand, there is nothing wrong with any of the Sieves. The sieves generate lists of primes quickly, so if it's a list that you want than a sieve can be your best bet. Atkin and Sundaram are my favorites. I don't know what you mean when you say that you've determined that sieves won't work for you, because it seems to me that you just want to generate primes. Is that wrong?

  • 0
    For a sieve you need a finite number. Set up the list counting from 2 till n, then start sieving. The problem there is that computer memory will be your limit when you need to setup that list. That was my major problem. I saw my computer stuff 1GB of ram full with its list and got crashed around 48 million. Which means sieves are limited because of the limit you need to set.2011-04-28
  • 0
    In practice, I believe that Miller Rabin is the fastest known way. This is provably true if you believe the Generalized Riemann Hypothesis.2011-04-28
  • 0
    @Eric: I know Miller Rabin is the most practical way of finding a prime, but is it the best for finding all primes up to some value n? I'm not familiar with that, actually, as Miller Rabin suffices and it's all I use. But I wouldn't be surprised if there were a better way, maybe? Alternatively, can you refer me to a paper that speaks of the excellence of Miller Rabin, perhaps with GRH?2011-04-28
  • 1
    Under GRH Miller Rabin gives a polynomial time algorithm for testing primality. (As opposed to probabilistic) We test some $a$ relatively prime to $n$, and if it passes the test we call it a "Strong Witness." (This implies $n$ is composite) If we test all the members from a set of generators of the multiplicative group $$\left(\mathbb{Z}/n\mathbb{Z}\right)^*,$$ if $n$ is composite at least one must pass the test. Heres where GRH comes in: Assuming it we can prove that $$\{n:\ 1\leq n \leq 2\log^2n\}$$ forms a generating set for $$\left(\mathbb{Z}/n\mathbb{Z}\right)^*.$$2011-04-29
  • 0
    I am not sure without consulting some books, but I believe that under GRH, the probability goes up as well after each iteration. (Instead of $\frac{1}{4}$ we can get a bit smaller). I don't completely remember the lectures from my number theory course, but I am certain this is true. I could email my professor, he probably knows an exact answer. (I am interested now too, exactly how much does it improve?)2011-04-29
1

Let's say you have 1Gb of RAM to play with. Use half of that for your base sieve, which has room for 4 billion bits. You only need to store odd primes in your sieve, so this lets you generate the primes up to 8 billion.
Now you can use the other half of RAM for a sliding sieve, using your base sieve to generate all primes p in any interval a <= p <= b with b < (8 billion)^2 = 2^66. You only need to process 8 billion of these intervals to generate all primes less than 2^66. I realise that this is not equal to infinity, which is what you seem to want. But it's certainly much bigger than 120 trillion.
Of course, you will need to program it in assembly language to get the best results.