Ontbinden in priemfactoren

Een script dat een getal ontbindt in priemfactoren.
Dus 200 wordt:
2 * 2 * 2 * 5 * 5
en 2940 wordt:
2 * 2 * 3 * 5 * 7 * 7

Het script gaat zo te werk:
1. Zoek alle priemgetallen die kleiner zijn dan of gelijk zijn aan het input getal en zet ze in de array $priemgetallen
2. Probeer het input getal te delen door alle priemgetallen, beginnend bij 2. Als dat lukt, zet het priemgetal waardoor het input getal gedeeld is in de array $priemfactoren.
3. Als het input getal hoger is dan 1, ga dan naar stap 2

Momentele versie: 1.5

P.S. Dit is mijn eerste script dat ik op PHPhulp post.

Voorbeeld: http://62.194.27.18/ontbinden_in_priemfactoren.php

Gesponsorde koppelingen

PHP script bestanden

1. ontbinden-in-priemfactoren

Er zijn 14 reacties op 'Ontbinden in priemfactoren'

PHP hulp
0 seconden vanaf nu

 

Gesponsorde koppelingen

steen
17 jaar geleden

 

0 -0

200 = 2 * 2 * 2 * 5 * 5 (volgens je script)

Computer
17 jaar geleden

 

0 -0

Ja, sorry, stond verkeerd in de toelichting. Ik heb het verbeterd.

Ruud Verbij
17 jaar geleden

 

0 -0

Heey,
Leuk script. Kan goed gebruikt worden voor bijvoorbeeld het kraken van RSA (of iets dergelijks).
Misschien goed om eens te kijken naar een efficiëntere manier om je lijst met priemgetallen op te bouwen. Je zou dan kunnen kijken naar de Zeef van Eratosthenes (http://nl.wikipedia.org/wiki/Zeef_van_Eratosthenes).

Verder hoef je wat betreft het zoeken naar priemfactoren nooit hoger te gaan dan de wortel van het getal. Zie hiervoor het artikel over priemfactoren (http://nl.wikipedia.org/wiki/Priemfactor).

Beide tips schelen waarschijnlijk behoorlijk voor de rekentijd die je script nodig heeft.

Verder leuk dat je dit script met ons deelt!

Computer
17 jaar geleden

 

0 -0

Ik zal hem sneller proberen te maken, dat wordt versie 2.0! Bedankt vaar de linkjes.

Edit:
Dat met de wortel zit erin, is inderdaad een heel stuk sneller!

Edit 2:
Nu dat met de wortel erin zit, zegt hij bijvoorbeeld bij de input 2451245 gewoon 5. Iemand enig idee hoe dit kan?

Pim -
17 jaar geleden

 

0 -0

Ik zou dit eerlijk gezegd echt niet met PHP gaan doen, erg langzaam bij dit soort berekeningen...

EDIT: Btw, is dit niet veel simpeler?

Code (php)

1
2
3
4
5
6
7
8
9
10
11
12
13

<?php

$n = $s = 1203981;
$array = array();
for($i = 2; $n != 1; $i++) {
    while($n % $i == 0) {
        $n /= $i;
        $array[] = $i;
    }
}

print_r($array);
?>

EDIT 2: En ik wil echt niet lullig zijn, maar dit is ca. 3-10x zo snel en die van jou geeft eigenlijk niet altijd de goede output, de laaste factor wordt niet geoutput.

Computer
17 jaar geleden

 

0 -0

@ Pim

Je hebt gelijk, ik heb er nooit aan gedacht om het zo te doen.

Pim -
17 jaar geleden

 

0 -0

Zonde van al dat werk ;)

Computer
17 jaar geleden

 

0 -0

Ach, zo gaat dat nu eenmaal...

toby hinloopen
17 jaar geleden

 

0 -0

Waarom zou je zoiets nodig hebben?

Joris van Rijn
17 jaar geleden

 

0 -0

Project Euler.

Ruud Verbij
17 jaar geleden

 

0 -0

@toby hinloopen: het kraken van RSA bijvoorbeeld
Binnen de cryptografie en binnen de discrete wiskunde zijn talloze voorbeelden te vinden voor praktisch nut hiervan.

17 jaar geleden

 

0 -0

Als je RSA of weet ik veel wat voor ander iets wilt kraken zou ik eerder een echte programmeertaal gebruik die zo dicht mogelijk bij machinetaal zit om te zorgen dat het programma zo snel en efficient mogelijk loopt. Dus niet een of andere scripttaal die dan nog door een parser moet worden omgebouwd en dan nog eens onefficient moet worden uitgevoerd.
Ik weet bijvoorbeeld dat als je Lisp gebruikt, dat je binnen een paar microseconde (of nog minder) al hebt kunnen uitrekenen of het getal een priemgetal is of niet.
In php zal dat wel langer duren.

Ruud Verbij
17 jaar geleden

 

0 -0

@Karl: uiteraard is PHP niet de manier om dat te doen. Het is wel leuk om wat probeersels te doen in PHP, het programmeert lekker makkelijk en snel weg.
Hoeveel tijd doden wij niet met nutteloze programmaatjes bouwen in PHP?
Lisp lijkt me inderdaad een goede keuze. Met enige kennis zou ik overigens altijd adviseren het te schrijven in assembly, alhoewel dat wel behoorlijk wat tijd, energie en humeur zal kosten :)

PHP hulp
0 seconden vanaf nu

 

Gesponsorde koppelingen

Computer
17 jaar geleden

 

0 -0

Jah, assembly, ik heb er wel eens een meerkleurig ledje mee gemaakt waarbij kleuren in elkaar overgaan, maar dat is veel werk... Bijvoorbeeld het PHP commando

Code (php)

1
2
3

<?php
$wortel2 = sqrt(2);
?>

vertaalt zich al naar heeel veel assembly commando's (er zijn er ook maar een paar)