반응형 순환고리1 26. 프로젝트 오일러 #26 : 순환고리 이번 문제는 가장 긴 순환고리를 찾는 문제입니다. 사실 순환고리는 오일러의 수 문제로 귀결됩니다. 오일러수는 다음과 같은 형태로 정의해서 낼 수 있습니다. 라고 한다면, 오일러의 수는 이라고 할 수 있습니다. 즉, n이 합성수라고 한다면, 오일러의 수는 엄청나게 줄어들게 됩니다. n이 소수라면 n-1 이 오일러의 수가 됩니다. 가장 긴 순환고리를 찾기 위해서는 사실 오일러의 수만 가지고 판단할 수는 없습니다. 10이란 숫자를 가지고 10이 n의 원시근이면 오일러의 수와 동일한 순환고리를 가지겠지만, 원시근이 아니라면, 오일러의 수의 약수 중 하나의 순환고리를 갖습니다. 일단 2의 배수와 5의 배수는 비순환고리를 가짐으로 실제 검사할 숫자들은입니다. 이 숫자 이외에는 비순환고리를 만듭니다. 예를 들어서 6.. 2015. 2. 27. 이전 1 다음 728x90