Comment résoudre le problème d'Euler 12?

Question

Possible en double:
Project Euler Problem 12 - C++

Je travaille sur les problèmes d'Euler et a heurté un mur avec le problème 12. Je lis sur des solutions mathématiques pour un grand nombre, mais je suis toujours pas la bonne réponse. Ceci est mon code:

#include <iostream> 
using namespace std; 

int divisorCount(const unsigned long long x) 
{ 
    int divizers = 0; 
    unsigned long long i = 1; 
    while(i <= x/i) 
    { 
     if(x % i == 0) 
     { 
      divizers++; 
     } 
     i++; 
    } 
    return divizers; 
} 

int main() 
{ 
    bool test; 
    unsigned long long total = 0, spread = 1; 
    int divisors = 1; 

    while(divisors < 501) 
    { 
     total+=spread; 
     divisors = divisorCount(total); 
     spread++; 
     if(divisors > 501) 
      cout << total << " " << spread << " " << divisors << endl; 
    } 


    cout << total << " is divisible by 500+ numbers" << endl; 
    system("pause"); 
    return 0; 
} 

Des suggestions?

Answer 1

il y a pour x ci-dessus diviseurs sqrt (x), donc corriger cela:

while(i <= x/i) 

à:

while(i <= x) 

aussi, faire spread++; après l'impression il indique le nombre correct.

Remarque: pour tester, il est préférable d'enlever le if avant l'impression pour voir ce qui se passe.

Note2: une façon beaucoup plus rapide de résoudre ce problème est de réaliser les propriétés de ces nombres, voir: triangular numbers. Le projet Euler est fortement basé sur les mathématiques, donc ne codez pas les solutions de force brute.

Answer 2

Pensez à votre déclaration if:

if(x % i == 0) 
{ 
    divizers++; 
} 

Depuis i est un facteur de x, quel autre facteur de x pouvez-vous écrire immédiatement vers le bas? Si 3 est un facteur de 24, quel autre facteur de 24 connaissez-vous? Il y a une prise cachée dans cet indice, juste pour que vous soyez au courant.