소인수 알고리즘: C, Python 예

소인수분해란 무엇입니까?

주어진 소인수 어떤 숫자는 다음과 같은 요소입니다. 소수. 인수를 곱하면 또 다른 숫자가 나옵니다. 소수는 그 자체로 나누어지거나 1로 나누어집니다.

즉, 소인수는 원래 숫자를 형성하기 위해 함께 곱해지는 소수를 찾아 결정됩니다.

: 10의 소인수는 2와 5입니다. 이는 2X5 =10이고 2,5가 모두 소수이기 때문입니다.

반복을 사용하여 소인수 찾기

주어진 숫자의 소인수를 찾으려면 먼저 2부터 숫자의 제곱근까지 모든 숫자를 반복한 다음 각 숫자가 소수인지 확인합니다. 원래 숫자가 이 소수로 나누어지는 한, 우리는 각 반복마다 이 소수를 계속 추가합니다.

예:

40보다 큰 모든 소수는 다음과 같이 기록됩니다.wing 공식: n2+n+41. 따라서 n을 모든 숫자로 대체하여 해당 소인수를 찾을 수 있습니다. 예: 02+0+41=41, 12+1+41=43, 22+2+41=47,…

숫자의 소인수를 인쇄하는 방법은 무엇입니까?

  • 이 방법에서는 이전 섹션에서 언급한 대로 2부터 숫자의 제곱근까지 숫자를 반복합니다.
  • 이를 위해 2부터 n의 제곱근까지 각 숫자의 원래 숫자의 모듈러스를 확인해야 합니다.
  • 그런 다음 n의 인수인 소수 목록을 찾습니다.
  • 이 해법은 O(Sqrt(n)) 시간에 있습니다.plexity.

연산:

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

체 알고리즘

체 방법은 숫자의 가장 작은 소인수를 저장하는 데 의존하므로 com.plex어떤 숫자에 대한 소인수를 계산할 때 눈에 띄게 나타납니다. Sieve 알고리즘은 모든 소인수를 다소 효율적으로 찾습니다.

  • 이 알고리즘의 주요 개념은 각 숫자의 가장 작은 소인수를 최대 숫자까지 저장하는 것입니다.
  • 주어진 각 숫자에 대해 가장 작은 소수를 가져와서 소인수 집합에 추가합니다.
  • 마지막으로, 이 소수로 나누고 1이 될 때까지 이 단계를 반복합니다.
  • 이 모든 작업은 O(log(n)) 시간 안에 완료됩니다.plex즉, 솔루션의 효율성이 크게 향상됩니다.
  • 이를 통해 이전 접근 방식을 사용하여 처리할 수 있었던 것보다 훨씬 더 큰 숫자의 소인수를 계산할 수 있습니다.

예:

두 번째 방법은 숫자가 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 소인수

여기, 우리는 쇼가 될 것이다wing 반복 방법으로 주어진 숫자의 소인수를 찾는 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 소인수

이 섹션에서는 다음의 코드를 보여줍니다. 파이썬 언어 체 방법을 사용하여 주어진 숫자의 소인수를 찾습니다.

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 소인수 프로그램

재귀를 사용한 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 외에 연속되는 소수가 없다는 것이다.
  • 또한 follo에는 2와 3을 제외한 모든 소수를 쓸 수 있습니다.wing 형식: 6 * n + 1 또는 6 * n – 1, 여기서 n은 양의 정수입니다.
  • 숫자의 소인수 집합은 고유한 집합입니다.
  • 1번은 소수도 아니고 합성수도 아닙니다.
  • 숫자의 소인수분해는 나눗셈, 분수 단순화, 다양한 분수의 공통 분모 찾기와 같은 문제를 해결하는 데 도움이 될 수 있습니다.
  • 또한 소인수분해의 흥미로운 용도 중 하나는 숫자 기반의 비밀 코드를 해독하는 것입니다.