- #1
Canute
- 1,568
- 0
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
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
Last edited: