Algoritam primarnog faktora: C, Python Primjer
Što je prosta faktorizacija?
Glavni faktor datog Bilo koji broj je faktor koji je a glavni broj. Čimbenici kada se pomnože daju vam drugi broj. Prost broj je djeljiv sam sa sobom ili s 1.
Drugim riječima, prosti faktori određuju se pronalaženjem prostih brojeva koji se međusobno množe da bi formirali izvorni broj.
Primjer: Prosti faktori od 10 su 2 i 5. To je zato što je 2X5 =10 i oba 2,5 prosti brojevi.
Pronalaženje prostih faktora pomoću iteracije
Da bismo pronašli proste faktore određenog broja, prvo prelazimo sve brojeve od 2 do kvadratnog korijena broja, a zatim provjeravamo je li svaki broj prost. Sve dok je izvorni broj djeljiv s ovim prostim brojem, nastavljamo zbrajati ovaj prosti broj sa svakom iteracijom.
Primjer:
Svaki prosti broj veći od 40 zapisuje se sljedećom formulom: n2+n+41. Dakle, možemo zamijeniti n sa svim brojevima kako bismo pronašli odgovarajući prosti faktor. npr. 02+0+41=41, 12+1+41=43, 22+2+41=47,…
Kako ispisati prosti faktor broja?
- U ovoj metodi ponavljat ćemo brojeve od 2 do kvadratnog korijena broja, kao što je spomenuto u prethodnom odjeljku.
- Za to moramo provjeriti modul izvornog broja na svakom od brojeva od 2 do kvadratnog korijena iz n.
- Zatim nalazimo popis prostih brojeva koji su faktori broja n.
- Ovo rješenje ima O(Sqrt(n)) vremensku složenost.
Algoritam:
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
Algoritam sita
Metoda sita oslanja se na pohranjivanje najmanjeg prostog faktora brojeva, što znatno smanjuje složenost pri izračunavanju prostih faktora za bilo koji broj. Sito algoritam pronalazi sve proste faktore donekle učinkovito.
- Glavni koncept ovog algoritma je pohraniti najmanji prosti faktor svakog broja do maksimalnog broja.
- Uzimamo najmanji prosti broj za svaki zadani broj i dodajemo ga skupu prostih faktora.
- Na kraju, dijelimo s ovim prostim brojem i ponavljamo ove korake dok ne dođemo do 1.
- Sve se to radi u O(log(n)) vremenskoj složenosti, čime se uvelike poboljšava učinkovitost rješenja.
- Što omogućuje izračunavanje prostih faktora mnogo većih brojeva od onih s kojima smo mogli postupati korištenjem prethodnog pristupa.
Primjer:
Drugi način je provjeriti može li se broj napisati kao 6n-1 ili 6n+1 budući da bilo koji prosti broj osim 2 i 3 treba napisati u jednoj od dviju formula. npr. 5=6(1)-1, 19=6(3)+1,… .
Algoritam:
Definirajte polje polja za pohranjivanje najmanjeg prostog faktora svakog broja s vrijednošću indeksa kao početnom vrijednošću za svaki element poredak.
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 Primarni faktori korištenjem iteracije
Ovdje ćemo prikazati kod Python jezik za pronalaženje prostih faktora zadanog broja u iterativnoj metodi:
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)
Izlaz:
Enter the number you want: 4 4
Python Primarni faktori korištenjem rekurzije
Ovaj odjeljak prikazuje kôd u Python jezik pomoću metode sita pronaći proste faktore zadanog broja.
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)
Izlaz:
Enter the number you want: 4 2 2
Program C prostih faktora korištenjem iteracije
To je isto rješenje kao iterativno python, ali napisano u njemu C jezik.
Tražimo od korisnika da unese broj, a zatim za svaki broj od 2 do kvadratnog korijena tog broja trebamo provjeriti je li djeljiv ispisivanjem svih pojavljivanja ovog faktora.
#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; }
Izlaz:
Enter the number you want: 2 2
Program C prostih faktora korištenjem rekurzije
Ovo je isto rješenje kao i python rekurzivno, ali napisano u C-u.
Možemo tražiti od korisnika da unese broj; zatim gradimo niz prostih brojeva koji pohranjuje najmanji prosti faktor svakog broja. Konačno, proste faktore nazivamo rekurzivnom funkcijom, koja dijeli zadani broj s njegovim najmanjim prostim faktorom i prisjeća se dok ne dođe do jedan.
#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; }
Izlaz:
Enter the number you want: 2 2
Nekoliko zanimljivih činjenica o prostim brojevima
- Jedna od najzanimljivijih činjenica je da svaki paran broj osim 2 može biti zbroj dva prosta broja.
- Na primjer: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … itd.
- Još jedna činjenica je da ne postoje uzastopni prosti brojevi osim 2 i 3, budući da je jedini paran prost broj broj 2.
- Također, svi prosti brojevi osim 2 i 3 mogu se napisati u sljedećem obliku: 6 * n + 1 ili 6 * n – 1, gdje je n pozitivan cijeli broj.
- Skup prostih faktora broja je jedinstven.
- Broj 1 nije ni prost ni složen.
- Rastavljanje brojeva na proste faktore može pomoći u rješavanju problema poput djeljivosti, pojednostavljivanja razlomaka i pronalaženja zajedničkih nazivnika različitih razlomaka.
- Također, jedna od uzbudljivih upotreba rastavljanja na proste faktore je razbijanje tajnih kodova koji se temelje na brojevima.