Algoritmo dei fattori primi: C, Python Esempio

Cos'è una fattorizzazione prima?

Il fattore primo di un dato in qualsiasi il numero è il fattore che è a numero primo. I fattori moltiplicati danno un altro numero. Un numero primo è divisibile per se stesso o per 1 .

In altre parole, i fattori primi vengono determinati trovando quali numeri primi si moltiplicano insieme per formare il numero originale.

Esempio: I fattori primi di 10 sono 2 e 5. Questo perché 2X5 =10 ed entrambi 2,5 sono numeri primi.

Trovare i Fattori Primi utilizzando l'Iterazione

Per trovare i fattori primi di un dato numero, prima iteriamo su tutti i numeri da 2 fino alla radice quadrata del numero, quindi controlliamo se ciascun numero è primo. Finché il numero originale è divisibile per questo numero primo, continuiamo ad aggiungerlo ad ogni iterazione.

Esempio:

Ogni numero primo maggiore di 40 è scritto nella seguente formula: n²+n+41. Quindi possiamo sostituire n con tutti i numeri per trovare il corrispondente fattore primo. ad esempio, 0²+0+41=41²+1+41=43²+2+41=47,…

Come stampare un fattore primo di un numero?

• In questo metodo, ripeteremo i numeri da 2 fino alla radice quadrata del numero, come menzionato nella sezione precedente.
• Per questo, dobbiamo controllare il modulo del numero originale su ciascuno dei numeri da 2 fino alla radice quadrata di n .
• Troviamo poi l'elenco dei numeri primi che sono fattori di n.
• Questa soluzione ha una complessità temporale pari a 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 Sieve si basa sulla memorizzazione del più piccolo fattore primo dei numeri, il che riduce notevolmente la complessità quando si calcolano i fattori primi per qualsiasi numero. L'algoritmo Sieve trova tutti i fattori primi in modo abbastanza efficiente.

• Il concetto principale di questo algoritmo è memorizzare il più piccolo fattore primo di ciascun numero fino al numero massimo.
• Prendiamo il numero primo più piccolo per ciascun numero dato e lo aggiungiamo all'insieme dei fattori primi.
• Infine, dividiamo per questo numero primo e ripetiamo questi passaggi finché non raggiungiamo 1.
• Tutto questo viene fatto con una complessità temporale di O(log(n)), migliorando notevolmente l'efficienza della soluzione.
• Ciò rende possibile calcolare i fattori primi di numeri molto più grandi di quelli che avremmo potuto trattare utilizzando l'approccio precedente.

Esempio:

Il secondo modo è verificare se il numero può essere scritto come 6n-1 o 6n+1 poiché qualsiasi numero primo diverso da 2 e 3 dovrebbe essere scritto in una delle due formule. ad esempio, 5=6(1)-1, 19=6(3)+1,… .

Algoritmo:

Definire un array per memorizzare il più piccolo fattore primo di ogni numero con il valore dell'indice come valore iniziale per ogni elemento di schieramento.

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 Fattori primi utilizzando l'iterazione

Qui mostreremo un codice in Python linguaggio per trovare i fattori primi di un dato numero in un metodo iterativo:

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
4

Python Fattori primi mediante ricorsione

Questa sezione mostra un codice in Python Lingua utilizzando 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)]
# 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)

Produzione:

Enter the number you want: 4
2
2

Programma C Prime Factors utilizzando l'iterazione

È la stessa soluzione di quella iterativa di Python ma scritta Linguaggio C..

Chiediamo all'utente di inserire il numero, quindi per ogni numero da 2 alla radice quadrata di questo numero, dobbiamo verificare se è divisibile stampando tutte le occorrenze di questo fattore.

#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

Questa è la stessa soluzione ricorsiva di Python ma scritta in C.

Possiamo chiedere all'utente di inserire il numero; quindi, costruiamo l'array dei numeri primi che memorizza il più piccolo fattore primo di ciascun numero. Chiamiamo infine la funzione ricorsiva Fattori Primi, che divide il numero dato per il suo più piccolo fattore primo e si richiama fino a raggiungere l'uno.

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

Produzione:

Enter the number you want: 2
2

Alcuni fatti interessanti sui numeri primi

• Uno dei fatti più interessanti è che qualsiasi numero pari diverso da 2 può essere la somma di due numeri primi.
• Ad esempio: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … ecc.
• Un altro fatto è che non esistono numeri primi consecutivi diversi dal 2 e dal 3, poiché l'unico numero primo pari è il numero 2.
• Inoltre, tutti i numeri primi, tranne 2 e 3, possono essere scritti nella seguente forma: 6 * n + 1 oppure 6 * n – 1, dove n è un numero intero positivo.
• L’insieme dei fattori primi di un numero è unico.
• Il numero 1 non è né primo né composto.
• La scomposizione in fattori primi dei numeri può aiutare a risolvere problemi come la divisibilità, la semplificazione delle frazioni e la ricerca di denominatori comuni di diverse frazioni.
• Inoltre, uno degli usi più interessanti della scomposizione in fattori primi è la decifrazione di codici segreti basati sui numeri.