Dobrý den,
Vyvýjím jednu aplikaci a potřebuji, aby daná aplikace uměla rozložit číslo na
součin prvočísel (prvočíselný rozklad). Naprogramovat nějaký základní
algoritmus není problém, ale problém nastane, pokud do algoritmu zadám nějaké
větší číslo (např. 4848484848484841178813).
Mému algoritmu toto číslo trvá dost dlouho, ale například na této stránce
dostanu výsledek takřtka okamžitě: http://www.numberempire.com/primenumbers.php
Jaký algoritmus byste mi doporučili používat? Na menší čísla se dá použít
faktorizace dělením:
def faktorizace_delenim(i):
prvocisla = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
59, 61, 67, 71, 73, 79, 83, 89, 97]
seznam=[]
cislo = 0
while len(prvocisla) != cislo:
if i%prvocisla[cislo] == 0:
seznam.append(prvocisla[cislo])
i = i/prvocisla[cislo]
else:
cislo = cislo +1
if i == 1: break
seznam.append(i)
return seznam
ale tenhle algoritmus má tu nevýhodu, že bych ten seznam prvočísel (o velikost
od 0 do sqrt(i)) musel vygenerovat, což trvá dost dlouho.
Další algoritmus co znám je Eulerova metoda, ale ta je použitelná pouze v
některých speciálních případech:
#-*- coding: utf-8 -*-
from math import*
import random
def nejvetsi_spolecny_delitel(cislo1,cislo2):
while cislo2 != 0:
r=cislo1%cislo2
cislo1=cislo2
cislo2=r
return cislo1
def ctverec(x, cislo = 2):
while 1:
r=x-cislo**2
if r < 0:
return -1, -1
if int(sqrt(r)) == sqrt(r):
return cislo, sqrt(r)
cislo = cislo+1
def euler(x):
a, b = ctverec(x)
if a == -1:
return u"Toto číslo nelze pomocí tohoto algoritmu rozložit. "
c, d = ctverec(x, min([a, b])+1)
if (a == c or a == d):
return u"Toto číslo nelze pomocí tohoto algoritmu rozložit. "
k=abs(nejvetsi_spolecny_delitel(a-c, d-b))
n=abs(nejvetsi_spolecny_delitel(a+c, d+b))
m=(a+c)/n
l=(d+b)/n
return str((k/2)**2+(n/2)**2)+" * "+str(m**2+l**2)+" = "+str(x)
print euler(1000009)
Poslední algoritmus, který znám je Pollardův rho algoritmus. Pracuje na
podobném principu jako faktorizace dělením, ale s tím rozdílem, že se nesnaží
najít všechny členy prvočíselného rozkladu, ale pouze jeden (a ani ten nemusí
být prvočíslo, proto musíme na výstup z toho algoritmu aplikovat ještě nějaký
jiný faktorizační algoritmus). Nicméně zvládně celkem úspěšně najít dělitele i
ohromných čísel:
from math import*
import random
def nejvetsi_spolecny_delitel(cislo1,cislo2):
while cislo2 != 0:
r=cislo1%cislo2
cislo1=cislo2
cislo2=r
return cislo1
def f(x, n):
return (x**2+random.randint(1, n-1))%n
def pollard(n):
a = random.randint(2, n-3)
b = random.randint(1, n-1)
g = 1
while g == 1:
a = f(a, n)
b = f(b, n)
b = f(b, n)
g = nejvetsi_spolecny_delitel(abs(a-b), n)
if g == n:
return -1
return g
print pollard(618131841351864132181230010152)
Znáte někdo nějaké efektivní řešení?
Děkuji
S pozdravem
Jakub Vojáček
_______________________________________________
Python mailing list
[email protected]
http://www.py.cz/mailman/listinfo/python
