Project Euler Problem 10

Hallo,

ich versuche mich gerade am Project Euler und versage dort bereits an der 10. Aufgabe.
Der Code von mir funktioniert fehlerlos, jedoch nur bis ca. i = 300000. Mein Code müsste also ihrgendwie optimiert und verändert werden. Ich weiß jedoch nicht, an welchen Stellen im Code ich noch etwas herausholen könnte. (Laut Project Euler sollen die Berechnungen nicht mehr als 1 Minute dauern!)

#include <iostream>
#include <inttypes.h>

using namespace std;

int main ()
{
	uint64_t sum = 5; // 64bit Zahl
	bool prime = true;

	for (int i = 5; i<=2000000; i+=2)
	{
		prime = true;

		for (int j = 3; j < i; j+=2)  // Überprüft, ob Primzahl
		{
			if (i % j == 0)
			{
				prime = false;
				break;
			}

		}

		if (prime == true) // Wenn Primzahl summe+primzahl
			sum += i;

	}

	cout << sum;
}

Grüße,
Kartoffel

HighLigerBiMBam

Du kannst j <= i / 3 versuchen. Spart immerhin 60% sinnloses prüfen

So klappts bei mir unter einer Minute:

#include <iostream>

using namespace std; 

int main () 
{ 
    __int64 sum = 5; // 64bit Zahl 

    for (int i = 5; i<=2000000; i+=2) 
        for (int j = 3; j <= i / 3; j+=2)
            if (i % j == 0) 
            { 
                sum += i; 
                break; 
            }

    cout << sum; 
}

SG1

Oder bis zur Wurzel.

Threads zur Primzahlbestimmung gibt's hier im Forum übrigens wie Sand am Meer. Einfach mal suchen.

krümelkacker

Ich werde auch nichts zur Primzahlberechnung sagen, nur folgendes

prime    prime==true
--------------------
false       false
true        true

"prime==true" liefert denselben Wahrheitswert wie den, der in prime gespeichert ist.

padreigh

http://www.primzahlen.de/ Links im Menue: Primzahlentest(s)

krümelkacker schrieb:

"prime==true" liefert denselben Wahrheitswert wie den, der in prime gespeichert ist.

Ich dachte das wäre nur etwas "designtechnisches" und es wäre egal, wie ich das schreibe.
Mein Lehrer in der Schule meinte, dass wir das immer "prime == true" schreiben sollen anstatt "prime".

Und nochmal ein großes Danke an euch, habe es nun mit der Wurzel gelöst

Kartoffel schrieb:

Mein Lehrer in der Schule meinte, dass wir das immer "prime == true" schreiben sollen anstatt "prime".

Hat er zufällig auch gesagt warum?

Kartoffel schrieb:
Mein Lehrer in der Schule meinte, dass wir das immer "prime == true" schreiben sollen anstatt "prime".

Hat er zufällig auch gesagt warum?

Tut doch jetzt nicht so. Ihr kennt doch selbst die Antwort (auch wenn ihr, aus angeberei oder was weiß ich, vorgibt sie nicht zu kennen).

Werner Salomon

Kartoffel schrieb:

ich versuche mich gerade am Project Euler und versage dort bereits an der 10. Aufgabe.
Der Code von mir funktioniert fehlerlos, jedoch nur bis ca. i = 300000. Mein Code müsste also ihrgendwie optimiert und verändert werden. Ich weiß jedoch nicht, an welchen Stellen im Code ich noch etwas herausholen könnte. (Laut Project Euler sollen die Berechnungen nicht mehr als 1 Minute dauern!)

Das liegt wohl daran, dass Dein Algorithmus eine Komplexität von O(n^2) hat. Das heißt, wenn er für eine Obergrenze N 10s benötigt, so benötigt er für für 2*N nicht das doppelte sondern das vierfache der Zeit.

Beherzige den Rat von SG1 und begrenze die Suche auf die Wurzel. Ersetze in Deinem Code die Zeile 15 durch

int ende = sqrt( double(i) ); // erfordert #include <cmath>
        for (int j = 3; j <= ende; j+=2)  // Überprüft, ob Primzahl

, dann ist die Komplexität O(N*log(N)) und die Laufzeit deutlich unter einer Minute.

Noch schneller wrst Du mit dem Sieb des Eratosthenes

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    using namespace std;
    const size_t N = 2000000;
    long long sum = 0;
    vector< bool > sieb(N, true);
    for( vector< bool >::iterator prim = sieb.begin()+2; (prim = find( prim, sieb.end(), true )) != sieb.end(); ++prim )
    {
        int Prim = prim - sieb.begin();
        sum += Prim;
        // --   Sieb des Eratosthenes
        for( size_t idx = 2*Prim; idx < sieb.size(); idx += Prim )
            sieb[ idx ] = false; // idx ist Vielfaches von Prim, also keine Primzahl
    }
    cout << "Summe aller Primzahlen bis " << N << " ist " << sum << endl;
    return 0;
}

das braucht nur den Bruchteil einer Sekunde.

Gruß
Werner

krümelkacker

Werner Salomon schrieb:

Beherzige den Rat von SG1 und begrenze die Suche auf die Wurzel. Ersetze in Deinem Code die Zeile 15 durch
int ende = sqrt( double(i) ); // erfordert #include <cmath>
        for (int j = 3; j <= ende; j+=2)  // Überprüft, ob Primzahl
, dann ist die Komplexität O(N*log(N)) und die Laufzeit deutlich unter einer Minute.

Meinst Du nicht eher O(N^1.5) ?

Es ist schon so, die Asymptote von ∑_1<k<n√k gleich n^1.5/1.5 entspricht. Ungefähr n/lnn Zahlen davon sind Primzahlen. Es kann also nicht gesagt werden, dass die Wahrscheinlichkeit, dass ein i gerade Teiler von k ist, konstant ist. Kennst du irgendeinen Beweis, der die Laufzeitkomplexität von dieser groben Methode als O(N^1.5) klarstellt?