Project Euler 12

nein, wenn der code zu allem vorliegt, kann das jeder bei sich zu hause auf seinem rechner testen und vergleichen und hat somit, da man sein eigenes system kennt, einen guten eindruck davon, wie die einzelnen impementierungen zueinander stehen - !rr!rr_.s zahlen geben einen ersten eindruck davon.

volkard

!rr!rr_. schrieb:

22 millisekunden

mult := [ :n :p || e q | 
	e := 0. q := p.
	[ n \\ q = 0 ] 
		whileTrue: [ 
			e := e+1. 
			q := q*p ]. 
	e+1 ].
primes := Integer primesUpTo: 19.
numberOfDivisors := [ :n | 
	primes 
		inject: 1 into: [ :prod :prime | 
			prod * (mult value: n value: prime) ] ].
run := [ | n | n := 1.
	[ | d | 
		d := numberOfDivisors value: n*(n+1)/2.
		d < 500 ] 
			whileTrue: [ n := n+1 ].
		Transcript  
			show: n asString ].
Time millisecondsToRun: [ run value ].

das Smiley in Zeile 1 steht für "Doppelpunkt p" :xmas2:

Die ersten Primzahlen bis 19 zu berechnen und vorher schon zu wissen, daß man nur 19 braucht, heißt, daß man das Ergebnis schon kennt.
Warum nicht gleich 76576500 anzeigen und fertig?

Außerdem ist bei so wenigen Millisekunden ein Messen kaum noch sinnvoll. Allein das Programm zu starten (neuer Prozess) ist ja schon in dieser Gegend. Oder? Wenn ich den Programmstart herausnehme und die langsame synchrone Ausgabe auf die Konsole und die Primzahlen bis 19 nehme, lande ich mit campers Trick und ohne Michael E.s Trick (der würde nochmal ca Faktor 2 machen) mit C/C++ bei 617µs.

volkard schrieb:

Die ersten Primzahlen bis 19 zu berechnen und vorher schon zu wissen, daß man nur 19 braucht, heißt, daß man das Ergebnis schon kennt.

Gut beobachtet! Das Programm ist schon leicht optimiert. Es liefert die gesuchte Zahl in vernünftiger zeit, das reicht mir.

Ich habe natürlich auch eine Komfort-Version, die kein Wissen über den größten Primfaktor voraussetzt, sondern nach und nach die Primfaktoren bis 2^r zufügt, unter der gut bestätigten Heuristik, daß die gesuchte Zahl aus vielen kleinen Primfaktoren bestehen wird.

Da es 564 Primzahlen < 2^12 gibt, und die gesuchte Zahl schwerlich mehr als 500 verschiedene Primfaktoren haben kann, reicht es, r <= 12 zu untersuchen, der Suchraum ist also nicht allzugroß, und das Programm auch nicht unendlich viel länger unterwegs.

volkard schrieb:

Außerdem ist bei so wenigen Millisekunden ein Messen kaum noch sinnvoll. Allein das Programm zu starten (neuer Prozess) ist ja schon in dieser Gegend. Oder?

Ja - und? dies ist ja auch kein Kolloquium über Meßtechnik :xmas1: 10 ms oder 20 oder 200, merkt man keinen unterschied. Bei 500000 Primteilern wäre das wahrscheinlich anders.