소인수2 [C/C++] 프로젝트 오일러 #47 : 서로 다른 소인수 프로젝트 오일러 #47 문제는 소인수 분해를 하기만 하면, 어렵지 않게 풀 수 있습니다.난이도는 5%입니다. Project Euler 47번 문제는 서로 다른 소인수를 가지는 연속된 자연수를 찾는 문제입니다. 이 문제의 핵심은 연속된 네 개의 자연수가 각각 네 개의 서로 다른 소인수를 가져야 한다는 점입니다. 이러한 조건을 만족하는 가장 작은 자연수를 찾는 것이 목표입니다.자연수는 소인수 분해를 통해 어떤 소수들의 곱으로 이루어져 있는지를 확인할 수 있습니다. 예를 들어, 14는 2와 7로 이루어져 있으며, 15는 3과 5로 이루어져 있습니다. 이러한 방식으로 각 숫자의 소인수를 분석하면서 연속된 숫자들이 일정 개수의 서로 다른 소인수를 가지는지를 검사하면 해결할 수 있습니다.예를 들어, 만약 문제에.. 2016. 6. 1. #3 : 가장 큰 소인수 찾기 이번 문제는 주어진 수에 대해서 가장 큰 소인수를 찾는 프로그램입니다. 사실 에라스토테네스의 체를 이용하여 가장 큰 소인수를 찾을 수밖에 없습니다. 일단 필요한 것은 주어진 수를 계속 나누기 하는 것입니다. 프로그램 역시 이 범주를 벗어나지 않습니다. 조금 속도를 빠르게 하기 위해서는 소수의 일반적인 형태, 2를 제외한 모든 소수는 홀수이다. 홀수 소인수는 6k+1, 6k+5를 가진다 등을 이용해서 시도횟수를 줄일 수는 있습니다. 이번에는 더 효율적인 알고리즘을 찾기 위한 방법은 별로 없어보이네요. 간단하게 프로그램을 짜보면 다음과 같습니다. int main() { int p = 3; int64 n = 600851475143; while( n%2 == 0 ) n /= 2; if( n == 1 ) { pr.. 2014. 12. 19. 이전 1 다음 728x90
