Name: Anonymous 2008-11-15 23:13
I'm working on Euler problem number 12. I've got the following:
The problem is, NumDivisors is horribly inefficient. I mean 30 minutes at 2.5ghz and I'm only on num=9219 with a maxdiv of 478. Any suggestions?
//cut out my includes
bool IsPrime(int num)
{
bool prime = true;
int number2 =(int) floor (sqrt ((long double)num));
for ( int j = 2; j <= number2; j++){
if ( num!=j && num % j == 0 ){
prime = false;
break;
}
}
return prime;
}
int NumDivisors(__int64 num)
{
int count = 0;
if(!IsPrime(num))
{
__int64 number2 = num/2;
for ( __int64 j = 2; j <= number2; j++){
if ( num % j == 0 ){
count++;
}
}
}
return count;
}
int _tmain(int argc, _TCHAR* argv[])
{
bool found = false;
__int64 num = 1;
__int64 maxdiv = 0;
while(!found)
{
__int64 trinum = 0;
for(int i = 0;i<=num;++i) trinum += i;
int div = NumDivisors(trinum);
if(div>maxdiv) maxdiv = div;
if(div>500) found = true;
if(!found) ++num;
}
return 0;
}The problem is, NumDivisors is horribly inefficient. I mean 30 minutes at 2.5ghz and I'm only on num=9219 with a maxdiv of 478. Any suggestions?