By using a sieve created by Prime Number Tables set up by the formula PN+(PNx6) for numbers generated by 6n+or-1, takes 182 calculations to identify 170 composite numbers. Using the Sieve of Eratosthenes would take around 1600 calculations. The Prime Number Tables identify all the composite numbers on the the list of 332 possible prime numbers:
5,11,17,23,29,35,41,47,53,59,65,71,77,83,89,95,101,107,113,119,125,131,137,143,149,155,161…
7,13,19,25,31,37,49,55,61,67,73,79,85,91,97,103,109,115,121,127,133,139,145,151,157,163,169…
Prime Number Table for:
5 identifies the multiples of 5 with 67 calculations (the Sieve of E: 249)
7: 23 calculations (the Sieve of E: 133)
11: 29 calculations (the Sieve of E: 98)
13: 11 calculations (the Sieve of E: 75)
17: 17 calculations (the Sieve of E: 57)
19: 4 calculations (the Sieve of E: 51)
23: 12 calculations (the Sieve of E: 42)
29: 5 calculations (the Sieve of E: 34)
31: 1 calculations (the Sieve of E: 31)
41: 3 47: 3 53: 2 59: 2 calculations (the Sieve of E:0)
71: 2 89: 1 101: 1 calculations (the Sieve of E: 0)
107: 1 113: 1 131: 1 137: 1 calculations (the Sieve of E: 0)
2: 0 calculations (the Sieve of E:499)
3: 0 calculations (the Sieve of E: 332)
Total Calculations:
A Sieve using PN Tables: 187 calculations to find 166 Prime Numbers by identifying 166 composite numbers (10 of 11 duplicate of multiples of 5)
Sieve of Eratosthenes: 1601 calculations to find 168 Prime Numbers by identifying 832 composite numbers (769 duplication of calculations)
Note: What I am really hoping for is some help. I have tested this up to 1411. There is no reason to believe it wouldn't go to whatever number. It seems since it deals with less numbers and less calculations, it would use less memory. If you look at the tables and what I have been able to research it makes Primes numbers even more interesting for children who might then take up more interest in math. Hey, I am a guy who works in a grocery store who just likes to think about things. I need help. People keep telling me about the Sieve of Eratosthenes. I have given a comparison between the 2 sieves. Would you rather make 1600 calculations or 187?
You can check on my website: https://mrspudgetty.wixsite.com/mr-spudgetty/prime-numbers
Best Answer
What you are looking for is a computational function that returns the list of primes less than 1000, and works as efficiently as possible, on just that problem.
There are 168 primes between 1 and 1000, so any method will take at least 168 operations, obviously.
Suppose you could find approximately a list of 13 numbers and a disjoint other list of 13 numbers, such that precisely every prime occurs when you sum the two sets together elementwise, and no more than that (no composites; otherwise more testing would be required to filter them out).
What I mean is:
$$ A := \{0, 2, 6\} \\ B := \{5, 11, 17\} \\ A + B = \{ 5, 11, 17, 7, 13, 19, 23\} $$
You can most likely find two sets of around 13-20 elements each such that when you sum the sets you get your list. The sets would then be constants in your program, and the program that generates your output in under 200 operations, actually in 169 arithmetic operations (less if you're allowed to include $B$ which could be made to be all prime numbers if there's a $0$ included in $A$).
See:
Compressing the primes using addition