Euler #47

euler.cpp

#include <vector>
#include <iostream>
#include <algorithm>

class Primegen
{
	std::vector<int> primes; //store all the primes we've generated so far

	void nextprime(void); //add one new prime to the end of the list
	
	public:
	Primegen(void); //constructor 
	int operator [] (unsigned int n); //return the nth prime number
	bool isprime(int n); //return true if n is prime
};

void Primegen::nextprime()
{
	int current=primes.back();
	bool isprime=true;

	do
	{
		current++;
		isprime=true; //start by assuming number is prime
		for(unsigned int i=0; i<primes.size() && isprime && primes[i]*primes[i] <= current; i++)
		{
			if(current%primes[i]==0)
			{
				isprime=false; //number is not prime if it has a factor
			}
		}

	}while(!isprime);

	primes.push_back(current);

}

Primegen::Primegen(void)
{
	primes.push_back(2); //seed the generator with a single prime
}

int Primegen::operator [] (unsigned int n)
{
	while(n>=primes.size())
	{
		nextprime();
	}

	return primes[n];
}

bool Primegen::isprime(int n)
{
	while(n>primes.back()) //make sure we have at least one prime bigger than n
	{
		nextprime();
	}
	
	return std::binary_search(primes.begin(), primes.end(), n);
}

int distinct_factors(Primegen &primes, int n)
{
	int ret=0;
	int p=primes[0];

	for(int i=0; primes[i]*primes[i] < n; p=primes[++i])
	{
		if(n%p==0)
		{
			ret++;
			while(n%p==0)
			{
				n/=p;
			}
		}
	}
	
	if(n!=1)
	{
		ret+=1;
	}

	return ret;
}

int main()
{
	Primegen primes;
	int streak=0, i;

	for(i=3; streak<4; i++)
	{
		if(distinct_factors(primes, i) >= 4)
		{
			streak++;
		}
		else
		{
			streak=0;
		}
	}

	std::cout << i-4 << std::endl;

	return 0;
}

I believe that 2 * 2 * 2 * 16741 = 133928 is the correct solution for problem 47.