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
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.