Prime Factor-algoritme: C, Python-voorbeeld

Wat is een priemfactorisatie?

De priemfactor van een gegeven elke getal is de factor die a is priemgetal. Als de factoren worden vermenigvuldigd, krijgt u een ander getal. Een priemgetal is deelbaar door zichzelf of door 1.

Met andere woorden, priemfactoren worden bepaald door te bepalen welke priemgetallen zich vermenigvuldigen om het oorspronkelijke getal te vormen.

Voorbeeld: Priemfactoren van 10 zijn 2 en 5. Dit komt omdat 2X5 =10 en beide 2,5 priemgetallen zijn.

Het vinden van de priemfactoren met behulp van iteratie

Om de priemfactoren van een bepaald getal te vinden, herhalen we eerst alle getallen vanaf 2 tot aan de wortel van het getal, en controleren dan of elk getal een priemgetal is. Zolang het oorspronkelijke getal deelbaar is door dit priemgetal, blijven we dit priemgetal bij elke iteratie toevoegen.

Voorbeeld:

Elk priemgetal groter dan 40 wordt in de follo geschrevenwing formule: n2+n+41. We kunnen dus n vervangen door alle getallen om de overeenkomstige priemfactor te vinden. bijvoorbeeld 02+0+41=41, 12+1+41=43, 22+2+41=47,…

Hoe druk ik een priemfactor van een getal af?

  • Bij deze methode herhalen we de getallen van 2 tot de vierkantswortel van het getal, zoals vermeld in de vorige sectie.
  • Daarvoor moeten we de modulus van het oorspronkelijke getal op elk van de getallen van 2 tot de wortel van n controleren.
  • Vervolgens vinden we de lijst met priemgetallen die factoren zijn van n.
  • Deze oplossing is in O(Sqrt(n)) tijd complexheid.

Algoritme:

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

Zeef algoritme

De zeefmethode is gebaseerd op het opslaan van de kleinste priemfactor van de getallen, waardoor de com wordt verminderdplexDit is merkbaar bij het berekenen van de priemfactoren voor elk getal. Het zeefalgoritme vindt alle hoofdfactoren enigszins efficiënt.

  • Het belangrijkste concept van dit algoritme is om de kleinste priemfactor van elk getal op te slaan tot het maximale getal.
  • We nemen het kleinste priemgetal voor elk gegeven getal en voegen dit toe aan de reeks priemfactoren.
  • Ten slotte delen we door dit priemgetal en herhalen we deze stappen totdat we 1 bereiken.
  • Dit gebeurt allemaal in O(log(n)) tijd complexwaardoor de efficiëntie van de oplossing aanzienlijk wordt verbeterd.
  • Dit maakt het mogelijk om de priemfactoren van veel grotere getallen te berekenen dan die waarmee we met de vorige aanpak hadden kunnen omgaan.

Voorbeeld:

De tweede manier is om te controleren of het getal kan worden geschreven als 6n-1 of 6n+1, aangezien elk priemgetal anders dan 2 en 3 in een van de twee formules moet worden geschreven. bijv. 5=6(1)-1, 19=6(3)+1,… .

Algoritme:

Definieer een array-array om de kleinste priemfactor van elk getal op te slaan, met de indexwaarde als beginwaarde voor elk element van de reeks.

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 Prime-factoren met behulp van iteratie

Hier zullen we sho zijnwing een code in Python-taal om de belangrijkste factoren van een bepaald getal te vinden in een iteratieve methode:

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 Prime-factoren met behulp van recursie

In deze sectie wordt een code weergegeven Python-taal de zeefmethode gebruiken om de priemfactoren van een bepaald getal te vinden.

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-programma met behulp van iteratie

Het is dezelfde oplossing als de iteratieve Python-oplossing, maar dan geschreven C taal.

We vragen de gebruiker om het getal in te voeren. Vervolgens moeten we voor elk getal van 2 tot de wortel van dit getal controleren of het deelbaar is door alle exemplaren van deze factor af te drukken.

#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-programma met behulp van recursie

C Prime Factors-programma met behulp van recursie

Dit is dezelfde oplossing als de recursieve python-oplossing, maar geschreven in C.

We kunnen de gebruiker vragen het nummer in te voeren; Vervolgens bouwen we de matrix met priemgetallen waarin de kleinste priemfactor van elk getal wordt opgeslagen. Ten slotte noemen we de priemfactoren recursieve functie, die het gegeven getal deelt door de kleinste priemfactor en zichzelf herinnert totdat het één bereikt.

#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

Enkele interessante feiten over priemgetallen

  • Een van de meest interessante feiten is dat elk even getal anders dan 2 de som kan zijn van twee priemgetallen.
  • Bijvoorbeeld: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … enz.
  • Een ander feit is dat er geen andere opeenvolgende priemgetallen zijn dan 2 en 3, aangezien het enige even priemgetal het getal 2 is.
  • Ook kunnen alle priemgetallen behalve 2 en 3 in de follo worden geschrevenwing vorm: 6 * n + 1 of 6 * n – 1, waarbij n een positief geheel getal is.
  • De verzameling priemfactoren van een getal is uniek.
  • Nummer 1 is noch priemgetal, noch samengesteld.
  • Het ontbinden van getallen in priemgetallen kan helpen bij het oplossen van problemen zoals deelbaarheid, het vereenvoudigen van breuken en het vinden van gemeenschappelijke noemers van verschillende breuken.
  • Een van de opwindende toepassingen van priemfactorisatie is ook het doorbreken van geheime codes die op getallen zijn gebaseerd.