"Andreas Kryger Jensen" <xylofonius@hotpop.com> writes:
> Enten er jeg blevet dum, eller også er det fordi, det er sent.
> Jeg sidder her og forsøger at lavet et forholdsvist simpelt script, der skal
> primtalsfaktorisere et tal, som brugeren vælger.
> Er der ikke en eller anden, der gider skrive noget pseudokode, eller i det
> mindste komme med et lille hint, for lige nu er jeg blank. :)
Start med at gøre dig klart hvilken faktoriseringsalgoritme du vil
bruge. Der findes flere forskellige, som er mere eller mindre
effektive.
Hvis vi antager at du vil bruge den simpleste, nemlig bare rå division
til du finder noget der er bonus på, så prøv noget i stil med:
$testtal = <tal du vil primtalsfaktorisere>;
$divisor = 2;
$foo = $testtal;
while ($foo != 1 && $i < sqrt($testtal)) {
while ($testtal % $i == 0) {
$foo /= $i;
$divisorer[] = $i;
}
$i++
}
Den kan naturligvis optimeres ved bruge af Eratostenes' si, eller blot
ved at undgå at dividere med alle lige tal efter man har prøvet 2 (en
simpel udgave af Eratostenes' si).
Alternativt kan vælges en helt anden algoritme, lidt afhængigt af hvor
store tal du vil faktorisere, fx Pollards rho-metode, Quadratic sieve,
og hvis det skal være avanceret number field sieve, som er blevet
brugt til at faktorisere en del RSA-X tal med.
.... og et par stykker mere, som jeg har glemt i skyndingen, men som du
kan finde i enhver fornuftig algoritmebog.
(med forbehold for at jeg ikke er helt ædru på nuværende tidspunkt :)
--
Jacob -
www.bunk.cc
That does not compute.