Python에서 소인수 찾기
질문:
두 부분으로 구성된 질문:
코드 예:
<code class="python">n = 600851475143 i = 2 while i * i < n: while n % i == 0: n = n / i i = i + 1 print(n)</code>
정답:
1. 알고리즘 작동 방식:
주어진 알고리즘은 2부터 주어진 숫자 n의 제곱근까지 모든 숫자를 반복하여 가장 큰 소인수를 찾기 위해 무차별 대입을 사용합니다. 각 숫자 i에 대해 n을 나머지 없이 나누는지 확인합니다. 만약 그렇다면, n이 더 이상 i로 나누어지지 않을 때까지 n을 i로 반복해서 나눕니다. 그런 다음 i를 1씩 증가시키고 프로세스를 계속합니다. 가장 큰 소인수는 n의 최종 값이 됩니다.
2. 알고리즘이 더 빠른 이유:
주어진 알고리즘은 숫자의 소인수가 제곱근보다 작거나 같다는 사실을 활용하기 때문에 단순히 모든 숫자를 테스트하는 것보다 빠릅니다. n의 제곱근까지만 반복함으로써 알고리즘은 확인할 잠재적 후보 수를 줄여 효율성을 크게 향상시킵니다.
향상된 알고리즘:
제공되는 코드 예제에는 모든 경우에 가장 큰 소인수를 올바르게 찾지 못하게 하는 몇 가지 문제가 있습니다. 알고리즘의 수정된 버전은 다음과 같습니다.
<code class="python">def largest_prime_factor(n): i = 2 while i * i <= n: if n % i == 0: n //= i else: i += 1 return n</code>
이 알고리즘은 완전제곱수와 소인수가 반복되는 숫자의 경우에도 가장 큰 소인수를 정확하게 찾습니다.
위 내용은 무차별 대입 알고리즘은 숫자의 가장 큰 소인수를 어떻게 찾고, 모든 숫자를 테스트하는 것보다 빠른 이유는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!