PrimeSum

vodkaz

vodkaz

Mitglied
Hallo erstmal :)
Ich habe gerade das Beispiel 10 von Project Euler geschrieben. Es funktioniert auch nur musste ich gute 30 Minuten warten bis mein PC das ausgerechnet hat.
Hier mal der Code :
Java: 
private static long sumOfPrimes(long numb){
		long sum = 0; 
		long counter = 2; 
		while(true){
			System.out.println(counter);
			if(isPrime(counter)){
				sum+=counter; 
			}
			
			if(counter < numb)counter++; 
			else break; 
		}
		return sum; 

	}

(kurz zusammengefasst das programm soll die summe aller primzahlen zwischen numb ausrechnen ... also wäre numb in diesem beispiel 2000000)

warum dauert es solang bis mein pc das ausrechnet ? ich hab eig nen i7 prozessor(falls das gut ist bin nich so der hardware experte :D ) liegts am code oder braucht mein pc nur sehr lang ?

MfG Vodkaz
 
Zuletzt bearbeitet:
H

Highchiller

Bekanntes Mitglied
Also erst mal geht es darum alle Primzahlen zu finden, die kleiner als 2 Mio sind. Warum nimmst du dann also eine while(true) schleife statt einer for? Du kennst doch start und anfang.

Viel entscheidender ist deine Methode isPrime().
Was glaubst du denn was an deinem Code so lange dauert? Ich kanns dir sagen, diese Methode!

Ich lös das Problem auf meinem Lappy (mit i5 M520 mit 2,4GHz) in 0,8 Sekunden.
 
vodkaz

vodkaz

Mitglied
OK, danke für den Tipp :)
Meine aktuelle Methode is nämlich die hier :
Java: 
private static boolean isPrime(long j){
		for(long i = 2; i<j; i++){
			if(j % i == 0) return false; 
		}
		return true; 
	}

ich versuch die mal zu optimieren :)
 
Zuletzt bearbeitet:
H

Highchiller

Bekanntes Mitglied
Dr. Zoidberg hats schon gesagt. Erst mal musst du nicht bis j überprüfen ob j eine Primzahl ist sondern nur bis Wurzel(i). Also bis i*i < j. Denn es ist offensichtlich dass jede Zahl k für die gilt i*i < k < j kein Teiler mehr von j sein kann.

Und obendrein kannst du i gleich in 2er schritten laufen lassen statt immer nur +1. Denn jede zweite Zahl ist eine Gerade Zahl, und wenn eine Gerade Zahl einer Teiler einer Zahl K ist, so ist auch stets 2 ein Teiler von K.

Kurzum. In 2er schritten (-> nur noch halbsoviele for schleifen) und nur solange i*i < j (also von der Hälfte noch mal die Wurzel ziehen).
Und selbst das ist noch "langsam". Aber im Vergleich zu deinen 30 Minuten schon mal nen riesen Fortschritt.
 
K

klauskarambulut

Bekanntes Mitglied
Code: 
1*2*1*8*8*2*
Time spent: 87 ms

Das Ergebnis möchte ich nicht vorwegnehmen, darum habe ich mal jede zweite Ziffer gesternt.

Das Problem ist die Methode boolean isPrime(long j)

Herauszufinden, dass eine große Primzahl tatsächlich eine Primzahl ist, ist mit ähnlichem Aufwand verbunden, wie alle bisherigen Primzahlen bis zu dieser großen Zahl zu berechnen.

Und das machst du hier für jede Primzahl erneut.


Das Sieb des Erasthoses, geht hier vernünftiger vor. Damit erhält man mit geringerem Aufwand eine Liste von Primzahlen, die man nur noch aufsummieren muß.


Mit den 87 ms bin ich damit etwa 180.000 mal schneller verglichen mit der halben Stunde.
 
L

Lonsdaleit

Aktives Mitglied
Es wurden ja bereits einige Verbesserungen vorgeschlagen.

Ergänzend:
Was das ganze natürlich auch ausbremst ist diese Zeile:
Java: 
System.out.println(counter);

Wenn du 2 Millionen mal deinen counter ausgibst, wirkt das ebenfalls verlangsamend!
Dies ist jedoch nicht der Grund, dass es eine halbe Stunde dauert - es ist nur ein zusätzlich verlangsamender Faktor.

Zum Vergleich:
Java: 
for (int i=0; i<2000000;i++){
	//System.out.println(i);
	i++;
	i--;
}

Ohne Ausgabe: 16ms
Mit Ausgabe: 19080ms

=>Natürlich sind 20 Sekunden zusätzlich im Vergleich zu einer halben Stunde kein Problem, aber wenn du ein Sieb verwendest und somit auf wenige ms für 2 Millionen Durchläufe kommst, fallen die 20 Sekunden wiederum auf:)


Gruß,
Lonsdaleit.
 
Zuletzt bearbeitet:

Aktuelle Jobs

Neue Themen


Oben