Ruby. 숫자 범위의 최소 배수를 검색하는 루프를 향상시키는 방법

Question

이 작업을 처리해야합니다.

"2520은 아무 것도 지정하지 않고 1에서 10까지의 각 숫자로 나눌 수있는 최소 숫자입니다. 나머지 숫자. 1에서 20까지의 모든 숫자로 균등하게 나눌 수있는 가장 작은 양수는 얼마입니까? "

내 솔루션은 다음과 같습니다

all_numbers = [] 

1.upto(2600) do |j| 
    1.upto(10) do |i| 
      if j % i == 0 
       all_numbers << j 
       end 
    end 
end 

result = all_numbers.select{|element| all_numbers.count(element) > 9 } 
p result[0] 

이 나에게 정답을 제공하지만, 내가 0..20의 범위를 확인하고이 같은 코드를 변경하려면 :

all_numbers = [] 

1.upto(100000) do |j| 
    1.upto(20) do |i| 
      if j % i == 0 
       all_numbers << j 
       end 
    end 
end 

result = all_numbers.select{|element| all_numbers.count(element) > 19 } 
p result[0] 

이 걸리는 답변을 받기에는 너무 많은 시간이 필요합니다. (실제로, 나는 너무 오래 기다리지도 않았지만 ... 아직 정답이 없습니다.).

아이디어가 있으십니까? 많은 감사합니다!

Answer 1

잘못된 각도에서 공격하고 있습니다. 올바른 번호를 찾을 때까지 검색하는 대신 번호를 계산할 수 있습니다. 기본적으로 결과가 나눌 수있는 모든 숫자를 살펴보고, 주요 요인을 찾은 다음 각 소수의 가장 큰 힘을 사용하는 것을 의미합니다. 예를 들어, 숫자 1-6으로 나누어 첫 번째 번호를 찾는 것은 다음과 같이 될 것이다 :

1: ignore 
2: prime factors 2**1 
3: prime factors 3**1 
4: prime factors 2**2 
5: prime factors 5**1 
6: prime factors 2**1, 3**1 

그래서, 당신의 유일한 소수는 2, 3, 5 (2) 제곱이며, 다른 모든이다 첫 번째 권력. 그 모두 함께 곱하면, 당신이 당신의 1-10 사건에 대한 조그마한 조금 더 복용 2 * 2 * 3 * 5 인 (60)을 얻을, 우리는이 :

7: prime factors 7**1 
8: prime factors 2**3 
9: prime factors 3**2 
10: prime factors 2**1, 5**1 

를 이제 고유 한 소수를 자신의 최대 전력은 2**3, 3**2, 5**1, 7**1 2 * 2 * 3 * 3 * 5 * 7을 곱하면 2520이됩니다. 이미 알고 계셨습니까? 이 접근 방법을 1-20의 숫자에 사용하면 각 번호에가는 것보다 훨씬 빨리 결과를 얻을 수 있습니다.

Ruby는 소수를 사용하도록 허용 된 경우 소수 라이브러리 (HW 할당이라고 가정)를 가지고 있습니다. 특히 prime_division 메소드는 기본적으로이 특별한 문제에 대해 매우 유용한 방법으로 프라임 인수를 반환합니다.