소인수 알고리즘: C, Python 예시
편집 팀
소인수분해란 무엇입니까?
어떤 수의 소인수는 그 자체가 1인 수입니다. 소수1과 자기 자신으로만 나누어떨어집니다.
예: 10의 소인수는 2와 5입니다. 왜냐하면 2 × 5 = 10이기 때문입니다.
반복을 사용하여 소인수 찾기
2부터 sqrt(n)까지 반복하면서 나누어 떨어지는지 확인합니다. n이 현재 후보로 나누어 떨어지는 동안에는 나누고 결과를 출력합니다.
예: 40보다 큰 모든 소수는 n에 적합합니다.2+n+41이므로 n = 0, 1, 2일 때 결과는 41, 43, 47입니다.
숫자의 소인수를 인쇄하는 방법은 무엇입니까?
- 2부터 sqrt(n)까지 숫자를 반복합니다.
- 각 후보에 대해 n의 나머지를 확인하십시오. 나머지가 0이면 해당 후보는 소인수입니다.
- n을 나누는 모든 소수를 모으세요.
- 이 루틴은 O(sqrt(n)) 시간 복잡도로 실행됩니다.
연산:
Set a counter i to 2 While i <= sqrt(n): While n % i == 0: n = n / i print i i = i + 1 if n > 1: print n
체 알고리즘
체 방법은 최대값까지 모든 수의 가장 작은 소인수를 저장하여 사전 계산 후 소인수 분해 비용을 크게 줄입니다.
- 최대값까지 모든 정수의 가장 작은 소인수를 기록하세요.
- 가장 작은 소수를 골라서 인수 집합에 추가하세요.
- 그 수를 해당 소수로 나누고, 결과가 1이 될 때까지 이 과정을 반복합니다.
- 각 쿼리는 대략 O(log n)의 시간 복잡도로 실행됩니다.
예: 2와 3 이외의 소수는 6n-1 또는 6n+1의 형태를 갖습니다. 예를 들어 5 = 6(1)-1이고 19 = 6(3)+1입니다.
연산: 정의하다 정렬 각 숫자의 가장 작은 소인수를 저장하며, 인덱스를 각 요소의 초기값으로 사용합니다.
Set array[1] to 1 Set i to 2 While i*i <= max_number: If array[i] == i: Set j to i*i While j <= max_number: If array[j] == j: array[j] = i j = j + i i = i + 1 while the_number != 1: print array[the_number] the_number = the_number / array[the_number]
관련 기사
Python 반복을 사용한 소인수
다음 Python 이 코드는 반복적인 나눗셈 방법을 사용하여 소인수를 찾습니다.
import math def PrimeFactors(n): for i in range(2, int(math.sqrt(n)) + 1, 1): while n % i == 0: # find all the occurrences of a prime factor print((int)(i)) n = n // i if n != 1: # if the number was originally a prime print((int)(n)) n = (int)(input("Enter the number you want: ")) PrimeFactors(n)
출력:
Enter the number you want: 4 2 2
Python 재귀를 사용한 소인수
The Python 아래 코드는 체법을 사용하여 주어진 숫자의 소인수를 찾습니다.
import math High = (int)(1e5 + 7) array = [0 for i in range(High)] # generate smallest prime factors def Sieve(): for i in range(1, High): array[i] = i for i in range(2, math.ceil(math.sqrt(High))): if array[i] == i: for j in range(i * i, High, i): if array[j] == j: array[j] = i def PrimeFactors(n): # divide until we reach 1 if n == 1: return print((int)(array[n])) PrimeFactors((int)(n / array[n])) Sieve() n = (int)(input("Enter the number you want: ")) PrimeFactors(n)
출력:
Enter the number you want: 4 2 2
반복을 사용한 C 소인수 프로그램
동일한 반복 솔루션이 작성되었습니다. C숫자를 입력한 다음 2부터 sqrt(n)까지의 각 후보에 대해 나누어 떨어지는지 확인하고 소인수가 나타나는 모든 위치를 출력합니다.
#include <stdio.h> int main() { int n; printf("Enter the number you want: "); scanf("%d", &n); for (int i = 2; i * i <= n; i++) { while (n % i == 0) // find all the occurrences of a prime factor { printf("%d\n", i); n /= i; } } if (n != 1) // if the number was originally a prime { printf("%d", n); } return 0; }
출력:
Enter the number you want: 2 2
재귀를 사용한 C 소인수 프로그램
재귀적인 C 버전은 다음을 반영합니다. Python 첫 번째 단계는 가장 작은 소인수들의 배열을 만드는 것입니다. 그런 다음 n이 1이 될 때까지 해당 소인수로 나누는 과정을 재귀적으로 수행합니다.
#include <stdio.h> int Max = 100007; int array[100007]; void Sieve() // smallest prime factors up to Max { for (int i = 1; i < Max; i++) array[i] = i; for (int i = 2; i * i <= Max; i++) { if (array[i] == i) { for (int j = i * i; j < Max; j += i) { if (array[j] == j) array[j] = i; } } } } void PrimeFactors(int n) { if (n == 1) // divide until we reach 1 return; printf("%d\n", array[n]); PrimeFactors(n / array[n]); } int main() { Sieve(); int n; printf("Enter the number you want: "); scanf("%d", &n); PrimeFactors(n); return 0; }
출력:
Enter the number you want: 2 2
소수에 대한 몇 가지 흥미로운 사실
- 2를 제외한 모든 짝수는 두 소수의 합으로 나타낼 수 있습니다 (4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3).
- 2와 3을 제외하고는 연속된 소수가 없습니다. 왜냐하면 2가 유일한 짝수 소수이기 때문입니다.
- 2와 3을 제외한 모든 소수는 n이 양의 정수일 때 6n + 1 또는 6n − 1의 형태를 갖습니다.
- 어떤 수의 소인수 집합은 유일하다.
- 숫자 1은 소수도 아니고 합성수도 아닙니다.
- 소인수분해는 나누어떨어짐 여부 확인, 분수 간소화, 공통분모 찾기에 도움이 됩니다.
- 소인수분해는 숫자 기반 암호화 코드의 기본 원리이기도 합니다.
