web analytics

Math Time 1: Priemgetallen (Deel 1)

In onze nieuwe artikelenreeks Math Time gaan we steeds enkele wiskundige problemen bekijken en proberen op te lossen met onze computer. Elke Math Time bestaat uit enkele delen die handelen over hetzelfde onderwerp. Wanneer een onderwerp dan volledig afgewerkt is , ga ik een volledig rapport publiceren zodat je duidelijk kan zien wat ik gedaan heb en wat m’n bevindingen zijn.

Voor de eerste Math Time gaan we even in detail naar priemgetallen kijken. Ik ga proberen om het 1 miljardste priemgetal zo snel en efficiënt mogelijk te vinden.

Om te beginnen begin ik met te zoeken naar een geschikte programmeertaal waarin ik me thuis voel. M’n oog valt op Java omdat ik deze taal redelijk beheers en omdat ik de Eclipse IDE makkelijk werken vind in combinatie met Java.

De eerste poging die we ondernemen om het gevraagde priemgetal te vinden is helemaal niet elegant en werkt op een soort van brute force-methode. Dit wil zeggen dat het gebruikte algoritme eigenlijk alle getallen van 2 tot een zelfgekozen bovengrens gaat controleren op de eigenschappen van priemgetallen. Dit heeft als voordeel dat het algoritme zelf makkelijk te ontwikkelen is, maar het grote nadeel is de snelheid. De snelheid neemt steeds verder af, naarmate er meer priemgetallen gevonden zijn. Hieronder zie je nu de code die ik geschreven heb om op deze manier priemgetallen te ontdekken:

public class Main {

    public static void main(String[] args) {
    long time1=0;
    long time2=0;
    long tottime=0;
    time1=System.currentTimeMillis();
    int i=2;
    int a=3;
    int b=2;
    while (b<=50000){
    	while (i<a){
    		if ((a%i)!=0){
    			if (i==(a-1)){
    				b++;
    				a++;
    				i=2;
    				System.out.println("B is nu gelijk aan:"+b);
    				break;
    			}
    			else{
    			i++;
    			}
    		}
    		else{
    			a++;
    			i=2;
    		}
    	}
    }
    System.out.println("Het 50000e priemgetal is:"+(a-1));
    time2=System.currentTimeMillis();
    tottime=time2-time1;
    System.out.println("De berekeningen duurden:"+tottime+"ms");
    }
}

Deze code bestaat eigenlijk uit een paar kleine stukjes die elk hun eigen specifieke functie hebben. We beginnen met enkele variabelen die we nodig hebben om te berekenen hoelang het geduurd heeft om de priemgetallen te vinden. Daarna declareren we nog enkele variabelen die nodig zijn tijdens het zoekproces naar de priemgetallen. b is de huidige index, met andere woorden b toont ons tijdens het zoekproces hoelang het nog duurt eer we onze uitkomst kunnen verwachten. a is het eigenlijke priemgetal en i is een rangtelnummer.

Bij het testen van dit algoritme werd het al gauw duidelijk dat dit helemaal niet geschikt is om 1 miljard priemgetallen te vinden, daarvoor moeten we verder zoeken naar betere methodes. Om een vergelijking in snelheid te ontdekken heb ik al 50000 priemgetallen opgezocht. Het duurde 77539 ms (77.5 s) in totaal om zoveel priemgetallen te vinden.

In de volgende Math Time gaan we verder op zoek naar een efficiënte manier om priemgetallen te berekenen en gaan we een algoritme schrijven dat steunt op de Zeef van Eratosthenes.

Geschreven door: Pieter Verschaffelt
All Rights Reserved © 2014 IFEMedia http://www.isearchfulledition.com

Leave a Reply

Your email address will not be published. Required fields are marked *