codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
// Populate prime numbers using wheel factorization // Algorithm should be fast enough to print 10001st prime number in less than 2 second // (Before encountering timeout on codepad) // 10001st prime number is 104743 // Is it possible to write a code that can print 9,99,999th prime number? #include <iostream> #include <vector> using namespace std; /** * This function prints all prime numbers from 2 to upTo. * * @param [in] upTo Largest number to test for prime. */ void printPrimes(int upTo) { if(upTo < 2) return; vector<int> primes; primes.reserve(upTo / 8); primes.push_back(2); cout << 2 << endl; if(upTo > 2) { primes.push_back(3); cout << 3 << endl; } int limit = 2, nextsq = 3 * 3; for(int i = 5; i <= upTo; i += 2) { if(nextsq <= i + 2) { ++limit; const int s = limit + 1; nextsq = s * s; } for(vector<int>::iterator it = primes.begin(); *it <= limit; ++it) { if(0 == i % *it) goto skipped; } primes.push_back(i); cout << i << endl; skipped: i += 2; for(vector<int>::iterator it = primes.begin(); *it <= limit; ++it) { if(0 == i % *it) goto skipped2; } primes.push_back(i); cout << i << endl; skipped2: i += 2; } } int main(int argc, char *const *argv) { if(1 == argc) { printPrimes(112233); } else for(int i = 1; i < argc; ++i) { printPrimes( atoi(argv[i]) ); } return 0; }
Private
[
?
]
Run code
Submit