Alkutekijän algoritmi: C, Python esimerkki

Mikä on ensisijainen faktorointi?

Tiedon alkutekijä Kaikki numero on tekijä, joka on a alkuluku. Kertomalla kertoimet antavat sinulle toisen luvun. Alkuluku on jaollinen itsellään tai 1:llä.

Toisin sanoen alkutekijät määritetään etsimällä, mitkä alkuluvut kertovat yhdessä muodostaen alkuperäisen luvun.

esimerkki: 10:n alkutekijät ovat 2 ja 5. Tämä johtuu siitä, että 2X5 =10 ja molemmat 2,5 ovat alkulukuja.

Ensisijaisten tekijöiden löytäminen iteraatiolla

Tietyn luvun alkutekijöiden löytämiseksi iteroimme ensin kaikki luvut luvusta 2 luvun neliöjuureen ja tarkistamme sitten, ovatko jokainen luku alkuluku. Niin kauan kuin alkuperäinen luku on jaettavissa tällä alkuluvulla, lisäämme tämän alkuluvun jokaisen iteroinnin yhteydessä.

Esimerkiksi:

Jokainen alkuluku, joka on suurempi kuin 40, kirjoitetaan seuraavaan kaavaan: n²+n+41. Voimme siis korvata n:n kaikilla luvuilla löytääksemme vastaavan alkutekijän. esim 0²+0+41=41, 1²+1+41=43, 2²+2+41=47,…

Kuinka tulostaa luvun alkutekijä?

• Tässä menetelmässä toistamme numeroita 2:sta luvun neliöjuureen, kuten edellisessä osiossa mainittiin.
• Tätä varten meidän on tarkistettava alkuperäisen luvun moduuli jokaisessa luvussa 2:sta n:n neliöjuureen.
• Sitten löydämme luettelon alkuluvuista, jotka ovat n:n tekijöitä.
• Tämä ratkaisu on O(Sqrt(n))-aikakompleksisuudessa.

algoritmi:

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

Seula-algoritmi

Seulamenetelmä perustuu lukujen pienimmän alkutekijän tallentamiseen, mikä vähentää monimutkaisuutta huomattavasti laskettaessa minkä tahansa luvun alkutekijöitä. Seula-algoritmi löytää kaikki alkutekijät jokseenkin tehokkaasti.

• Tämän algoritmin pääkonsepti on tallentaa kunkin luvun pienin alkutekijä maksiminumeroon asti.
• Otetaan pienin alkuluku jokaiselle annetulle luvulle ja lisätään se alkutekijöiden joukkoon.
• Lopuksi jaamme tällä alkuluvulla ja toistamme näitä vaiheita, kunnes saavutamme luvun 1.
• Tämä kaikki tehdään O(log(n))-aikakompleksisuudessa, mikä parantaa ratkaisun tehokkuutta huomattavasti.
• Tämä mahdollistaa paljon suurempien lukujen alkutekijöiden laskemisen kuin ne, joita olisimme voineet käsitellä edellisellä lähestymistavalla.

Esimerkiksi:

Toinen tapa on tarkistaa, voidaanko luku kirjoittaa muodossa 6n-1 tai 6n+1, koska mikä tahansa muu alkuluku kuin 2 ja 3 tulee kirjoittaa jompaankumpaan kaavasta. esim. 5=6(1)-1, 19=6(3)+1,… .

algoritmi:

Määritä taulukko, joka tallentaa kunkin luvun pienimmän alkutekijän indeksiarvon kanssa alkuarvona jokaiselle ryhmä.

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 Ensisijaiset tekijät iteraatiolla

Tässä näytämme koodin Python kieli tietyn luvun alkutekijöiden löytämiseksi iteratiivisessa menetelmässä:

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)

lähtö:

Enter the number you want: 4
4

Python Ensisijaiset tekijät rekursiolla

Tässä osiossa näkyy koodi Python Kieli käyttämällä seulamenetelmää tietyn luvun alkutekijöiden löytämiseen.

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)

lähtö:

Enter the number you want: 4
2
2

C Prime Factors -ohjelma käyttäen iteraatiota

Se on sama ratkaisu kuin iteratiivinen python, mutta kirjoitettu sisään C-kieli.

Pyydämme käyttäjää syöttämään numeron, minkä jälkeen meidän on tarkistettava jokaisen luvun välillä 2 neliöjuureen, onko se jaettavissa tulostamalla kaikki tämän tekijän esiintymät.

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

lähtö:

Enter the number you want: 2
2

C Prime Factors -ohjelma, jossa käytetään rekursiota

Tämä on sama ratkaisu kuin pythonin rekursiivinen ratkaisu, mutta kirjoitettu C-kielellä.

Voimme pyytää käyttäjää syöttämään numeron; sitten rakennamme alkulukutaulukon, joka tallentaa kunkin luvun pienimmän alkutekijän. Lopuksi kutsutaan alkutekijöiden rekursiivista funktiota, joka jakaa annetun luvun pienimmällä alkutekijällä ja palauttaa itsensä takaisin, kunnes saavuttaa yhden.

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

lähtö:

Enter the number you want: 2
2

Mielenkiintoisia faktoja alkuluvuista

• Yksi mielenkiintoisimmista faktoista on, että mikä tahansa muu parillinen luku kuin 2 voi olla kahden alkuluvun summa.
• Esimerkiksi: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … jne.
• Toinen tosiasia on, että ei ole muita peräkkäisiä alkulukuja kuin 2 ja 3, koska ainoa parillinen alkuluku on luku 2.
• Myös kaikki alkuluvut paitsi 2 ja 3 voidaan kirjoittaa seuraavassa muodossa: 6 * n + 1 tai 6 * n – 1, jossa n on positiivinen kokonaisluku.
• Luvun alkutekijöiden joukko on ainutlaatuinen.
• Numero 1 ei ole alkuluku eikä yhdistelmä.
• Lukujen alkulukujen jakaminen voi auttaa ratkaisemaan ongelmia, kuten jaollisuus, murtolukujen yksinkertaistaminen ja eri murtolukujen yhteisten nimittäjien löytäminen.
• Yksi prime factorisation jännittävistä käyttötavoista on myös lukuihin perustuvien salaisten koodien rikkominen.