Algorytm czynnika pierwszego: C, Python Przykład

Co to jest faktoryzacja pierwsza?

Czynnik pierwszy danego każdy liczba jest czynnikiem, który jest a Liczba pierwsza. Czynniki pomnożone dają inną liczbę. Liczba pierwsza jest podzielna przez samą siebie lub przez 1.

Innymi słowy, czynniki pierwsze określa się poprzez znalezienie liczb pierwszych, które pomnożone przez siebie tworzą liczbę początkową.

Przykład:Czynnikami pierwszymi liczby 10 są 2 i 5. Wynika to z faktu, że 2X5 = 10, a obie liczby 2,5 i XNUMX są liczbami pierwszymi.

Znajdowanie czynników pierwszych za pomocą iteracji

Aby znaleźć czynniki pierwsze danej liczby, najpierw iterujemy po wszystkich liczbach od 2 do pierwiastka kwadratowego liczby, a następnie sprawdzamy, czy każda liczba jest pierwsza. Dopóki pierwotna liczba jest podzielna przez tę liczbę pierwszą, dodajemy tę liczbę pierwszą z każdą iteracją.

Przykład:

Każdą liczbę pierwszą większą od 40 zapisuje się następującym wzorem: n²+n+41. Możemy więc podstawić n za wszystkie liczby, aby znaleźć odpowiadający im czynnik pierwszy, np. 0²+0+41=41, 1²+1+41=43, 2²+2+41=47,…

Jak wydrukować czynnik pierwszy liczby?

• W tej metodzie będziemy iterować po liczbach od 2 aż do pierwiastka kwadratowego liczby, jak wspomniano w poprzedniej sekcji.
• W tym celu musimy sprawdzić moduł oryginalnej liczby dla każdej z liczb od 2 do pierwiastka kwadratowego z n.
• Następnie znajdujemy listę liczb pierwszych, które są czynnikami n.
• To rozwiązanie ma złożoność czasową O(Sqrt(n)).

Algorytm:

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

Algorytm sita

Metoda sita polega na przechowywaniu najmniejszego czynnika pierwszego liczby, co zauważalnie zmniejsza złożoność podczas obliczania czynników pierwszych dla dowolnej liczby. Algorytm sita znajduje wszystkie czynniki pierwsze w miarę wydajnie.

• Główną koncepcją tego algorytmu jest przechowywanie najmniejszego czynnika pierwszego każdej liczby aż do uzyskania maksymalnej liczby.
• Dla każdej podanej liczby bierzemy najmniejszą liczbę pierwszą i dodajemy ją do zbioru czynników pierwszych.
• Na koniec dzielimy przez tę liczbę pierwszą i powtarzamy te kroki, aż dotrzemy do 1.
• Wszystko to odbywa się przy złożoności czasowej O(log(n)), co znacznie zwiększa wydajność rozwiązania.
• Dzięki temu możliwe jest obliczenie czynników pierwszych znacznie większych liczb, niż te, z którymi moglibyśmy mieć do czynienia, stosując poprzednie podejście.

Przykład:

Drugi sposób polega na sprawdzeniu, czy liczbę można zapisać jako 6n-1 lub 6n+1, gdyż dowolną liczbę pierwszą inną niż 2 i 3 należy zapisać w jednym z dwóch wzorów. np. 5=6(1)-1, 19=6(3)+1,… .

Algorytm:

Zdefiniuj tablicę tablicową do przechowywania najmniejszego czynnika pierwszego każdej liczby z wartością indeksu jako wartością początkową dla każdego elementu szyk.

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 Czynniki pierwsze przy użyciu iteracji

Tutaj pokażemy kod w Python język do znajdowania czynników pierwszych danej liczby metodą iteracyjną:

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)

Wyjście:

Enter the number you want: 4
4

Python Czynniki pierwsze przy użyciu rekurencji

Ta sekcja pokazuje kod w Python język stosując metodę sitową do znalezienia czynników pierwszych danej liczby.

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)

Wyjście:

Enter the number you want: 4
2
2

Program czynników pierwszych w C przy użyciu iteracji

Jest to to samo rozwiązanie, co iteracyjne rozwiązanie w Pythonie, ale zapisane Język C..

Prosimy użytkownika o podanie liczby, następnie dla każdej liczby od 2 do pierwiastka kwadratowego tej liczby sprawdzamy, czy jest ona podzielna, wypisując wszystkie wystąpienia tego współczynnika.

#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;
}

Wyjście:

Enter the number you want: 2
2

Program czynników pierwszych w C przy użyciu rekurencji

Jest to to samo rozwiązanie, co rozwiązanie rekurencyjne w Pythonie, ale napisane w C.

Możemy poprosić użytkownika o podanie numeru; następnie budujemy tablicę liczb pierwszych, która przechowuje najmniejszy czynnik pierwszy każdej liczby. Na koniec nazywamy funkcję rekurencyjną Czynniki Pierwsze, która dzieli daną liczbę przez jej najmniejszy czynnik pierwszy i przypomina sobie, aż osiągnie jeden.

#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;
}

Wyjście:

Enter the number you want: 2
2

Kilka interesujących faktów na temat liczb pierwszych

• Jednym z najciekawszych faktów jest to, że każda liczba parzysta inna niż 2 może być sumą dwóch liczb pierwszych.
• Na przykład: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3… itd.
• Innym faktem jest to, że nie ma kolejnych liczb pierwszych innych niż 2 i 3, ponieważ jedyną parzystą liczbą pierwszą jest liczba 2.
• Ponadto wszystkie liczby pierwsze, z wyjątkiem 2 i 3, można zapisać w następującej postaci: 6 * n + 1 lub 6 * n – 1, gdzie n jest liczbą całkowitą dodatnią.
• Zbiór czynników pierwszych liczby jest unikalny.
• Liczba 1 nie jest ani liczbą pierwszą, ani złożoną.
• Rozkład liczb na czynniki pierwsze może pomóc w rozwiązywaniu problemów, takich jak podzielność, upraszczanie ułamków i znajdowanie wspólnych mianowników różnych ułamków.
• Ponadto jednym z ekscytujących zastosowań rozkładu na czynniki pierwsze jest łamanie tajnych kodów opartych na liczbach.