this is attempt for sieve of Eras algorithm...but it works freaking slow for numbers above 10000..i was wondering is there a way to make it faster (I am yet to try the Euler sieve algorithm..but I don't see how it is any different)? I don't think it would make any difference if i used vectors..and i don't know how to use vectors anyway.Code:
#include <iostream>
#include <list>
using namespace std ;
#define SIZE 10
int main()
{
list<unsigned long int> sieve ;
list<unsigned long int>::iterator it ;
long int i =2 ;
while(i<SIZE)
{
sieve.push_back(i) ;
i++ ;
}
it = sieve.begin() ;
i=*it;
unsigned long int sum =0;
while(i*i < SIZE)
{
i = *it ;
sieve.push_back(*it) ;
it = sieve.erase(it) ;
while(it!=sieve.end())
{
if(i!=*it&&(*it)%i==0)
{
it = sieve.erase(it) ;
}
else
{
it++ ;
}
}
it = sieve.begin() ;
}
it = sieve.begin() ;
while(it!=sieve.end())
{
sum+=*it ;
it++ ;
}
cout << "Sum of all prime is: " << sum ;
cin.get() ;
return 0 ;
}
One more thing..when I remove the multiples from a list and i increment the iterator, the program crashes i had to use an else for that, to increment the iterator if an element is not erased.
I don't understand why it crashes, i mean
i would safely assume that when I removed from a list and incremented the list thereafter the iterator would point to valid address if there was an element after it. But since I can't be sure, it is better to use the else to increment the iterator if not erased... :S