Sieving for Primes - A Program to Find Primes in Any Range

[Canute]

Sieving for Primes

For a while now I've been messing about in a spreadsheet trying to make sense of the pattern of the primes. I've at last managed to construct a simple programme that will sieve a range of numbers leaving only the primes. But I'm wondering just what it is I've done, whether it has any mathematical significance.

The programme runs in Excel. The user inputs a value for N and this sets the position of the range of numbers to be seived. The range is always 130 numbers. (E.g. For N = 10,000,000 the range is 9999925 to 10000055).

The programme lists all numbers in the specified range that occur at 6n+/-1. (All others are ignored). It then lists all numbers in this same range that occur at 6n+/-1 and which have prime divisors. It identifies these divisors.

Because I can't do macros the user (me) then has to cross check the two lists by hand. All the numbers that appear in the second list (the multiples of primes) are crossed off the first list (the possible primes). The numbers remaining are prime.

It's a very simple programme (the file is under 500 KB). It will remain a bit clunky until I can get it do the crosschecking of the two lists automatically, but it seems to work. Checking for primes by hand takes a couple of minutes for ranges of 130 numbers up as far as 100,000,000. (Soon after that the numbers get too big for my version of Excel). At the moment it sieves a range but the next upgrade will enable the user to test any single N for primacy.

I suppose it won't be much use unless it can search for very, very big numbers, but there seems no reason why it shouldn't be able to do this given some decent computing power. My second-rate PC does all the calcs. for ranges of numbers up to 100,000,000 instantaneously, but I have no idea what's involved in processing numbers with hundreds of digits.

Does this sound interesting? Are there other programmes/algorithms that can already do the same thing? Will I be rich and famous or have I overlooked some obvious flaw in my plan?

By the way, is there anybody here who is an Excel expert and who wouldn't mind answering a few questions about some of its more advanced features?

Thanks in advance for any responses.

Canute

 

[nate808]

there are many other programs that can do the same thing. Some of the largest primes know today are hundreds of thousands of digits long, your 9 digit primes pale in comparison. In 1772 euler proved a number in the billions to be prime, (without a computer obviously) By the way, the largest known prime is 2^25964951-1. Over 7 million digits long

 

[Hurkyl]

It's useful to have prime generating algorithms, because sometimes you want a program that has access to, say, all the primes smaller than 10,000. I understand the best algorithms (wheel sieve, I think) can generate these lists of primes faster than they could be read from disk!

And if you have the primes through 100,000,000 = 10^8, you would actually be able to use a sieve to find all the primes in some interval [a, b] where a and b are less than 10^16!


The point of a sieve, though, is that it tests many numbers. While it might take N work to test a single number for divisibility by p, it takes far less than N * 10^6 work to test 10^6 numbers for divisilibity by p. If you're looking to test single number N for primality, trial division by all primes smaller than √N would be faster than trying to sieve!

 

[Canute]

Yeah, I know that my 9-digits isn't much. However the programme is limited only because Excel can't handle big numbers. If it could handle the number of digits then I could test any N for primacy up to about 36 digits without rewriting it. On a better system I don't know what the limit would be. When N gets up above 100 digits or so it might start choking. I can't see why it should but then I don't know anything about computing with such large numbers.

This raises another question. Do you know how high is the highest prime for which all primes below it are known? Although we know some enormous primes I presume that these are mostly isolated cases, that there are still unknown primes that are smaller than these. Up to what number has the complete sequence of primes been calculated, with no gaps? Or, in other words, in what range of numbers is the lowest unknown prime likely to be found?

 

[Canute]

It's useful to have prime generating algorithms, because sometimes you want a program that has access to, say, all the primes smaller than 10,000. I understand the best algorithms (wheel sieve, I think) can generate these lists of primes faster than they could be read from disk!

Fascinating. I wish I knew more about this. Would you be able to explain in outline how a wheel sieve works?

And if you have the primes through 100,000,000 = 10^8, you would actually be able to use a sieve to find all the primes in some interval [a, b] where a and b are less than 10^16!

I think I can get past 10^16 without needing to know any lower primes.

The point of a sieve, though, is that it tests many numbers. While it might take N work to test a single number for divisibility by p, it takes far less than N * 10^6 work to test 10^6 numbers for divisilibity by p. If you're looking to test single number N for primality, trial division by all primes smaller than √N would be faster than trying to sieve!

Yes, good point about sieves. It took me a while to realize how much more efficient sieving a range is than testing single numbers. I've found a way of testing N for primality which does not depend on trial division or on knowing the primes below sqrt N, but at the moment can't figure out whether this method is old news or interesting. I need to know more about how existing programmes test for primality, so any help on that would be appreciated.

 

[Hurkyl]

I don't know all the gory details about a wheel sieve, but I know it's based on recursively generalizing the fact you were only sieving on 6n-1 and 6n+1.


Here's a sketch of what I think is the rough idea (which probably isn't near the most efficient implementations):


You've already sieved the interval [1, 6] by 2 and 3, leaving the numbers {1, 5}, and recognize that 5 is the next prime.

So, you "roll" your "wheel" along 5 times to fill out the interval [1, 30], giving {1, 5, 7, 11, 13, 17, 19, 23, 25, 29}, and you cross out everything divisible by 5, leaving {1, 7, 11, 13, 17, 19, 23, 29}.


Then, you recognize 7 as the next prime, so you roll this wheel out 7 times to the interval [1, 210], and cross out all the multiples of 7.

But wait, you don't need to go through all multiples of 7, just its multiples by {1, 7, 11, 13, 17, 19, 23, 29}! (Because all of its other multiples have already been crossed off!)

And now, since I happen to have only wanted all primes through 200, I stop rolling my wheels (I could have stopped earlier), and just cross out the multiples of the primes as I find them.


You really should do a search on it to see if you can find a good description of a good implementation.



By the way, you probably want to look at http://mathworld.wolfram.com/PrimalityTest.html .

 

[Canute]

Thanks. It seems that by the wheel sieve method one has to check all the multiples of each prime from the first multiple up to the target number. Is that the case?

I checked out your link, which was very useful. It states that "The state of the art in deterministic primality testing for arbitrary numbers is elliptic curve primality proving. As of 2004, the program PRIMO can certify a 4769-digit prime in approximately 2000 hours of computation (or nearly three months of uninterrupted computation) on a 1 GHz processor using this technique."

It seems my technique needs to be a lot more efficient to compete. I've added a single number tester now and it will check N for primality up to about 10^11, the software limit, instantaneously. In 2000 hours I reckon I could get to about 10^25. Pathetic really. Mind you, I get confused by all these all these zeros so may have miscalculated. But back to drawing board I think, for a faster method. Not much chance of success but it's fun trying.

 

[shmoe]

How does your program find the numbers in the given range that have prime divisors? (if you're willing to divulge)

If you want more info on the Wheel sieve, look for an article by Paul Pritchard, "Explaining the Wheel Sieve". I found a scan of it online before but unfortunately can't seem to find the link now.

Some interesting info at http://primes.utm.edu/notes/faq/LongestList.html where they say the largest list of primes is up to about 10^17 and have links to all sorts of other fun stuff you might find usefull

 

[Canute]

Great. Thanks. I'll check out those links. I don't want to get into exactly how the programme works, since it's based on an idea which I'm hoping will have more possibilities than I've yet discovered, but basically it finds numbers with prime divisors by multiplication of the primes in sequence, clocking only those that fall at 6n+/-1 and which are in the target range. It does no calcs for any numbers outside that range. It uses no list of primes, although it would be much more efficient if I fed it with one.

There is a formula which all multiples of primes obey which allows it to zero in immediately on only those that are relevant. This method seems no more efficient than trial division for single numbers, at the moment anyway, but may be quicker for sieving a range. I can only test it up to about 10^7 on Excel, but my guess is that it will sieve a range of 130 numbers efficiently up to about 10^14. (The range can be easily expanded). After that I'm not sure. Having thought again about what I said above it might be able to sieve a range around 10^35 in about 2000 hours (on a standard PC). It ain't much but then I'm no mathematician, which is why I've had to come at the problem in a rather naive way.

I've got a feeling it could be much improved but I'd need to understand something about Fourier analysis. This is because I've come at the problem as a mathematically illiterate musician, in terms of the interaction or 'beating' of waves at different frequencies. The number line and the audio spectrum have much in common.

The trouble is that thinking about the primes means having ones head filled with numbers all day. I don't know how you guys who do it all the time stay sane.

 

[Cynical]

To Canute - I am glad someone else would like to understand the principles behind Reimanns Hypothesis without getting bogged down with the math. Mathematics is a pure substitute for understanding and mathematicians use it like a blind man uses a stick, they stumble around in the dark and may even find what they are looking for but they still cannot see.

 

[Hurkyl]

Someone who is used to living in the dark gets blinded when exposed to the light. :tongue:

(Old wise man's saying: every saying has an opposite)