web analytics

Math Time 1: Priemgetallen (Deel 2)

In deel 2 van onze eerste Math Time die over priemgetallen gaat, gaan we op zoek naar een goede interpretatie van de Zeef van Eratosthenes en gaan we hiervoor een nieuw algoritme schrijven. Groot verschil tussen de werking van dit en het vorige algoritme is het feit dat we nu een bovengrens moeten bepalen, dus met andere woorden moeten we ons algoritme vertellen tot waar het moet zoeken. Persoonlijk vind ik dit iets minder handig en ga ik ervoor zorgen dat we in deel 3 van deze Math Time hiervoor een oplossing hebben.

De Zeef van Eratosthenes bestaat uit 4 eenvoudige stappen:

1) Stel een gesorteerde lijst op beginnende van 2 tot en met de gewenste bovenlimiet
2) Neem het kleinste getal uit deze lijst
3) Streep alle veelvouden van dit getal door (behalve het getal zelf)
4) Kies nu het eerstvolgende niet-doorstreepte getal en begin terug bij stap 3. Ga door met stap 3 en 4 tot en met de bovenlimiet bereikt is.

Nu gaan we verder met de code. Deze is ongeveer even lang als bij onze brute force aanpak, maar werkt wel veel efficiënter. Ten eerste voeren we enkele variabelen in die we gebruiken om te berekenen hoe lang het duurde om het gevraagde aantal priemgetallen te zoeken. We bereken dit tijdsverschil door in variabele “time1” de huidige tijd in milliseconden op te slaan, na het berekenen van de priemgetallen slaan we ook weer de huidige tijd op in variabele “time2” en berekenen we het verschil tussen “time2” en “time1”.

De variabele “n” staat voor de bovenlimiet en daar moeten we dus invullen tot waar we priemgetallen willen zoeken. Het algoritme zal dus alle priemgetallen tussen 2 en n opsommen. Variabele “q” gebruiken we dan weer om tijdens het rekenen te tellen hoeveel priemgetallen we al gevonden hebben.

De eerste For-loop die je tegenkomt zet alle indices van het array “prime” op true, aangezien arrays standaard op false staan. De tweede For-loop is de daadwerkelijke Zeef van Eratosthenes.

public class Main {
	public static void main(String[] args){
		long time1=0;
		long time2=0;
		long tottime=0;
		time1=System.currentTimeMillis();
		int n=15485864; //De bovenlimiet
		int q=0;   //Hoeveel priemgetallen zijn er?
		boolean[] prime; //Een nieuw array waarin we al onze priemgetallen gaan opslaan
		prime = new boolean[n+1];
		for (int i=2; i<n; i++){	//Het hele array instellen op true, arrays staan standaard op false
			prime[i]=true;				//Later worden niet-priemgetallen op false gezet
		}
		for (int i=2; i<n; i++){	//We maken een nieuwe integer i aan
			if (prime[i]==true){
				System.out.println("I is nu: "+i);	//debug code
				q++;
						for (int z=2; i<n && z*i<n; z++){
							prime[z*i]=false;
						}
			}
		}
		System.out.println("We hebben "+q+" priemgetallen gevonden.");
		time2=System.currentTimeMillis();
	    tottime=time2-time1;
	    System.out.println("De berekeningen duurden:"+tottime+"ms");
	}
}

Met het algoritme van deel 1 duurde het 77.5 seconden om 50000 priemgetallen te zoeken, met dit algoritme duurt dit slechts 0.594 seconden. Dit wil zeggen dat dit algoritme ongeveer 130 keer sneller is dan het vorige. Een grote verbetering, al zeg ik het zelf.

Zo, deel 2 van deze Math Time zit er weeral op. In deel 3 ga ik dit algoritme verbeteren door ervoor te zorgen dat we enkel het aantal priemgetallen dat we willen zoeken moeten opgeven en niet meer te hoeven werken met de bovenlimiet. Ook ga ik kijken of er nog efficiëntere manieren bestaan om priemgetallen te zoeken en gaan we deze proberen implementeren.

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 *