Euler Problem 12 runs for 10+ minutes with no solution

[Darkenor]

So, I know it goes against everything socially acceptable to come to a forum as a newbie, drop off your entire source, and say "You canz debug for meh, plz?" - but I think I'm going to do just that.

But before I do, here's a little background -

I'm working Euler problem 12 and decided to implement the sieve of eratosthenes to help. In case you aren't familiar with what that is, here's a link:

http://projecteuler.net/index.php?section=problems&id=12

I know it's not the fastest algorithm on the planet (as I'm sure someone will point out) but it's the one I chose to use and I think it will work for my purposes.

I believe my sieve is working. And further, I believe that my program's method of finding the divisors (finding the prime factors, taking their exponents, and then adding one to them and multiplying them) is also a solid solution. The problem comes in that my program has been running for 12 minutes solid and still doesn't have a solution - which strikes me that there's either a bug or a design flaw, or both (because I am new to this and sort of suck).

With all that, here's my code. If you can help me debug it, I'd really appreciate it. I surrender any ownership, so use it as you like. Or make fun of it as you like. :)

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <math.h>

#pragma warning(disable: 4244)

using namespace std;

vector<__int64> sieve(__int64);
__int64 findtrianglenumber(__int64);
__int64 finddivisors(vector<__int64> primevector, __int64);

int main()
{
	__int64 n =3;
	__int64 Tn = 0;
	__int64 numdivisors=0;
	vector<__int64> primesonly;

	bool found = false;

	while (!found)
	{
		Tn = findtrianglenumber(n);
		cout<<"Examining triangle number "<<n<<". It is: "<<Tn<<". ";

		vector<__int64> myvector = sieve(Tn);

	/*	for (__int64 x=0; x<myvector.size(); x++)
		{
			cout<<myvector.at(x)<<" ";
		}
*/
		//cout<<"\n\nThe primes which are factors are:\n\n";
		int stopper = static_cast<int>(sqrt(static_cast<double>(Tn)));
		for (__int64 x=0; x<stopper; x++)
		{
			if (Tn%myvector.at(x) ==0)
			{
			//	cout<<myvector.at(x)<<" ";
				primesonly.push_back(myvector.at(x));
			}
		}
		numdivisors = finddivisors(primesonly, Tn);
	
		cout<<"The number of divisors is "<<numdivisors<<".\n";
	
		if (numdivisors ==500)
		{
			cout<<"Found it! It is "<<Tn;
			found = true;
		}
		n++;
		cout<<"\n";
	}

	system("pause");
	return 0;
}

vector<__int64> sieve(__int64 number)
{
	/* Algorithm:
	DONE - Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).
	DONE - Initially, let p equal 2, the first prime number.
	DONE - Strike from the list all multiples of p less than or equal to n. (2p, 3p, 4p, etc.)
	DONE - Find the first number remaining on the list after p (this number is the next prime); replace p with this number.
	DONE - Repeat steps 3 and 4 until p2 is greater than n.
	DONE - All the remaining numbers in the list are prime. */
	vector<__int64> fullsieve; //Sieve
	vector<__int64>::iterator iter; //Vector iterator for cleanup (used later)
	__int64 divisor=2; //Initial Divisor
	__int64 primecount=0;  //Used to reference total number of primes for easy access

	//check to make sure the number a user is passing is less than 2
	try
	{
		if (number<3)
		{
			throw 1;
		}
	}
	catch (int)
	{
		cout<<"The number must be higher than 2. Exiting now.\n";
		return fullsieve;
	}
	//Make a vector all numbers 0 to N (zero is kept for ease of algorithm)
	for (__int64 x=0; x<number+1; x++)
	{
		fullsieve.push_back(x);
	}

	//Actual Sieve is here
	while (divisor*2 < number) //Check if divisor is 1/2 N, if so we are done
	{
		//start at divisor*2, increment by divisor until the divisor's next iterator is greater than the remaining elements in the vector
		for (__int64 x=divisor*2; x<fullsieve.size(); x+=divisor)
		{
			if (x>number)
			{
				break;
			}
			else
			{
				fullsieve.at(x) = 0; //replace non-primes with 0. 
			}
		}

		//loop through the whole vector here
		for (__int64 x=0; x<number+1; x++) 
		{
			if ((x>divisor) && (fullsieve.at(x) !=0)) //if x is greater than the divisor, divisor is x. break out if found
			{
				divisor = x;
				break;
			}
		}
	}

	//Remove Zeros
	fullsieve.erase(remove(fullsieve.begin(), fullsieve.end(), 0), fullsieve.end());
	//Remove the number 1
	fullsieve.erase(fullsieve.begin());
	//Count primes (currently doesn't do anything, might use this in a class later)
	primecount = fullsieve.size();

	return fullsieve;
}
__int64 findtrianglenumber(__int64 number)
{
	__int64 trianglenumber = (number*(number+1))/2;

	return trianglenumber;
}
__int64 finddivisors(vector<__int64> primevector, __int64 TriangleNum)
{
	
	vector<int> exponentoccurence;
	__int64 tempTn=TriangleNum;
	__int64 numdivisors=1;

	for (__int64 x=primevector.size()-1; x>-1; x--)
	{
		__int64 count=0;
		while (tempTn%primevector.at(x) == 0)
			{
				tempTn = tempTn/primevector.at(x);
				count++;
			}
		exponentoccurence.push_back(count+1);
	}
	
	for (__int64 x=0; x<exponentoccurence.size(); x++)
	{
		numdivisors = numdivisors*exponentoccurence.at(x);
	}
	return numdivisors;
}

[ne555]

//Make a vector all numbers 0 to N (zero is kept for ease of algorithm)
	for (__int64 x=0; x<number+1; x++)
	{
		fullsieve.push_back(x);
	}

Only that is O(n²)
Change your method for finding primes (I suggest you a dynamic one). Also, why are you recalculating all the primes over and over again?

Also pass your vectors as references instead of copies (const references if you aren't going to modify them)

[Darkenor]

Hey, thanks for the input. :)

I've seen a couple people suggest using the sieve of atkin. Is that a good solution? Do you have another algorithm that you could recommend? I'm not a programming ninja, so the easier to implement, the better.

And yes - the const reference is definitely a good idea. I'll change that tonight.

[Darkenor]

Oh - and you mentioned counting find primes over and over again? I don't "think" I am - I should do it once per loop as it iterates through the triangle numbers? Am I mistaken?

[ne555]

You test a number, find all the primes to that number, compute the number of divisors. You do that for every triangle number.

Primes to 10: 2 3 5 7 
Primes to 21: 2 3 5 7 11 13 17 19

You already know that 2 3 5 7 were primes numbers, but you calculate them again.

Another mistake is to compute the primes to that number. You only need to the square root (if you don't find any divisors, then the number was prime)


I use the definition
_A number is prime if it cant be divided by any prime number less than or equal to its square root.
_2 is a prime number.

Because of memory ussage, instead of erasing the numbers that are not primes, insert the numbers that are.
So I start wiht a vector that has only the 2. Then test for modulo for every odd number against the numbers in the vector.
If it is a prime number, added to the vector and continue.

[ne555]

Project Euler wrote:

What is the value of the first triangle number to have over five hundred divisors?

		if (numdivisors ==500) 
		{
			cout<<"Found it! It is "<<Tn;
			found = true;
		}

[Darkenor]

Thanks, ne555 - that's great advice. I'm going to work on that tonight. I'll also change that to 501. :)

[Darkenor]

Thanks, all. As an update, I solved the problem by just finding all the primes up to 2000 and then running my finddivisors() function. The program finished in less than 2 seconds.

[Browni3141]

I didn't even know about project Euler untill this post showed up. I decided to take a look and I think I'll go for it. I started today and have six so far.