Algoritmo dei fattori primi: C, Python Esempio

Cos'è una fattorizzazione prima?

Il fattore primo di un numero è un fattore che è a sua volta un numero primo, divisibile solo per 1 e per se stesso.

Esempio: I fattori primi di 10 sono 2 e 5, poiché 2 × 5 = 10.

Trovare i Fattori Primi utilizzando l'Iterazione

Itera da 2 fino a sqrt(n) e verifica la divisibilità. Finché n è divisibile per il candidato corrente, dividi e stampa.

Esempio: ogni numero primo maggiore di 40 si adatta a n²+n+41, quindi n = 0, 1, 2 produce 41, 43, 47.

Come stampare un fattore primo di un numero?

• Itera i numeri da 2 fino a sqrt(n).
• Verifica il modulo di n per ciascun candidato; un resto pari a zero indica che il candidato è un fattore primo.
• Raccogli tutti i numeri primi che dividono n.
• La routine ha una complessità temporale di O(sqrt(n)).

Algoritmo:

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

Algoritmo del setaccio

Il metodo del crivello memorizza il più piccolo fattore primo di ogni numero fino a un limite massimo, riducendo drasticamente i costi di fattorizzazione dopo il precalcolo.

• Registra il più piccolo fattore primo di ogni numero intero fino al limite massimo.
• Prendi il più piccolo numero primo e aggiungilo all'insieme dei fattori.
• Dividi il numero per quel numero primo e ripeti l'operazione finché non raggiungi 1.
• Ogni query viene eseguita in circa O(log n).

Esempio: Un numero primo diverso da 2 e 3 ha la forma 6n-1 o 6n+1. Ad esempio, 5 = 6(1)-1 e 19 = 6(3)+1.

Algoritmo: definire un schieramento che memorizza il più piccolo fattore primo di ciascun numero, utilizzando l'indice come valore iniziale per ogni elemento.

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]

Articoli Correlati

• Struttura dei dati del grafico e Algorithms
• Problema del commesso viaggiatore
• Algoritmo del metodo di bisezione
• Algoritmo di ordinamento del bucket

Python Fattori primi utilizzando l'iterazione

Le seguenti Python Il codice trova i fattori primi utilizzando il metodo iterativo della divisione per tentativi:

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)

Produzione:

Enter the number you want: 4
2
2

Python Fattori primi mediante ricorsione

Migliori Python Il codice seguente utilizza il metodo del crivello per trovare i fattori primi di un dato numero.

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)

Produzione:

Enter the number you want: 4
2
2

Programma C Prime Factors utilizzando l'iterazione

La stessa soluzione iterativa scritta in C: inserisci un numero, quindi per ogni candidato da 2 fino a sqrt(n), verifica la divisibilità e stampa ogni occorrenza di un fattore primo.

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

Produzione:

Enter the number you want: 2
2

C Programma a fattori primi che utilizza la ricorsione

La versione ricorsiva C rispecchia la Python 1: costruire l'array dei più piccoli fattori primi, quindi ripetere la divisione per quel fattore finché n non raggiunge 1.

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

Produzione:

Enter the number you want: 2
2

Alcuni fatti interessanti sui numeri primi

• Qualsiasi numero pari diverso da 2 può essere scritto come somma di due numeri primi (4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3).
• Non ci sono altri numeri primi consecutivi oltre a 2 e 3, perché 2 è l'unico numero primo pari.
• Ogni numero primo, eccetto 2 e 3, ha la forma 6n + 1 o 6n − 1, dove n è un intero positivo.
• L'insieme dei fattori primi di un numero è unico.
• Il numero 1 non è né primo né composto.
• La scomposizione in fattori primi aiuta a risolvere i problemi di divisibilità, a semplificare le frazioni e a trovare i denominatori comuni.
• La fattorizzazione in numeri primi è alla base anche dei codici crittografici basati sui numeri.

DOMANDE FREQUENTI