codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
// Print all prime numbers up to give number // Algorithm: Wheel factorization #include <iostream> #include <vector> #include <cassert> using namespace std; class CPrimeNumbers { vector<int> primes; static const int WHEEL_SIZE = 2 * 3 * 5; bool notPrimeArray[WHEEL_SIZE]; template<int N> void setNotPrime(bool (&npa)[N], int counter) { for(int i = counter; i < N; i += counter) npa[i] = true; } public: CPrimeNumbers() { assert(2*3*5 == WHEEL_SIZE); for(int i = 0; i < WHEEL_SIZE; ++i) notPrimeArray[i] = false; primes.push_back(2), setNotPrime(notPrimeArray, 2); primes.push_back(3), setNotPrime(notPrimeArray, 3); primes.push_back(5), setNotPrime(notPrimeArray, 5); } bool insertNum(int i) { if(i < 2) return false; if(i > WHEEL_SIZE && notPrimeArray[i % WHEEL_SIZE]) return false; for(vector<int>::iterator it = primes.begin() ; it != primes.end() ; ++it) { const int &iter = *it; if(iter * iter > i) break; if(0 == i % iter) return false; } primes.push_back(i); return true; } }; void printPrime(int upTo) { CPrimeNumbers primes; for(int i = 2; i < upTo; ++i) { if( primes.insertNum(i) ) cout << i << endl; } } int main() { printPrime(99999); return 0; }
Private
[
?
]
Run code
Submit