void sieve::sequential(){
std::list<double> seqPrimes;
double root = sqrt(max);
if ( max < 1 ) return;
// start with 2
seqPrimes.push_back(2);
// get everyone else
for(double i = 3; i < max; i += 2 ){
double s = 6;
if( ( std::fmod((i-1),s) == 0 ) || (std::fmod((i+1),s) == 0 ) )
seqPrimes.push_back(i);
}
// initialize iterators
std::list<double>::iterator outside = seqPrimes.begin();
std::list<double>::iterator inside = seqPrimes.begin();
++inside; // start inside as the one after
// start
while( outside != seqPrimes.end() ){
// if outside iterator is > root, done
if( *outside >= root ) break;
// inside iterator is the one were checking against
while( inside != seqPrimes.end()){
// if inside is divisible by outside, its not prime
if ( fmod( *inside, *outside ) == 0 ){
inside = seqPrimes.erase( inside ) ;
}
// check next number
++inside;
}
// we've elimated all numbers that are divisble by outside
// now go to the next one
++outside;
// set the inside counter to the next element of outside
inside = outside;
++inside;
}
std::cout << "# of primes < " << max << " : " << seqPrimes.size() << std::endl;
}
Then you should use unsignedlonglong, it also occupies 8 bytes and provides accurate representation of integer numbers.
Ordinary int can represent numbers up to 2,000,000,000. Do you need more?
void sieve::sequential(){
std::list<unsignedlonglong> seqPrimes;
unsignedlonglong root = sqrt(max);
if ( max < 1 ) return;
// start with 2
seqPrimes.push_back(2);
seqPrimes.push_back(3);
// get everyone else
for(unsignedlonglong i = 3; i < max; i += 2 ){
unsignedlonglong s = 6;
if( ( std::fmod((i-1),s) == 0 ) || (std::fmod((i+1),s) == 0 ) )
seqPrimes.push_back(i);
}
// initialize iterators
std::list<unsignedlonglong>::iterator outside = seqPrimes.begin();
std::list<unsignedlonglong>::iterator inside = seqPrimes.begin();
unsignedlonglong outside_prime, inside_num;
// start
while( outside != seqPrimes.end() ){
outside_prime = *outside;// set the inside counter to the next element of outside
if( outside_prime >= root ) break;
inside = outside;
if( inside != seqPrimes.end())
++inside;
// inside iterator is the one were checking against
while( inside != seqPrimes.end()){
inside_num = *inside;
// if inside is divisible by outside, its not prime
if ( inside_num % outside_prime == 0 ){
inside = seqPrimes.erase( inside ) ;
}
// check next number
if( inside != seqPrimes.end())
++inside;
}
// we've elimated all numbers that are divisble by outside
// now go to the next one
++outside;
}
std::cout << "# of primes < " << max << " : " << seqPrimes.size() << std::endl;
}
void sieve::sequential(){
std::list<int> seqPrimes;
int root = sqrt(max);
int s = 6;
if ( max < 1 ) return;
// start with 2 and 3
seqPrimes.push_back(2);
seqPrimes.push_back(3);
// get everyone else
for (int i = 6; i < max; i += 6){
seqPrimes.push_back(i - 1);
seqPrimes.push_back(i + 1);
}
// initialize iterators
std::list<int>::iterator outside = seqPrimes.begin();
std::list<int>::iterator inside = seqPrimes.begin();
int outside_prime, inside_num;
// start
while( outside != seqPrimes.end() ){
outside_prime = *outside;
// only check until root+1 ( compensate rounding errors )
if( outside_prime >= root+1 ) break;
// set the inside counter to the next element of outside
inside = outside;
if( inside != seqPrimes.end())
++inside;
// inside iterator is the one were checking against
while( inside != seqPrimes.end()){
inside_num = *inside;
// if inside is divisible by outside, its not prime
if ( inside_num % outside_prime == 0 ){
inside = seqPrimes.erase( inside ) ;
continue;
}
// check next number
if( inside != seqPrimes.end())
++inside;
}
// we've elimated all numbers that are divisble by outside
// now go to the next one
++outside;
}
std::cout << "# of primes < " << max << " : " << seqPrimes.size() << std::endl;
}