Project Euler Problem5
2015. 2. 12. 02:09ㆍ프로그래밍/알고리즘
728x90
728x90
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. 최대 제곱수로 계산.
728x90
반응형
'프로그래밍 > 알고리즘' 카테고리의 다른 글
Project Euler Problem16 (0) | 2015.02.24 |
---|---|
Project Euler Problem15 (0) | 2015.02.17 |
Project Euler Problem10 (0) | 2015.02.15 |
Project Euler Problem9 (0) | 2015.02.15 |
Project Euler Problem7 (0) | 2015.02.05 |
Project Euler Problem6 (0) | 2015.02.05 |
Project Euler Problem4 (0) | 2015.01.25 |