Home » C++ Programming | RSS |

## The sieve of Eratosthenes | |

Hi all, I have some code here that I found online for the sieve but it seems limited to in the range of 1000 or so. Do you know which part of it requires change to let there be no limit to the values for the sieve? Or do you know what needs changing to allow for a great value to be the limit of the sieve? I'm thinking of numbers approaching 1000 digits. I realise that would take an awfully long time to output. /* Sieve Of Erathosthenes by Denis Sureau */ #include <stdlib.h> #include <stdio.h> #include <iostream> #include <vector> #include "BigIntegerLibrary.hh"usingnamespace std; void eratosthenes(int top) { vector<int> all(top); int idx = 0; std::cout << "1 "; int prime = 3; while(prime <= top) { for(int x = 0; x < top; x++) { if(all[x] == prime) goto skip; } std::cout << prime << " "; int j = prime; while(j <= (top / prime)) { all[idx++] = prime * j; j += 1; } skip: prime+=2; } std::cout << std::endl; return; } int main(int argc, char **argv) { if(argc == 2) eratosthenes(atoi(argv[1])); else eratosthenes(1000); cin.get(); return 0; } ## 6 Answers FoundOn 1/13/2011 4:56 PM, Michael.1975 wrote:
That doesn't seem to be the case. The program accepts the range on the command line, and only defaults to 1000 when none is given. Have you tried running it with a larger value as a command line parameter?
I doubt that. Very few people (if any) can imagine numbers appoaching 10^1000. For comparison, the observable universe is thought to contain approximately 10^80 atoms.
In fact, probably longer than the age of the universe. In other words, completely impractical. Igor Tandetnik I don't know if this is right or not, I'm just skimming and I found this: int main(int argc, char **argv) { if(argc == 2) eratosthenes(atoi(argv[1])); if you change the "else eratosthenes(1000)" To whatever you want number to change it to. I don't know though, just skimming I can imagine the Mersenne prime 2^43,112,609 with 12,978,189 decimal digits just fine. And its primality was verified by a computer (though with the Lucas-Lehmer test, not the Sieve of Eratosthenes). On 1/13/2011 6:11 PM, Stephan T. Lavavej - MSFT wrote:
Can you really? How thick a stack of paper would it take to print it out?
It's much easier to verify whether a given number is prime, than it is to find a prime in the first place. That's why people concentrate on numbers of a special form, which are analytically shown to be much more likely to be prime than a number of comparable magnitude just picked at random. Sieve of Eratosthenes is an algorithm for finding primes, and is largely a toy, impractical beyond some, rather low, threshold. Igor Tandetnik > Can you really? How thick a stack of paper would it take to print it out? Using a reasonable font size, and estimates of 80 columns and 56 rows, and two-sided printing, 1449 pages. > It's much easier to verify whether a given number is prime, than it is to find a prime in the first place. Actually, finding primes isn't too hard. The probability of a number around 10^1000 (~= 2^3322, so a very realistic size) being prime is around 1 / ln(10^1000) == 1 / (1000 * ln(10)) == 1 / 2302.585... (see http://en.wikipedia.org/wiki/Prime_number_theorem ) and that's counting numbers with tiny divisors like 2, 3, 5. It gets better, because it takes only one failed probabilistic primality test to exclude a number from consideration (see http://en.wikipedia.org/wiki/Primality_test ). After narrowing down the candidates, then you can throw a bunch of probabilistic primality tests at a survivor (this is "good enough" for encryption), or a deterministic test if you want that (the probabilistic tests beforehand are cheap in comparison). > That's why people concentrate on numbers of a special form, which are analytically Actually, Mersenne numbers are special because they have an exceedingly fast deterministic primality test (the fastest one known). I don't know if Mersenne numbers can be said to be "much more likely" to be prime than ordinary numbers (this is beyond my amateur mathematical ability). Let's play around with C++:
C:\Temp>type primes.cpp #include <math.h> #include <iostream> #include <ostream> usingnamespace std; bool prime(constint n) { if (n < 2) { returnfalse; } for (int i = 2; i <= n / i; ++i) { if (n % i == 0) { returnfalse; } } returntrue; }; int main() { double total_prime_exponents = 0.0; double total_all_exponents = 0.0; for (int i = 2; i <= 43112609; ++i) { constdouble d = i < 31 ? log((1 << i) - 1.0) : i * log(2.0); if (prime(i)) { total_prime_exponents += 1 / d; } total_all_exponents += 1 / d; } cout << "total_prime_exponents: " << total_prime_exponents << endl; cout << " total_all_exponents: " << total_all_exponents << endl; } C:\Temp>cl /EHsc /nologo /W4 /MT /O2 /GL primes.cpp primes.cpp Generating code Finished generating code C:\Temp>primes total_prime_exponents: 4.73798 total_all_exponents: 24.9863
Looking at only those Mersenne numbers with prime exponents, the Prime Number Theorem says we should expect about 5 of them to be prime, when in fact 47 of them in this range are known to be prime (there may be more). It certainly appears that by exploiting an easy-to-prove fact about Mersenne numbers (for 2^N - 1 to be prime, N must be prime) and by performing a tiny amount of work (testing N for primality), the remaining Mersenne numbers with prime exponents are about 10 times more likely to be prime than numbers chosen at random. Without exploiting that fact, Mersenne numbers in general don't appear to be "especially prime". The ultra-trivial fact about them is that they're all odd, and the chance of a random odd number being prime is double the chance of any random number being prime, so the Prime Number Theorem tells us to expect about 50 primes in this range, and we've found 47. (Ooh, conjecture! It would be awesome if there were exactly 3 currently-unknown Mersenne primes with exponents between 20,996,011 and 43,112,609.) That was fun. > Sieve of Eratosthenes is an algorithm for finding primes, Of course. I have a small sieve program, I might post it on my forum if I am bored. I use it in my Fibonacci program that is free on my developer site.
Search for The sieve of Eratosthenes |