This is a project that is more or less for fun to see what is possible. Prime numbers that are more then 1 digit long all end with a 1,3,7,9. In order to find what is prime and what is not prime there are many different ways to go about it and I will list a few of them in the larger description. I am hoping that this will be useful. I am planing on using some time on amazons Ec2 which we will be testing next month and going over the best strategy for its use this month. Before we go on I like to state the intention of working with some very large prime numbers though my methods shouldn't be effected much by that fact. Regardless of the method that we use it will be essencial that a progress bar be used. My idea is that when the program is working on a digit range it will display the digit range it is working on and display the estimated time til it is complete with that digit range.
## Deliverables
Keep in mind that I am only looking for complete prime lists so some algorithms that would be used to find prime numbers of large lengths will not be useful at times. Ok the methods that I wanted to try out are as follows:
Since all prime numbers beyond 1 digit end with 1,3,7,9 a list can be made sort of as follows for primes ending with 1 if we skip 1 digit numbers
11
21
31
41
51
61
71
81
91
ect
The interesting part about making a list like this is when you take the knowledge of the only numbers that can equal a number that ends with 1 is
1*1, 1*11, 11*11 ect
3*7, 13*7, 3*17 ect
9*9, 9*19, 29*19 ect
and you take the first prime numbers that apply to that namely 3*7 you will get 21. Now starting from 21 if you count 3 from 21 in this list you will find another multiple of 3. If you count 7 from 21 you will find another multiple of 7. This is an interesting take on a sieve of sorts. If you take a certain range, say 100,000 numbers and run these numbers through it shouldn't take too long on a modern computer to get this done. These thoughts lead to this idea.
The program should create a binary number of about 100,000 bits entirely made of 0's. Each 0 represents a number ending with 1, At least in this particular example. Their will be 3 other list for numbers ending with 3,7, and 9. For the list 3 and 7 are the first numbers used so after the calculation we would go from 00000000000000000 to 01001001001001001 for the 3 and then for the 7, 01001001101001011
Once every prime number has been tested below the first number that is not a 1 that number is prime. 01001001101001011 which means the lowest number that exists in any of these list is 11 and therefore prime. This means that the next list should be worked on with 3,7, and 11. we move on to numbers that end with 3 then to 7 then to 9 and back to 1 until the 100,000 end has been reached and all primes have been tested. Now here is the tricky part. We now have a pattern that will be repeated forever but where it begins and end is going to change. To give you an idea of what I mean 1000001 is what I believe off the top of my head is the last number that would appear in the 1 list and is not divisible by 3. The next number if the list continued would be 1000011 and would be divisible by 3. For every number tested in this way we will count out how many it needs for its next hit as it were. That way we can move the pattern over in the next binary number which will show pretty quickly the next prime number. Now given the further you go the more numbers are picked up but the best part about this project is the calculations are down to a small amount so that the computer doesn't have to work with so many large numbers. If a computer was asked to calculate a million digit number it would be no problem but if you ask it to calculate 1,000,000,000! it would take a really long time. I will go over more with people that are interested and I am open to anybody's ideas that they believe to be faster. I will have various questions that I need answered before I accept any bid. Thank you all for your time and hopefully we find some cool things.