Prímtényező algoritmus: C, Python Példa

Mi az a primer Faktorizáció?

Egy szám prímtényezője olyan tényező, amely maga is egy prímszám, csak 1-gyel és önmagával osztható.

Példa: A 10 prímtényezői 2 és 5, mivel 2 × 5 = 10.

Elsődleges tényezők megkeresése iteráció segítségével

Iterálj 2-től sqrt(n)-ig, és ellenőrizd az oszthatóságot. Amíg n osztható az aktuális jelölttel, oszd el és írd ki.

Példa: minden 40-nél nagyobb prímszám illik n-hez²+n+41, tehát n = 0, 1, 2 esetén 41, 43, 47.

Hogyan kell egy szám prímtényezőjét nyomtatni?

• Ismételje meg a számokat 2-től sqrt(n)-ig.
• Ellenőrizd az n modulusát minden jelölttel szemben; a nulla maradék azt jelenti, hogy a jelölt prímtényező.
• Gyűjtsd össze az összes prímszámot, amely osztja n-et.
• A rutin O(sqrt(n)) időbonyolultsággal fut.

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 minden szám legkisebb prímtényezőjét tárolja egy maximális korlátig, jelentősen csökkentve a faktorizáció költségét az előszámítás után.

• Írd fel minden egész szám legkisebb prímtényezőjét a maximális határig.
• Vedd a legkisebb prímszámot, és add hozzá a faktorhalmazhoz.
• Oszd el a kapott számot a prímszámmal, és ismételd ezt, amíg el nem éred az 1-et.
• Minden lekérdezés körülbelül O(log n) alatt fut.

Példa: Egy 2-től és 3-tól eltérő prímszám 6n-1 vagy 6n+1 alakot visel. Például 5 = 6(1)-1 és 19 = 6(3)+1.

Algoritmus: definiál egy sor amely minden szám legkisebb prímtényezőjét tárolja, minden elem kezdeti értékét az indexszel használva.

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]

Kapcsolódó cikkek

• Grafikon adatszerkezet és Algorithms
• Utazó eladó probléma
• Felezési módszer algoritmus
• Vödör rendezési algoritmus

Python Elsődleges tényezők iterációt használva

A következő Python A kód iteratív próbaosztásos módszerrel keresi meg a prímtényezőket:

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

Python Elsődleges tényezők rekurzió használatával

Az Python Az alábbi kód a szita módszert használja egy adott szám prímtényezőinek megtalálására.

import math
High = (int)(1e5 + 7)
array = [0 for i in range(High)]

# generate smallest prime factors
def Sieve():
    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):  # divide until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n / array[n]))

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

Ugyanaz az iteratív megoldás írva a C: írjon be egy számot, majd 2-től sqrt(n)-ig minden lehetséges számra ellenőrizze az oszthatóságot, és írja ki a prímtényezők ö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

A rekurzív C verzió tükrözi a Python egy: ​​építsd fel a legkisebb prímtényezők tömbjét, majd ismételd meg az osztást ezzel a tényezővel, amíg n el nem éri az 1-et.

#include <stdio.h>
int Max = 100007;
int array[100007];

void Sieve()  // smallest prime factors up to Max
{
    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)  // divide until we reach 1
        return;
    printf("%d\n", array[n]);
    PrimeFactors(n / array[n]);
}

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

• Bármely 2-n kívüli páros szám felírható két prímszám összegeként (4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3).
• Nincsenek egymást követő prímszámok a 2-n és a 3-on kívül, mivel a 2 az egyetlen páros prímszám.
• A 2-es és 3-as kivételével minden prímszám 6n + 1 vagy 6n − 1 alakot ölt, ahol n pozitív egész szám.
• Egy szám prímtényezőinek halmaza egyedi.
• Az 1-es szám se nem prím, se nem összetett.
• A prímtényezős felbontás segít az oszthatóságban, a törtek egyszerűsítésében és a közös nevezők megtalálásában.
• A prímtényezős felbontás a számalapú kriptográfiai kódok alapját is képezi.

GYIK