소인수 알고리즘: C, Python 예시
사라 첸
소인수분해란 무엇입니까?
주어진 소인수 어떤 숫자는 다음과 같은 요소입니다. 소수. 인수를 곱하면 또 다른 숫자가 나옵니다. 소수는 그 자체로 나누어지거나 1로 나누어집니다.
즉, 소인수는 어떤 소수가 서로 곱해져 원래 숫자를 형성하는지를 찾아 결정됩니다.
예시: 10의 소인수는 2와 5입니다. 2X5 = 10이고 2,5, XNUMX는 모두 소수이기 때문입니다.
반복을 사용하여 소인수 찾기
주어진 숫자의 소인수를 구하려면 먼저 2부터 숫자의 제곱근까지 모든 숫자를 반복한 다음 각 숫자가 소수인지 확인합니다. 원래 숫자가 이 소수로 나누어지는 한, 반복할 때마다 이 소수를 계속 추가합니다.
예:
40보다 큰 모든 소수는 다음 공식으로 표현됩니다: n2+n+41. 따라서 n을 모든 숫자로 대체하여 해당 소인수를 찾을 수 있습니다. 예: 02+0+41=41, 12+1+41=43, 22+2+41=47,…
숫자의 소인수를 인쇄하는 방법은 무엇입니까?
- 이 방법에서는 이전 섹션에서 언급한 대로 2부터 숫자의 제곱근까지 숫자를 반복합니다.
- 그러기 위해서는 2부터 n의 제곱근까지의 각 숫자에 대한 원래 숫자의 모듈러스를 확인해야 합니다.
- 그런 다음 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)) 시간 복잡도로 수행되어 솔루션의 효율성이 크게 향상됩니다.
- 이를 통해 이전 접근방식을 사용해서 처리할 수 있었던 것보다 훨씬 큰 숫자의 소인수를 계산하는 것이 가능해졌습니다.
예:
두 번째 방법은 숫자가 6n-1 또는 6n+1로 쓰여질 수 있는지 확인하는 것입니다. 2와 3 이외의 소수는 두 수식 중 하나로 쓰여야 하기 때문입니다. 예: 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 4
Python 재귀를 사용한 소인수
이 섹션에서는 다음의 코드를 보여줍니다. Python 언어 체 방법을 사용하여 주어진 숫자의 소인수를 찾습니다.
import math
High = (int)(1e5+7)
array=[0 for i in range(High)]
# function to generate all the smallest prime
def Sieve():
#factors of the numbers until the maximum number
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):
#We will keep dividing until we reach 1
if n == 1:
return
print((int)(array[n]))
PrimeFactors((int)(n/array[n]))
#Here we call the function after dividing it by this prime
Sieve()
n=(int)(input("Enter the number you want: "))
PrimeFactors(n)
출력:
Enter the number you want: 4 2 2
반복을 사용한 C 소인수 프로그램
반복적 Python 솔루션과 동일한 솔루션이지만 다음으로 작성되었습니다. C 언어.
사용자에게 숫자를 입력하도록 요청한 다음 2부터 이 숫자의 제곱근까지의 각 숫자에 대해 이 요소가 나타나는 모든 항목을 인쇄하여 나눌 수 있는지 확인해야 합니다.
#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 소인수 프로그램
이것은 Python 재귀 솔루션과 동일한 솔루션이지만 C로 작성되었습니다.
사용자에게 번호를 입력하도록 요청할 수 있습니다. 그런 다음 각 숫자의 가장 작은 소인수를 저장하는 소수 배열을 만듭니다. 마지막으로 주어진 숫자를 가장 작은 소인수로 나누고 XNUMX에 도달할 때까지 자신을 호출하는 소인수 재귀 함수를 호출합니다.
#include <stdio.h>
int Max = 100007;
int array[100007];
void Sieve()//helping function to generate all the smallest //prime factors of the numbers until the maximum number
{
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)//keep dividing until we reach 1
{
return;
}
printf("%d\n",array[n]);
PrimeFactors(n/array[n]);//call the function after dividing by //this prime
}
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을 제외한 모든 소수는 다음과 같은 형태로 쓸 수 있습니다: 6 * n + 1 또는 6 * n – 1, 여기서 n은 양의 정수입니다.
- 숫자의 소인수 집합은 고유한 집합입니다.
- 1번은 소수도 아니고 합성수도 아닙니다.
- 숫자의 소인수분해는 나누어 떨어지는 문제, 분수를 단순화하는 문제, 다양한 분수의 공통 분모를 찾는 문제와 같은 문제를 해결하는 데 도움이 될 수 있습니다.
- 또한 소인수분해의 흥미로운 용도 중 하나는 숫자 기반의 비밀 코드를 해독하는 것입니다.
