Hoe ontbind je een groot getal in priemfactoren?

Ik weet niet echt hoe ik het aan moet pakken. Als je bijvoorbeeld het getal 640 hebt, dan kan je toch niet eindeloos blijven proberen tot er eentje goed is? Is er niet een snelle manier om grote getallen te ontbinden in priemfactoren?

Weet jij het antwoord?

/2500

Het beste antwoord

Begin altijd met het kleinste priemgetal (2 dus) en ga door tot die niet meer kan. Neem dan de volgende (3) en dan ook weer net zo vaak tot het niet meer kan. Zo steeds verder. Voorbeeld: 640 : 2 = 320 320 : 2 = 160 160 : 2 = 80 80 : 2 = 40 40 : 2 = 20 20 : 2 = 10 10 : 2 = 5 5 is een priemgetal, dus die kun je niet meer delen. Dus: 640 = 2x2x2x2x2x2x2x5

Dit is een interessante vraag waarover menig wiskundige zich het hoofd heeft gebroken. De algoritmes om priemontbinden te vinden zijn momenteel niet veel beter dan brute force en evenzo is het bepalen van priemfactoren. Voor relatief kleine getallen zoals 640 bestaan er natuurlijk trucs, zie bijvoorbeeld http://math.about.com/library/bldivide.htm Hierbij kun je opmerken dat als 640 = a*b, dan zal een van beide factoren kleiner zijn dan sqrt(640)=25,2... en de ander groter. Dus bij het zoeken naar factoren hoef je alleen naar alle mogelijk priemfactoren onder de 25 te kijken. Wanneer de getallen zo groot worden dat handmatige berekeningen ondoenlijk zijn, dan zijn er altijd nog computers waar je je toe kunt richten. Probeer maar eens een groot geheel getal in Wolfram Alpha in te voeren ( http://www.wolframalpha.com ). Onder het kopje "Prime factorization" komt je ontbinding te staan. Het feit dat ontbinding in priemfactoren zo'n lastig probleem is wordt uitvoerig gebruikt in de cryptografie. Kijk hiervoor maar eens op http://en.wikipedia.org/wiki/RSA_%28algorithm%29

Bronnen:
http://en.wikipedia.org/wiki/RSA_%28algorithm%29
http://math.about.com/library/bldivide.htm
http://www.wolframalpha.com

Stel zelf een vraag

Ben je op zoek naar het antwoord op die ene vraag die je misschien al tijden achtervolgt?

/100