내 코드가 실행되지 않는 이유는 무엇입니까?

Question

프로젝트 오일러에서 Problem #5을 해결하려고합니다. 이 코드는 예제에서 작동합니다. 1에서 10까지의 숫자를 확인하면 결과적으로 2520이됩니다. 그러나 1에서 20까지의 숫자를 확인할 때 코드가 실행되는 것을 멈추지 않습니다.

여기입니다

num = 0 

while true 

    num += 1 
    check = true 

    for i in 1..20 

     break unless check 

     check = num%i==0 

    end 

    break if check 

end 

File.open("__RESULT__.txt", "w+").write num 

Answer 1

이 문제에 대한 솔루션은 단지 모든 가능한 솔루션을 계산함으로써 발견 될 수 없다. 해결책은 너무 커서 계산하는 데 며칠 (아마도 몇 년)이 걸릴 것입니다.

소수를 사용하여 숫자를 적어 놓는 똑똑한 해결책이 있습니다.

주어진 예 이렇게 적어 수 (2520 번호 10 내지 1 divisable 가장 작은 번호) :

1 = 1 (can be skipped) = 2^0 * 3^0 * 5^0 * 7^0 
2 = 2 (prime)   = 2^1 * 3^0 * 5^0 * 7^0 
3 = 3 (prime)   = 2^0 * 3^1 * 5^0 * 7^0 
4 = 2^2     = 2^2 * 3^0 * 5^0 * 7^0 
5 = 5 (prime)   = 2^0 * 3^0 * 5^1 * 7^0 
6 = 2 * 3    = 2^1 * 3^1 * 5^0 * 7^0 
7 = 7 (prime)   = 2^0 * 3^0 * 5^0 * 7^1 
8 = 2^3     = 2^3 * 3^0 * 5^0 * 7^0 
9 = 3^2     = 2^0 * 3^2 * 5^0 * 7^0 
10= 2 * 5    = 2^1 * 3^0 * 5^1 * 7^0 

이제 다음에 의해 나누어 질 수있는 최소 숫자

동일한 번호가 ON (심지어 수동으로) 수행 될 수

2^3 * 3^2 * 5^1 * 7^1 = 2520 

1~20

통해 각 프라임에서 사용되는 최대 전력을 사용하여 계산 될 수있다 마지막 힌트 : 대답은 억이 100.000.000보다 큰 미만이기 때문에 효율적으로 수행하는 경우가 이분에서 계산 될 수있다

Answer 2

문제는 본질적으로 처음 20 수의 LCM을 찾을 수 있도록 요청합니다. ..

lcm = 1 
for i = 2 to 20 
    lcm = (i * lcm)/gcd(lcm,i) 

Answer 3

훨씬 간단한 해결책은 알고리즘을 사용하는 것이지만 1이 아닌 2520 씩 증가시키는 것입니다. 여기서 내 C++ 솔루션입니다. 위에서 볼 수 있듯이

#include <iostream> 
using namespace std; 

int main() 
{ 
    int check = 2520; 
    int i = 11; 
    while (i != 20) 
    { 
     i ++; 
     if (check % i != 0) 
     { 
      check +=2520; 
      i = 1; 
     } 
    } 
    cout << check << endl; 
    return 0; 
} 

, 나는 또한 번호 2520에서 시작, 우리가 문제의 필요한 정보를 제공 한 것처럼 우리는 이러한 최적화를 할 수 있습니다 (11)을 동일하게 난을 설정합니다.