Project Euler Problem5

Problem5.

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

나의 풀이)

알고리즘은 소수의 최대제곱을 찾으면 되는 것이다.

특히 2와 3의 값이 중요한데

5부터는 어차피 2개 이상 가지고 있는 수는 25를 넘어가버리므로

5,7,11,13,17,19는 확정으로 곱해진다.

2의 배수 중 20이하의 수를 구하면 16 = 2^4

3의 배수 중 20이하의 수는 9 = 3^2

이므로 이를 모두 곱하면 답이 된다.

1. 20이하의 모든 소수 찾기.

2. 소수의 제곱수가 20 이하에 존재하는지 확인.

3. 최대 제곱수로 계산.