Prímtényező algoritmus: C, Python Példa
Sarah Chen
Mi az a primer Faktorizáció?
Egy adott prímtényezője bármilyen a szám az a tényező, amely a prímszám. A tényezők szorozva egy másik számot adnak. Egy prímszám osztható önmagával vagy 1-gyel.
Más szavakkal, a prímtényezőket úgy határozzuk meg, hogy megtaláljuk, mely prímszámok szorozva alkotják az eredeti számot.
Példa: A 10-es prímtényezők 2 és 5. Ez azért van, mert 2X5 =10 és mindkettő 2,5 prímszám.
Elsődleges tényezők megkeresése iteráció segítségével
Egy adott szám prímtényezőinek megtalálásához először iteráljuk az összes számot 2-től a szám négyzetgyökéig, majd ellenőrizzük, hogy minden szám prím-e. Mindaddig, amíg az eredeti szám osztható ezzel a prímmel, minden iterációnál ezt a prímet adjuk hozzá.
Példa:
Minden 40-nél nagyobb prímszámot a következő képletbe írunk: n2+n+41. Tehát helyettesíthetjük n-t az összes számmal, hogy megtaláljuk a megfelelő prímtényezőt. pl 02+0+41=41, 12+1+41=43, 22+2+41=47,…
Hogyan kell egy szám prímtényezőjét nyomtatni?
- Ebben a módszerben a számokat 2-től a szám négyzetgyökéig iteráljuk, amint azt az előző részben említettük.
- Ehhez minden egyes számon ellenőriznünk kell az eredeti szám modulusát 2-től n négyzetgyökéig.
- Ezután megtaláljuk azon prímszámok listáját, amelyek n tényezői.
- Ez a megoldás O(Sqrt(n)) időbonyolultságú.
Algoritmus:
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
Szita algoritmus
A szita módszer a számok legkisebb prímtényezőjének tárolásán alapul, ami észrevehetően csökkenti a bonyolultságot bármely szám prímtényezőinek kiszámításakor. A szita-algoritmus valamennyi prímtényezőt valamelyest hatékonyan megtalálja.
- Ennek az algoritmusnak az a fő koncepciója, hogy minden szám legkisebb prímtényezőjét tárolja a maximális számig.
- Minden adott számhoz vesszük a legkisebb prímszámot, és hozzáadjuk a prímtényezők halmazához.
- Végül osztunk ezzel a prímszámmal, és addig ismételjük ezeket a lépéseket, amíg el nem érjük az 1-et.
- Mindez O(log(n)) időbonyolításban történik, ami jelentősen javítja a megoldás hatékonyságát.
- Ez lehetővé teszi sokkal nagyobb számok prímtényezőinek kiszámítását, mint amelyekkel az előző megközelítéssel foglalkozhattunk volna.
Példa:
A második módszer annak ellenőrzése, hogy a szám felírható-e 6n-1 vagy 6n+1 alakban, mivel a 2-től és 3-tól eltérő prímszámot be kell írni a két képlet valamelyikébe. pl. 5=6(1)-1, 19=6(3)+1,… .
Algoritmus:
Határozzon meg egy tömbtömböt, amely az egyes számok legkisebb prímtényezőjét tárolja úgy, hogy a szám minden elemének kezdőértéke legyen az indexérték. sor.
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 Elsődleges tényezők iterációt használva
Itt egy kódot fogunk megjeleníteni Python nyelv egy adott szám prímtényezőinek megtalálásához iteratív módszerrel:
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)
output:
Enter the number you want: 4 4
Python Elsődleges tényezők rekurzió használatával
Ez a rész egy kódot mutat be Python nyelv szita módszerrel keressük meg egy adott szám prímtényezőit.
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)
output:
Enter the number you want: 4 2 2
C Prime Factors program iterációt használva
Ez ugyanaz a megoldás, mint az iteratív python, de be van írva C nyelv.
Megkérjük a felhasználót, hogy írja be a számot, majd 2-től a szám négyzetgyökéig minden egyes számnál ellenőriznünk kell, hogy osztható-e úgy, hogy kinyomtatja ennek a tényezőnek az összes előfordulásá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;
}
output:
Enter the number you want: 2 2
C Prime Factors program rekurziót használva
Ez ugyanaz a megoldás, mint a python rekurzív megoldás, de C-ben van írva.
Megkérhetjük a felhasználót a szám megadására; majd elkészítjük azt a prímtömböt, amely az egyes számok legkisebb prímtényezőjét tárolja. Végül a Prímtényezők rekurzív függvénynek nevezzük, amely elosztja az adott számot a legkisebb prímtényezőjével, és visszahívja magát, amíg el nem éri az egyet.
#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;
}
output:
Enter the number you want: 2 2
Néhány érdekes tény a prímszámokról
- Az egyik legérdekesebb tény, hogy a 2-től eltérő bármely páros szám lehet két prímszám összege.
- Például: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … stb.
- Egy másik tény, hogy a 2-en és 3-on kívül nincsenek egymást követő prímek, mivel az egyetlen páros prímszám a 2.
- Ezenkívül a 2 és 3 kivételével minden prímszám felírható a következő formában: 6 * n + 1 vagy 6 * n – 1, ahol n pozitív egész szám.
- Egy szám prímtényezőinek halmaza egyedi.
- Az 1-es szám nem prím és nem összetett.
- A számok prímtényezőssé tétele segíthet olyan problémák megoldásában, mint az oszthatóság, a törtek egyszerűsítése és a különböző törtek közös nevezőinek megtalálása.
- A prímfaktorizálás egyik izgalmas felhasználási módja továbbá a számalapú titkos kódok feltörése.
