Algoritmus prvočinitele: C, Python Příklad

Co je primární faktorizace?

Prvotní faktor dané věci žádný číslo je faktor, který je a prvočíslo. Vynásobením faktorů získáte další číslo. Prvočíslo je dělitelné samo sebou nebo 1 .

Jinými slovy, prvočísla se určují tím, že se zjistí, která prvočísla se násobí a tvoří původní číslo.

Příklad: Prvočísla 10 jsou 2 a 5. Je to proto, že 2X5 =10 a obě 2,5 jsou prvočísla.

Hledání prvočinitelů pomocí iterace

Abychom našli prvočíslo daného čísla, nejprve iterujeme všechna čísla od 2 až po druhou odmocninu čísla a pak zkontrolujeme, zda je každé číslo prvočíslo. Dokud je původní číslo dělitelné tímto prvočíslem, přidáváme toto prvočíslo s každou iterací.

Příklad:

Každé prvočíslo větší než 40 je zapsáno v následujícím vzorci: n²+n+41. Můžeme tedy nahradit n všemi čísly, abychom našli odpovídající prvočinitel. např. 0²+0+41=41, 1²+1+41=43, 2²+2+41=47,…

Jak vytisknout prvočíslo čísla?

• V této metodě budeme iterovat čísla od 2 až do druhé odmocniny čísla, jak bylo uvedeno v předchozí části.
• K tomu potřebujeme zkontrolovat modul původního čísla na každém z čísel od 2 do druhé odmocniny n .
• Potom najdeme seznam prvočísel, která jsou faktory n.
• Toto řešení je v časové složitosti O(Sqrt(n)).

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

Síťový algoritmus

Sieve metoda spoléhá na ukládání nejmenšího prvočinitele čísel, což výrazně snižuje složitost při výpočtu prvočísel pro libovolné číslo. Algoritmus Sieve najde všechny primární faktory poněkud efektivně.

• Hlavním konceptem tohoto algoritmu je uložit nejmenší prvočinitel každého čísla až do maximálního čísla.
• Vezmeme nejmenší prvočíslo pro každé dané číslo a přidáme ho k množině prvočísel.
• Nakonec vydělíme tímto prvočíslem a tyto kroky opakujeme, dokud nedosáhneme 1.
• To vše se děje v časové složitosti O(log(n)), což výrazně zlepšuje efektivitu řešení.
• Což umožňuje vypočítat prvočinitele mnohem větších čísel, než s jakými jsme se mohli vypořádat pomocí předchozího přístupu.

Příklad:

Druhým způsobem je zkontrolovat, zda lze číslo zapsat jako 6n-1 nebo 6n+1, protože jakékoli prvočíslo jiné než 2 a 3 by se mělo zapsat do jednoho ze dvou vzorců. např. 5=6(1)-1, 19=6(3)+1,… .

Algoritmus:

Definujte pole pole pro uložení nejmenšího prvočísla každého čísla s hodnotou indexu jako počáteční hodnotou pro každý prvek řada.

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 Prvotní faktory pomocí iterací

Zde vám ukážeme kód Python jazyk k nalezení prvočinitelů daného čísla iterativní metodou:

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)

Výstup:

Enter the number you want: 4
4

Python Prvotní faktory pomocí rekurze

Tato část zobrazuje kód v Python jazyk pomocí síto metody najít prvočinitele daného čísla.

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)

Výstup:

Enter the number you want: 4
2
2

C Program Prime Factors pomocí iterace

Je to stejné řešení jako iterativní python, ale zapsané Jazyk C.

Požádáme uživatele, aby zadal číslo, pak pro každé číslo od 2 do druhé odmocniny tohoto čísla musíme zkontrolovat, zda je dělitelné tiskem všech výskytů tohoto faktoru.

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

Výstup:

Enter the number you want: 2
2

C Program primárních faktorů pomocí rekurze

Toto je stejné řešení jako rekurzivní python, ale napsané v C.

Můžeme požádat uživatele o zadání čísla; potom vytvoříme pole prvočísel, které uchovává nejmenší prvočíselný faktor každého čísla. Nakonec zavoláme rekurzivní funkci Prvočinitele, která vydělí dané číslo jeho nejmenším prvočinitelem a vyvolá se, dokud nedosáhne jedničky.

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

Výstup:

Enter the number you want: 2
2

Několik zajímavých faktů o prvočíslech

• Jedním z nejzajímavějších faktů je, že jakékoli sudé číslo jiné než 2 může být součtem dvou prvočísel.
• Například: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … atd.
• Dalším faktem je, že neexistují žádná po sobě jdoucí prvočísla jiná než 2 a 3, protože jediné sudé prvočíslo je číslo 2.
• Všechna prvočísla kromě 2 a 3 lze také zapsat v následujícím tvaru: 6 * n + 1 nebo 6 * n – 1, kde n je kladné celé číslo.
• Sada prvočinitelů čísla je jedinečná.
• Číslo 1 není ani prvočíslo, ani složené.
• Prvotřídní rozklad čísel může pomoci vyřešit problémy, jako je dělitelnost, zjednodušení zlomků a hledání společných jmenovatelů různých zlomků.
• Jedním ze vzrušujících využití prvočíselného rozkladu je také prolomení tajných kódů, které jsou založeny na číslech.