3. 가장 큰 소인수 찾기

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

13195의 소인수는 5, 7, 13, 29다.

600851475143의 가장 큰 소인수는 무엇인가?

소수 판단 알고리즘처럼 600851475143의 제곱근에서 수를 감소하며 소인수인지 확인하면 됩니다.

가장 큰 소인수가 2일 리는 없으니 홀수만 검사합니다.

#include <stdio.h> #include <math.h> int is_prime(int n) { int i, sqrn; sqrn = (int)sqrt(n); for (i = 2; i <= sqrn; i++) if (n % i == 0) return 0; return 1; } int main() { int a=sqrt(600851475143); if((a&1) == 0) //짝수면 1을 빼 홀수로 a--; while(a-=2) //홀수만 확인합니다 { if( (600851475143 % a) == 0 && is_prime(a)) break; } printf("%d", a); }

BLUEnLIVE님께서 지적해주셔서 만든 소스

#include <stdio.h> #include <math.h> int is_prime(int n) { int i, sqrn; sqrn = (int)sqrt(n); for (i = 2; i <= sqrn; i++) if (n % i == 0) return 0; return 1; } int main() { int a=sqrt(600851475143); if((a&1) == 0) //짝수면 1을 빼 홀수로 a--; do { if( (600851475143 % a) == 0 && is_prime(a)) break; }while(a-=2) //홀수만 확인합니다 printf("%d", a); }