Algteguri algoritm: C, Python Näide

Mis on peafaktoriseerimine?

Antud algtegur mistahes arv on tegur, mis on a algarv. Tegurid korrutatuna annavad teise arvu. Algarv jagub iseenda või 1-ga.

Teisisõnu määratakse algtegurid, leides, millised algarvud korrutades moodustavad algarvu.

Näide: 10 algtegurid on 2 ja 5. Seda seetõttu, et 2X5 =10 ja mõlemad 2,5 on algarvud.

Peamiste tegurite leidmine iteratsiooni abil

Antud arvu algtegurite leidmiseks kordame esmalt kõiki arve alates 2 kuni arvu ruutjuureni ja seejärel kontrollime, kas iga arv on algarv. Kuni algne arv on selle algarvuga jagatav, lisame selle algarvu iga iteratsiooniga.

Näide:

Iga algarv, mis on suurem kui 40, kirjutatakse järgmisesse valemisse: n2+n+41. Seega saame vastava algteguri leidmiseks asendada n kõigi arvudega. näiteks 02+0+41=41, 12+1+41=43, 22+2+41=47,…

Kuidas printida arvu algtegurit?

  • Selle meetodi puhul kordame numbreid alates 2 kuni numbri ruutjuureni, nagu eelmises jaotises mainitud.
  • Selleks peame kontrollima algarvu moodulit igal arvul alates 2 kuni ruutjuureni n .
  • Seejärel leiame loendi algarvudest, mis on n-i tegurid.
  • See lahendus on O(Sqrt(n)) aja keerukuses.

Algoritm:

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

Sõela algoritm

Sõelameetod põhineb arvude väikseima algteguri salvestamisel, mis vähendab märkimisväärselt keerukust mis tahes arvu algtegurite arvutamisel. Sõela algoritm leiab kõik algtegurid mõnevõrra tõhusalt.

  • Selle algoritmi põhikontseptsioon on salvestada iga arvu väikseim algtegur kuni maksimaalse arvuni.
  • Võtame iga antud arvu väikseima algarvu ja lisame selle algtegurite hulka.
  • Lõpuks jagame selle algarvuga ja kordame neid samme, kuni jõuame 1-ni.
  • Seda kõike tehakse O(log(n)) aja keerukuses, mis parandab oluliselt lahenduse efektiivsust.
  • Mis võimaldab arvutada palju suuremate arvude algtegureid kui need, mida oleksime saanud käsitleda eelmist lähenemist kasutades.

Näide:

Teine võimalus on kontrollida, kas arvu saab kirjutada kujul 6n-1 või 6n+1, kuna mis tahes algarv peale 2 ja 3 tuleks kirjutada ühte kahest valemist. nt 5=6(1)-1, 19=6(3)+1,… .

Algoritm:

Määratlege massiivi massiiv, mis salvestab iga arvu väikseima algteguri koos indeksi väärtusega iga elemendi algväärtusena. massiivi.

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 Iteratsiooni kasutavad algtegurid

Siin näitame sisse koodi Python keel antud arvu algtegurite leidmiseks iteratiivsel meetodil:

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)

Väljund:

Enter the number you want: 4
4

Python Rekursiooni kasutavad algtegurid

Selles jaotises kuvatakse kood Python keel kasutades sõelmeetodit antud arvu algtegurite leidmiseks.

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)

Väljund:

Enter the number you want: 4
2
2

C peamiste tegurite programm, mis kasutab iteratsiooni

See on sama lahendus kui iteratiivne python, kuid see on sisse kirjutatud C keel.

Palume kasutajal sisestada arv, seejärel peame kontrollima iga arvu puhul alates 2 kuni selle arvu ruutjuureni, trükkides välja kõik selle teguri esinemised.

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

Väljund:

Enter the number you want: 2
2

C põhitegurite programm, mis kasutab rekursiooni

C põhitegurite programm, mis kasutab rekursiooni

See on sama lahendus mis pythoni rekursiivne lahendus, kuid kirjutatud C-s.

Võime paluda kasutajal numbri sisestada; seejärel koostame algarvude massiivi, mis salvestab iga arvu väikseima algteguri. Lõpuks nimetame rekursiivseks funktsiooniks Algtegurid, mis jagab antud arvu väikseima algteguriga ja tuletab end meelde, kuni jõuab üheni.

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

Väljund:

Enter the number you want: 2
2

Mõned huvitavad faktid algarvude kohta

  • Üks huvitavamaid fakte on see, et iga paarisarv peale 2 võib olla kahe algarvu summa.
  • Näiteks: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … jne.
  • Teine tõsiasi on see, et peale 2 ja 3 ei ole ühtegi järjestikust algarvu, kuna ainus paaris algarv on arv 2.
  • Samuti saab kõik algarvud peale 2 ja 3 kirjutada järgmisel kujul: 6 * n + 1 või 6 * n – 1, kus n on positiivne täisarv.
  • Arvu algtegurite kogum on kordumatu.
  • Arv 1 ei ole alg ega liit.
  • Arvude algfaktoriseerimine võib aidata lahendada selliseid probleeme nagu jaguvus, murdude lihtsustamine ja erinevate murdude ühisnimetajate leidmine.
  • Samuti on algfaktoriseerimise üks põnevaid kasutusviise numbripõhiste salakoodide murdmine.