Program taking far too long

[georgep]

I'm stuck on Problem 12: http://projecteuler.net/problem=12 on projecteuler.net

The problem is to find the first triangle number to have more than 500 factors.

Here is my code:

#include<iostream>
#include<cstdlib>

using namespace std;
int main(){

unsigned a, number, divisor, factors, term=0;

    while(1){
       a = 0;
       number = 0;
             
          while(a <= term){ 
             number += a;
             a += 1;
          }                  //gets next triangle number
              
          divisor = 1;
          factors = 0;
            while(divisor <= number){                                  
                    
                 if(number % divisor == 0){                       
                    factors += 1;             //gets number of factors
                                                          
                    if(factors > 500){                            
                      cout << number << endl;    //displays number if it has more than 500 factors                                                                                                                           
                       system("pause>nul");
                       return 0;
                    } 
                 
                 } 
                 
             divisor += 1;
           }
                                        
      term += 1;
    }
return 0;
}

It takes ~10s for the first triangle number with 320 factors, but no higher.

I have left it for at least 1 hour with no output.

Please help me work out why, but ideally without just solving the whole problem.


Thanks!

[Athar]

Well... if a number p is evenly divisible by q, then it is also divisible by p/q.
So there's no need to test further than sqrt(p). With that change, the program gives me the result in less than a second.

[georgep]

Of course!

This worked for me, is this what you meant?

           ... while(divisor <= sqrt(number)){                                  
                    
                 if(number % divisor == 0){                       
                    factors += 2;             
                                                          
                    if(factors > 500){                            
                      cout << number << endl;                                                                                                                             
                       system("pause>nul");
                       return 0;
                    } ...
              

I don't know why I didn't think of that, thank you very much!

[Athar]

Yeah, that's what I meant. When number is a square number, factors should be one less
(because of p/q=q for q=sqrt(p)), but at least for this particular problem, it doesn't change the answer.

[Cninja]

I don't get this code
forgive me if i am wrong , i am a newbie .

  while(1) //infinite loop?
{
       a = 0;
       number = 0;
             
          while(a <= term)/* first loop[ 0<=0 , number += 0, a+=1 ]  2nd loop [ a (1)  <= term(0)  == false ; loop breaks] */
{ 
             number += a;
             a += 1;
          }    

the 'while' loop at the top keeps executing and nothing will ever stop it. You need a flag/counter? to change it when you have your required result other wise your other code will never execute.

you're also initializing 'a' to 0 both times first when you're declaring your variables and second time in the while loop .
Also 'factor' is already initialized to zero at line 7 , no need to have it again in 19.

I am in a rush so sorry if i can't help you out completely with your program.
best of luck.

[Athar]

the 'while' loop at the top keeps executing and nothing will ever stop it.

There's something that will: the return in line 28.

Also 'factor' is already initialized to zero at line 7 , no need to have it again in 19.

It's not initialized to anything, so it has an unspecified value.
It's true though that these variables (besides term) should have been declared later (when they are needed).

[Cninja]

@Athar
Yup you are correct athar.



Thank you .

[moorecm]

Just wait until problem 15! It's a hard one. I thought I had a clever recursive solution but it doesn't scale well enough, either. I'm pretty sure I know an algorithm that will work but I haven't had time to go back to it. I've been working on a Vim plugin for the past few days.

[JLBorges]

A composite number n can be decomposed as

n = p₀^i₀ + p₁^i₁ + p₂^i₂ + p₃^i₃ + p₄^i₄+ ...

where p₀, p₁, p₂, p₃, p₄ etc are the prime factors of n.

Simple combinatorics would show that the number of divisors of n is given by:
( i₀ + 1 ) * ( i₁ + 1 ) * ( i₂ + 1 ) * ( i₃ + 1 ) * ( i₄ + 1 ) * ...

Exploiting this:

#include <vector>
#include <iostream>

// generate prime numbers <= n
std::vector<int> generate_primes( int n )
{
    std::vector<bool>sieve( n, true ) ;
    for( std::size_t i = 2 ; i < sieve.size() ; ++i ) if( sieve[i] )
          for( auto j = i*i ; j < sieve.size() ; j += i ) sieve[j] = false ;

    std::vector<int> primes ;
    for( std::size_t i = 2 ; i < sieve.size() ; ++i )
        if( sieve[i] ) primes.push_back(i) ;
    return primes ;
}

// number of factors of triangular number 1+2+3+...+n
int num_factors( long long n )
{
    enum { MAX_PRIME = 1024*1024 } ;
    static const auto primes = generate_primes(MAX_PRIME) ;
    static const double root2 = 1.4142135623730951 ;

    long long number = n * (n+1) / 2 ; // triangular number 1+2+3+...+n
    const int root = (n+1) / root2 + 1 ; // upper bound on square root of number

    int num_factors = 1 ;
    for( auto i : primes )
        if( i > root ) break ;
        else
        {
            int power = 0 ;
            while( number%i == 0 ) { ++power ; number /= i ; }
            num_factors *= (power+1) ;
        }

    return num_factors != 1 ? num_factors : 2 ;
}

int main()
{
    enum { REQUIRED = 500 } ;
    long long n = 1 ;
    int nfactors_found ;
    while( ( nfactors_found = num_factors(n) ) < REQUIRED ) ++n ;
    std::cout << "n == " << n << "  triangular number == " << n * (n+1) / 2
              << "  nfactors == " << nfactors_found << '\n' ;
}