[link] Project Euler - Programmieraufgaben

Cyberm@ster · Jan 14, 2007

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

When new problems are added to the database they are initially worth 20 points. However, each time a problem is solved by a registered user, it reduces slightly in value.

Project Euler

CraHack · Jan 14, 2007

KLasse Seite! Danke für den Link.

Edit: Hmpf kaum hab ich 5 Probleme gelöst, schmiert die Datenbank ab.

Edit2: Jetzt gehts wieder

Eydeet · Jan 14, 2007

Die Seite ist echt gut.
Ich warte nur immer noch darauf, dass mein PC die Summe aller Primzahlen von eins bis eine Millionen ausgerechnet hat.^^ Ich bin jetzt nach ca. einer halben Stunde erst bei Nr. 70 000, und das ganze geht natürlich immer langsamer, je größer die Zahlen werden. Ich hab nur Angst, dass ein unsigned long das Ergebnis gar nicht speichern kann. Naja, für mich ist die Aufgabe jedenfalls gelöst, theoretisch klappt es ja

Obwohl, ich merke gerade, dass ich nicht die Summe der ersten Millionen Primzahlen suchen muss, sondern abbrechen soll, sobald die Summe 1 Millionen übersteigt. Lesen sollte man können

Die ersten Aufgaben sind auf jeden Fall nicht sonderlich schwer, und prima für Anfänger und Fortgeschrittene geeignet. Bei Aufgabe 137 bin ich noch nicht angekommen, aber der Schwierigkeitsgrad scheint zu steigen.

lagalopex · Jan 15, 2007

WOW! Das ist mal eine richtig gute Seite 8o
Wirklich gute Aufgaben und schön nach Anzahl der Lösungen sortiert (ist wohl auch ein grober Anhaltspunkt für die Schwierigkeit).
Ganz ohne mathematisches Verständnis gehts wohl nicht, aber vieles ist ja zumindest mal ausreichend erklärt.

Hab erstmal bei den einfachereren angefangen aber bin jetzt schon "10% genius" 8)
*weiter-machen-muss*

Janus · Jan 15, 2007

nochma falsch, junge, du sollst die summe aller geraden Fibo-Zahlen suchen, die selbst nicht größer als eine Million sind

Eydeet · Jan 15, 2007

"Find the sum of all the primes below one million" heißt doch, dass man alle Primzahlen, die 1 Millionen nicht überschreiten, zusammenrechnen soll, oder? Wie soll man eine so große Variable speichern? Außerdem sollen normale Computer nach Aussage der Seite maximal 1 Sekunde an einer Aufgabe zu rechnen haben...

Naja, ich denke, man merkt, dass ich Anfänger bin, auch was Englisch angeht...

Gnome · Jan 15, 2007

Original von Eydeet
"Find the sum of all the primes below one million" heißt doch, dass man alle Primzahlen, die 1 Millionen nicht überschreiten, zusammenrechnen soll, oder? Wie soll man eine so große Variable speichern?

Wie wärs mit dem Datentyl long?

Außerdem sollen normale Computer nach Aussage der Seite maximal 1 Sekunde an einer Aufgabe zu rechnen haben...

"obtained on a modestly powered computer in less than one minute (see note). "

Cyberm@ster · Jan 15, 2007

"of the primes below one million"

@ Eyedeet:

Das bezieht sich imho auf die Primzahl p < 10 ^ 6 und nicht auf die Summe, und ich würde eine halbe Stunde Rechenzeit auch nicht unbedingt als gelöst betrachten.

@ Janus:

Das mit den Fibonacci Zahlen ( 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 ... ) ist so auch nicht richtig. 1, 8 & 21 sind schon mal keine Primzahlen ( 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 ...), ausserdem vergisst du damit die 7. Sind halt zwei verschiedene Paar Schuhe.

http://de.wikipedia.org/wiki/Primzahl
http://de.wikipedia.org/wiki/Fibonacci-Folge

Digi · Jan 15, 2007

Klasse Seite, danke für den Link.

Ich mache die Aufgaben mit Mathematika, deshalb sind einige Probleme einfacher, wie z.B.
Problem 16

Code:

Total[RealDigits[2^1000][[1]]]

Mich interessiert nun, wie man denn diese Aufgabe ansonsten lösen würde, mir fällt momentan keine andere Lösung ein ausser eigene Variablentypen zu verwenden. (Die Zahl hat 302 Stellen). Habt ihr eine Idee?

Achja, ich will hier nicht unbedingt Mathematica empfehlen, da ich schon auf eine Aufgabe gestossen bin(und ich habe erst ein paar angeschaut/gemacht), bei der Mathematica zu lange braucht. (Vielleicht habe ich auch einen falschen Ansatz, aber mal schauen wie schnell es in C gehen wird..)

Cyberm@ster · Jan 15, 2007

Ich denke Mathematica, Derive & Co. sind ganz schön um das Problem zu analysieren, Ansätze zu finden und Resultate zu vergleichen, mehr aber auch nicht. Es geht schliesslich drum, ein eigenes Programm zu schreiben, und nicht darum ein bestehendes zu benutzen. Der Weg ist das Ziel! Damit will ich sagen, dass die Entwicklung des Algorithmus' bzw. das Coden des Programms und das was man dabei lernt bei Weitem wichtiger sind, als das "nackte" Resultat!

Digi · Jan 15, 2007

Die Aufgaben, die ich bisher gemacht habe, wären genau gleich in anderen Programmiersprachen gegangen, bis auf eben Problem 16. Das will ich eben auch anders lösen. Und wie ich sehe, wird man später auch keinen grossen Vorteil mehr haben, da es dann nicht mehr so sehr um grosse Zahlen geht. (Bin erst am Anfang, könnte mich als irren

).
Mathematica und andere ähnliche Programme werden auch in der Liste der Programmiersprachen aufgelistet, also glaube ich kaum, dass man mit solchen Programme keine Arbeit hat. (Am Anfang anscheinend weniger.)

Edit: Ich glaube, ich habe eine zweite Alternative für Problem 16 gefunden.

Janus · Jan 16, 2007

lol @Cyberm@ster:

Mir is grad ein Verständnisfehler bei mir aufgefallen ^^ ich hab von der falschen aufgabe geredet

und ich weiß natürlich, dass keine Primzahlen sind, junge, ich studier Mathe

ich war bei der aufgabe, die die summe aller geraden Fibo-Zahlen errechnet, und die größte Fibo-Zahl in der Summe soll nicht größer als 1 Mio sein ^^

und die summe aller primzahlen war nicht wirklich schwer und hat vielleicht 5min gebraucht, was hastn du für nen rechner?

Cyberm@ster · Jan 16, 2007

Eyedeet schrieb:

Ich bin jetzt nach ca. einer halben Stunde erst bei Nr. 70 000, und das ganze geht natürlich immer langsamer, je größer die Zahlen werden. Naja, für mich ist die Aufgabe jedenfalls gelöst, theoretisch klappt es ja

Das hab ich mir schon gedacht Janus, ich wollte es nur klarstellen, und wenn schon, dann auch richtig. Das hat nichts damit zu tun, dass ich an dir oder deinem Wissen zweifele

Ich hab halt gedacht, dass die Informationen vielleicht mal für jemanden nützlich sein könnten.

Eydeet · Jan 16, 2007

Ich hab den Algorithmus nochmal überarbeitet und hab jetzt nach ca. 15 Minuten Rechenzeit die Lösung

Als Datentyp musste ich "unsigned long long" nehmen.

@Janus: Ich hab einen AMD Athlon XP 2500+ (auf 2014 MHz getaktet)

CDW · Jan 16, 2007

jetzt nach ca. 15 Minuten Rechenzeit die Lösung

ein simpler Algo in Java:

Code:

public static void main(String[] args) 
{		
	BigInteger primzahl = BigInteger.valueOf(2);
	BigInteger summe=BigInteger.ZERO;
	int primcounter=0;
	long time=System.currentTimeMillis();
	do
	{
	      summe=summe.add(primzahl);
	      primcounter++;
	      primzahl=primzahl.nextProbablePrime();	
	}while (primzahl.compareTo(BigInteger.valueOf(1000000))==-1);
		
	System.out.println("Summe: "+summe.toString()+" Anahl der Primzahlen:" 
			+ primcounter+" , benötigte Zeit: " 
			+(System.currentTimeMillis()-time)/1000+ " Sekunden" );	
	
		
}

Summe: 3755xxxx023 Anahl der Primzahlen:78498 , benötigte Zeit: 63 Sekunden

Und das mit BigIntegers (Klasse für beliebiggroße Zahlen) auf einem alten P4 1.92 GHZ

Ich versuche es gleich mal mit "normalen" Datentypen.

Edit: ohne BigIntegers und mit "Eigenimplementierung" des Primzahltests:

Summe: 375xxxxx023 Anahl der Primzahlen:78498 , benötigte Zeit: 4 Sekunden

Code:

public static boolean prim(long zahl)
{
	for (int i=3;i<=Math.sqrt(zahl);i=i+2)
	  if (zahl%i==0)return false;
		  
	return true;
}

public static long nextPrim(long zahl)
{
       while (!prim(zahl=zahl+2));    	       	
       return zahl;
}

public static void main(String[] args) 
{		
	long primzahl = 3;  //starten mit 3
	long summe=2;      //bisschen mogeln - die 2 wurde schon "addiert"
	int primcounter=1;  // deswegen wurde schon eine Primzahl "gefunden"
	long time=System.currentTimeMillis();
	do
	{
	     summe=summe+primzahl;
	     primcounter++;
	     primzahl=nextPrim(primzahl);		   	
	}while (primzahl<1000000);
		
	System.out.println("Summe: "+summe+" Anahl der Primzahlen:" 
				+ primcounter+" , benötigte Zeit: " 
				+(System.currentTimeMillis()-time)/1000+ " Sekunden" );	
	
		
}

Eydeet · Jan 16, 2007

So, ich habe wieder mal meinen Algo verbessert. Das sieht dann doch ein wenig blöd aus, wenn meiner 5 Minuten braucht

Ich hab auf jeden Fall ne Menge dabei gelernt, auch wenn der Code vielleicht etwas kurz erscheint

Anzahl: 78498 Summe: 375xxxxxx23 Laufzeit: 1.16 Sekunden

Code:

#include <iostream>
#include <cmath>
using namespace std;

bool isprime(unsigned long long num) {
    int i;
    for(i=3; i<sqrt(num)+1; i+=2)
        if(num % i == 0) return false;
    return true;
}

int main() {
    int test=3,counter=1;
    unsigned long long sum=2;
    double time1=clock(), time2;
    while(test < 1000000) {
        if(isprime(test)) {
            sum += test;
            counter++;
        }
        test += 2;
    }
    time2 = (clock() - time1) / CLOCKS_PER_SEC;
    cout << "Anzahl: " << counter << " Summe: " << sum << " Laufzeit: " << time2 << " Sekunden" << endl;
}

Lesco · Jan 16, 2007

Man kann auch noch ein bisschen was an Geschwindigkeit rausholen, wenn man statt jedesmal zu prüfen, ob eine Zahl prim ist oder nicht, einfach ein entsprechendes Sieb verwendet, wie z.B. Atkins Sieb: http://en.wikipedia.org/wiki/Sieve_of_Atkin

lumax · Jan 16, 2007

Jap, sowas hab ich auch gemacht (allerdings auf Basis des Sieb des Eratosthenes, das von Atkin kannte ich gar nicht

). Mein C-Code braucht damit selbst auf der 666 Mhz-Gurke im Keller weniger als 'ne halbe Sekunde.

Edit:
Hat jemand 'nen brauchbaren Ansatz fuer Aufgabe 14? Bruteforcen bringt's da nicht wirklich, da rechnet man ewig dran.

CDW · Jan 17, 2007

nfach ein entsprechendes Sieb verwendet, wie z.B. Atkins Sieb

Atkins Sieb mag zwar theoretisch eine bessere Laufzeit als Eratosthenes haben (O(N/log log N) anstatt O(N)) aber bei praktischer Umsetzung ist die O-Notationskonstante imho recht happig (wegen der Gleichungengen).

Zum Javacode:
Hab mal den Java-Code auf meinem Rechner laufen gelassen ( 3,5 Jahre alter P4 mit 3 Ghz -> benötigte Zeit: 1.953 Sekunden)

Allerdings ist Sieb des Eratosthenes um einiges schneller:0.083s -> 83ms

Code:

.386 
.model flat,stdcall 
option casemap:none 

include \masm32\include\windows.inc 
include \masm32\include\user32.inc 
include \masm32\include\kernel32.inc 
include \masm32\include\winmm.inc
include \masm32\include\masm32.inc

includelib \masm32\lib\masm32.lib
includelib \masm32\lib\winmm.lib
includelib \masm32\lib\user32.lib 
includelib \masm32\lib\kernel32.lib 

MAX_SIZE equ 1000000
NOT_PRIM equ 0

.data 
format db"Summe: %s, Zeit:%d ms",0

.data? 
summe dq ?
primarray dd ?
zeit dd ?
outbuffer db (256) dup (?)
summe_string db (256) dup (?)  

.code 
 
start:    
    ;Speicher reservieren, os abhängig, 0-initialisierung wird vorausgesetzt
    invoke VirtualAlloc,0,MAX_SIZE*sizeof DWORD,MEM_COMMIT,PAGE_EXECUTE_READWRITE
    mov primarray,eax
    ;zeitmessung
    invoke timeBeginPeriod,1 ;genauigkeit der Zeitmessung auf 1 ms setzten
    invoke timeGetTime
    mov zeit,eax
    
    
    ;array füllen
    mov esi,primarray
    mov ecx,MAX_SIZE-(1-MAX_SIZE MOD 2)  ;Macroanweisungen, damit nicht ünnötig alle vielfachen von 2 gefüllt werden
    fill_loop:
      mov dword ptr [esi+ecx*4],ecx
    sub ecx,2
    jns fill_loop
    
    ;Summe wird  in ebx,edx gezählt, wobei ebx=niederwertiges DWORD, edx=höherwertiges DWORD
    ;vorteil gegenüber FPU Nutzung: ca. 1/5 Perfomancegewinn
    mov ebx,2 ;initialisiere mit 2
    mov edx,0
    mov ecx,3 ;index steht jetzt auf 3 (beginne mit der Primzahl 3)
    ;aussieben
    sive_loop:
      mov edi,[esi+ecx*4]
      mov eax,edi
      imul edi,edi      
      
      cmp edi,MAX_SIZE
      jg nearly_finished
      
      flag_loop:
        mov dword ptr[esi+edi*4],NOT_PRIM  
        add edi,eax
      cmp edi,MAX_SIZE
      jb flag_loop
      
      ;jetzt nach der nächsten Primzahl scannen und gleich die Summe bilden
      add ebx,[esi+ecx*4]
      adc edx,0
      scan_loop:        
         add ecx,2
      cmp dword ptr [esi+ecx*4],NOT_PRIM
      je scan_loop
      
    jmp sive_loop  
         
    nearly_finished:
    ;rest zusammenzählen          
      
      cmp dword ptr [esi+ecx*4],NOT_PRIM
      jz noadd
      add ebx,[esi+ecx*4]
      adc edx,0
    noadd:  
    add ecx,2
    cmp ecx,MAX_SIZE
    jb nearly_finished
    
    ;ergebnis speichern
    mov dword ptr [summe+4],edx
    mov dword ptr [summe],ebx
    
    ;zeit messen,ausgeben und weitere OS abhängige Sachen:
    invoke timeGetTime   
    sub eax,zeit
    mov zeit,eax
    fild qword ptr [summe]
    fstp qword ptr [summe]
    invoke FloatToStr2,qword ptr [summe],offset summe_string  ;Funktion aus der MASM Lib
    invoke wsprintf,offset outbuffer,offset format,offset summe_string,zeit
    invoke MessageBox,0,offset outbuffer,0,0
    
    retn

end start

Hat jemand 'nen brauchbaren Ansatz fuer Aufgabe 14? Bruteforcen bringt's da nicht wirklich, da rechnet man ewig dran

Hm, bei mir dauert es ca 6 Sek. (wieder Java, nichts optimiertes, allerdings keine Rekursive Sequenzbildung (auch wenns schöner aussieht

)

Code:

variablen: 
len=1 und nummer

Solange nummer>1
    ist nummer gerade->nummer=nummer/2; sonst nummer=nummer*3+1;
   // d.h wir bilden jedesmal eine neue Nummer, solange diese >1 ist ->also bei jeder Bildung mitzählen
      len++   ;

am Ende steht in len die Sequenzlänge.

PS: mit 
 variable&1 (Bitweise AND Verknüpfung) kann man testen, ob das niedrigste  Bit eines Werts gesetzt ist - >wenn nein, ist der Wert gerade (dadurch spart man sich die Division)

der Startwert len=1 kommt daher, da man ja auch die erste nummer (mit der man beginnt) zählen sollte
Und für die variable "nummer" sollte man nicht allzukleinen Datentyp wählen

lumax · Jan 17, 2007

Argh, bin jetzt selber drauf gekommen, war ein ziemlich dummer Bug. Mein Ansatz war richtig, ich hab bloss irgendwie verpennt, dass die Zahl ziemlich gross werden kann. Das Ganze resultierte dann in 'nem Integer Overflow, wodurch ich negative Zahlen hatte. Da ich nicht auf > 1, sondern auf != 1 getestet habe, hat der also immer munter weitergerechnet. Mit 'nem groesseren (und unsigned) Datentyp funktioniert's. Trotzdem danke.

Daran, & 1 statt % 2 zu machen, hab ich nicht gedacht, interessanterweise macht das aber im Endeffekt keinen Unterschied in der Laufzeit. Ich vermute mal, der gcc setzt fuer % 2 eh schon & 1 ein (aber ich kann's nicht ueberpruefen, weil ich leider kein bisschen Asm kann).