The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
#include <stdio.h>
int main(int argc, char* argv[])
{
long long number = 600851475143;
int i;
for(i=2; i<=number; i++)
{
if(number % i == 0)
{
number = number / i;
}
}
printf("%d",i-1);
return 0;
}
접근 방법
1. number가 나누어지는 수 즉 인수를 반복문을 통해 찾는다.
2. 이 때 인수가 소인수인지 어떻게 알수있나?
3. 만약 소인수가 아니였다면 더 작은 i에서 나누어 떨어졌을 것.
'Computer Science > Algorithm' 카테고리의 다른 글
[Algorithm/C] Project Euler. Largest palindrome product (0) | 2017.12.05 |
---|---|
[Algorithm/C] Project Euler. Smallest multiple (0) | 2017.12.04 |
[Algorithm/C] Project Euler. Even Fibonacci Numbers (0) | 2017.11.29 |
[Algorithm/C] Zig-Zag 배열 만들기 (0) | 2017.11.28 |
[Algorithm/C] Project Euler. Multiple of 3 and 5 (0) | 2017.11.27 |