Original post by Zahlman

    for (int i = 0; i < count; ++i) {      if (!(m % s)) { // current value is divisible by a former prime;                         // discard it        prime = false; break;        // In case you're wondering, solving this with a goto is just as tricky;        // you'd need to put it at the *end* of the outer loop, with no        // action following it, which is rather bizarre.      }    } 

I don’t see how that will work. You only compare the current number to be considered with the existing primes. Won’t you need to compare it with ALL the numbers from 2 to half it self to see if it’s prime, and not just the known primes smaller than it self?

Quote:Original post by Motz
No, you don't need to. All of the non-primes smaller than N are made up of the primes in that set. For example, 24 is not a prime, it's quite obviously divisible by 6. As such, it must also be divisible by 3 and 2, so why make more work for yourself by checking it against 6 once you know that it divides by 2 and 3? By the same token, 23 is a prime number. 10 is just under half of 23. However, 10 cleanly divides by 5 and 2. If 23 doesn't divide by 5 or 2, then it can't be divisible by 10, so why check it?

There's a mathematical law (can't remember which) that states that every number N is the product of two primes, p and p'. Thus, if a number is not divisible by any primes, then it won't be divisible by non-primes either, since they themselves are the products of smaller primes.

#include <iostream>#include <iomanip>#include <vector>#include "bits.h"void Sieve(bits& s ,unsigned int n){	unsigned int m,i;	    	std::cout << "Filling set: " << 1 << " to " << n << std::endl << std::endl;	s.resize(n);	s.set(); // set(), clear() with no argument sets/clears all elements in the bit object;	s.clear(0);	s.clear(1);		std::cout << "Set Filled, " /*<< s.size() << " Items."<< std::endl /**/;	std::cout << "Removing non-primes:" << std::endl << std::endl;		m = 0;	for(i=0; i < n; i++)		if(s)		{			m++;			for(int k = (i+i); k < n; k+=i)				s.clear(k); 		}		std::cout << "Non-primes removed: " << m << " items remaining" << std::endl;	std::cout << "Primes ratio: " << (float)m/(float)n  << std::endl; }void Sieve(std::vector<unsigned int>& s ,unsigned int n) {  unsigned int m,i;  std::cout << "Calculating primes: " <<  std::endl <<  std::endl;  s.erase(s.begin(),s.end());  //s.push_back(1);  s.push_back(2);  for(m=3; m<=n; m+=2) {    int count = s.size();    bool prime = true;    for (int i = 0; i < count; ++i) {      if (!(m % s)) { // current value is divisible by a former prime;                         // discard it        prime = false; break;        // In case you're wondering, solving this with a goto is just as tricky;        // you'd need to put it at the *end* of the outer loop, with no        // action following it, which is rather bizarre.      }    }    if (prime) s.push_back(m);  }  std::cout << s.size() << " primes calculated." << std::endl;}int main(){		unsigned int count = 0;	unsigned int N = 1000000;	bits Bit(N);		std::vector<unsigned int> primes;	std::vector<unsigned int>::iterator itr;	Sieve(Bit,N);			Sieve(primes,N);}

//FILE: bits.h#include <vector>class bits{	std::vector<unsigned char> B;public:	bits(unsigned int size)	{		B.resize(1 + size/8);	}	void resize(unsigned int size)	{		B.resize(1 + size/8);	}	unsigned int size()	{		return B.size()*8;	}	void set(unsigned int bit)	{		unsigned int p = bit/8;		unsigned int b = bit%8;		unsigned char m = 1 << b;		B = B | m;	}	void set()	{		for(unsigned int i = 0; i < this->size(); i++)			set(i);	}	void clear(unsigned int bit)	{		unsigned int p = bit/8;		unsigned int b = bit%8;		unsigned char m = 1 << b;		m = ~m;		B = B & m;	}	void clear()	{		for(unsigned int i = 0; i < this->size(); i++)			clear(i);	}		bool operator [](unsigned int bit)	{		unsigned int p = bit/8;		unsigned int b = bit%8;		unsigned char m = 1 << b;		m = m & B;		m = m >> b;		return m;	}};

Quote:Original post by Motz
There's a mathematical law (can't remember which) that states that every number N is the product of two primes, p and p'.

Quote:Original post by Grain
0k. but for some reason that method painfully slow. I just copied and pasted Zahlmans code and compared it side by side with the bit array method, and the difference is ridiculous. That method takes about a minute and a half for just 1 million ints. As where the actual Sieve of Eratosthenes using bit aray takes less than a second.

Just for reference here is the entire program as it is now
*** Source Snippet Removed ***

*** Source Snippet Removed ***
EDIT: Using the Bit array is insanely fast. Way faster than my original set method. I just rechecked my original size of 35 million ints which took about 1 minuet using std::set. But with the bit array it took only a couple seconds!!

void Sieve(std::vector<unsigned int>& s ,unsigned int n) {  unsigned int m;  std::cout << "Calculating primes: " <<  std::endl <<  std::endl;  s.erase(s.begin(),s.end());  //s.push_back(1);  s.push_back(2);  int root = 2;  for(m=3; m<=n; m+=2) {    int count = s.size();    bool prime = true;    while (root * root < m)    {      ++root;    }    for (int i = 0; i < count && s <= root; ++i) {      if (!(m % s)) { // current value is divisible by a former prime;                         // discard it        prime = false; break;        // In case you're wondering, solving this with a goto is just as tricky;        // you'd need to put it at the *end* of the outer loop, with no        // action following it, which is rather bizarre.      }    }    if (prime) s.push_back(m);  }  std::cout << s.size() << " primes calculated." << std::endl;}

Quote:Original post by nmi

Quote:Original post by Motz
There's a mathematical law (can't remember which) that states that every number N is the product of two primes, p and p'.

Thats wrong, just take 24 which is 2*3*4, which are more than two primes.
The theorem you remebered may be this one:
http://mathworld.wolfram.com/FundamentalTheoremofArithmetic.html

Quote:Original post by Prozak
Also remember that all primes above 2 end in 1,3,7 or 9.

So, instead of populating your array with loads of numbers, just populate them with those that finish in these digits.

Quote:Original post by Motz

Quote:Original post by nmi

Quote:Original post by Motz
There's a mathematical law (can't remember which) that states that every number N is the product of two primes, p and p'.

Thats wrong, just take 24 which is 2*3*4, which are more than two primes.
The theorem you remebered may be this one:
http://mathworld.wolfram.com/FundamentalTheoremofArithmetic.html

4 isn't a prime, it's the product of 2 and 2. But I was wrong anyway, just checked back on a simulation I did a while ago ;) Sorry about that. Anyhow, the point it supported still stands, since every non-prime is divisable by 1 or more primes and thus you needn't try dividing by non-primes.