Aus Neugier hatte ich das gestern noch mal für alte Hardware nach QBasic portiert und auf meinem DOS-Rechner laufen lassen – lief für die 20.000 Zahlen knapp unter einer halben Minute.
Code: Alles auswählen
DECLARE FUNCTION IsPrime% (n AS INTEGER)
DECLARE FUNCTION IsSumOfTwoPrimes% (n AS INTEGER)
DECLARE FUNCTION AllEvensAreTheSumOfTwoPrimes% (a AS INTEGER, b AS INTEGER)
DIM start AS SINGLE
start = TIMER
IF AllEvensAreTheSumOfTwoPrimes(4, 20000) THEN
PRINT "Juhuu!"
ELSE
PRINT "Ooooh!"
END IF
PRINT "Laufzeit:"; TIMER - start; "Sekunden."
FUNCTION AllEvensAreTheSumOfTwoPrimes% (a AS INTEGER, b AS INTEGER)
DIM n AS INTEGER, result AS INTEGER
result = -1
FOR n = a TO b STEP 2
IF NOT IsSumOfTwoPrimes(n) THEN
result = 0
EXIT FOR
END IF
NEXT
AllEvensAreTheSumOfTwoPrimes = result
END FUNCTION
FUNCTION IsPrime% (n AS INTEGER)
DIM i AS INTEGER, result AS INTEGER
IF n < 2 THEN
result = 0
ELSEIF n = 2 THEN
result = -1
ELSEIF n AND 1 = 0 THEN
result = 0
ELSE
result = -1
FOR i = 3 TO SQR(n) STEP 2
IF n MOD i = 0 THEN
result = 0
EXIT FOR
END IF
NEXT
END IF
IsPrime = result
END FUNCTION
FUNCTION IsSumOfTwoPrimes% (n AS INTEGER)
DIM i AS INTEGER, result AS INTEGER
result = 0
FOR i = 2 TO n \ 2
IF IsPrime(i) THEN
IF IsPrime(n - i) THEN
result = -1
EXIT FOR
END IF
END IF
NEXT
IsSumOfTwoPrimes = result
END FUNCTION
Also flugs ein Sieb nach Eratosthenes dazu programmiert, und es läuft in knapp unter vier Sekunden.
Code: Alles auswählen
DECLARE SUB InitIsPrime ()
DECLARE FUNCTION IsSumOfTwoPrimes% (n AS INTEGER)
DECLARE FUNCTION AllEvensAreTheSumOfTwoPrimes% (a AS INTEGER, b AS INTEGER)
CONST UpperLimit = 20000
DIM start AS SINGLE
DIM SHARED IsPrime(UpperLimit) AS INTEGER
start = TIMER
InitIsPrime
IF AllEvensAreTheSumOfTwoPrimes(4, UpperLimit) THEN
PRINT "Juhuu!"
ELSE
PRINT "Ooooh!"
END IF
PRINT "Laufzeit:"; TIMER - start; "Sekunden."
FUNCTION AllEvensAreTheSumOfTwoPrimes% (a AS INTEGER, b AS INTEGER)
DIM n AS INTEGER, result AS INTEGER
result = -1
FOR n = a TO b STEP 2
IF NOT IsSumOfTwoPrimes(n) THEN
result = 0
EXIT FOR
END IF
NEXT
AllEvensAreTheSumOfTwoPrimes = result
END FUNCTION
SUB InitIsPrime
DIM i AS INTEGER, j AS INTEGER
IsPrime(2) = -1
FOR i = 3 TO UBOUND(IsPrime) STEP 2
IsPrime(i) = -1
NEXT
FOR i = 3 TO SQR(UBOUND(IsPrime)) STEP 2
IF IsPrime(i) THEN
FOR j = i * i TO UBOUND(IsPrime) STEP i
IsPrime(j) = 0
NEXT
END IF
NEXT
END SUB
FUNCTION IsSumOfTwoPrimes% (n AS INTEGER)
DIM i AS INTEGER, result AS INTEGER
result = 0
FOR i = 2 TO n \ 2
IF IsPrime(i) THEN
IF IsPrime(n - i) THEN
result = -1
EXIT FOR
END IF
END IF
NEXT
IsSumOfTwoPrimes = result
END FUNCTION
Interessant an BASIC ist hier die Entscheidung für Funktionsaufrufe und Arrayzugriffe die gleiche Art von Klammern zu verwenden, so das man beim Wechsel von einer `IsPrime`-Funktion zu einem `IsPrime`-Array mit vorberechneten Ergebnissen an den Aufrufen, bzw. dann Zugriffen, nichts ändern muss.