Primes List

[danbaron]

Hi Gang!

Here is a little EB console program that finds prime numbers.

It is similar to the famous method, "the Sieve of Eratosthenes". For our
method, we have patented the name, "the Sleeve of Hercules".

The Sieve operates by finding all of the prime numbers, less than or
equal to some value M. That is, all of the prime numbers in the
interval, 0,1,2, .. ,M.

The Sleeve operates by finding the first N prime numbers.

Here is an example of how (I think) the Sieve operates. Say, you wanted
to find all of the prime numbers, less than or equal to 100. The Sieve
would use an array, P[101], of CHARs. The Sieve determines whether each
index of P[], is prime. If the index is not prime, it sets the value to
0 (FALSE). If the index is prime, it sets the value to 1 (TRUE). So,
P[0], would be set to 0, because 0 is not prime. P[1], would be set to
0, because 1 is not prime. P[2], would be set to 1, because 2 is prime.
P[3], would be set to 1, because 3 is prime, and so on. After all of the
values were set up to P[100], the list of primes would consist of all of
the indexes, with values of 1.

The Sleeve uses an array P[N+1] (for any value N), of UINT64s. It starts
at the beginning, and successively determines each value in the array.
So, first it would determine that P[1], equals 2, the first prime
number. Then, it would determine that P[2], equals 3, the second prime
number. Then, it would determine that P[3], equals 5, the third prime
number, etcetera.

One CHAR, uses 1 byte. One UINT64, uses 8 bytes. The value of the Nth
prime number, is always greater than N. And that difference grows with
N.  You can see, that for small lists, the Sieve uses less memory, and
for large lists, the Sleeve uses less memory. On the other hand,
the rate at which the Sleeve generates new primes, continually
decreases. I didn't time the Sleeve, but on my machine, I think it
generated the first 6 million primes, in less than half an hour.

The program is for the console.

When it starts, maximize the console window.

It is set to print the index and value of every 25000th prime, in the
console window.

You can quit the program at any time, by pressing "ESC".

(My experience is that, if the program quits immediately after it
starts, it means, the value of the program constant, MAXPRIMES, is set
too big.)

Nuf sed.

Best Wishes;
Shemp Howard,
Dan Baron.

Code Select Expand


'-------------------------------------------------------

'FILE = "PRIMESLIST.EBA"

'COMPILE AS "CONSOLE EXE".

'WHEN THE PROGRAM BEGINS, MAXIMIZE THE CONSOLE WINDOW.

'IF THE PROGRAM QUITS IMMEDIATELY AFTER STARTING,
'THEN, SET THE VALUE OF THE CONSTANT, "MAXPRIMES", SMALLER.

'-------------------------------------------------------

CONST MAXPRIMES = 10000000
CONST SHOWINTERVAL = 25000
UINT64 PRIMESLIST[MAXPRIMES + 1]
DOUBLE R
INT N = 2
INT NEXTINT = 3

'-------------------------------------------------------

OPENCONSOLE

SHOWINSTRUCTIONS()

PRIMESLIST[1] = 2
PRIMESLIST[2] = 3

WHILE TRUE

LABEL L1

NEXTINT += 2
R = SQRT(NEXTINT)

FOR I = 2 TO N
IF PRIMESLIST[I] > R THEN GOTO L2
IF NEXTINT % PRIMESLIST[I] = 0 THEN GOTO L1
NEXT I

LABEL L2

N += 1
PRIMESLIST[N] = NEXTINT
IF N % SHOWINTERVAL = 0 THEN SHOWPRIME(N)

IF N = MAXPRIMES THEN SHOWTERMINATION()
IF INKEY$ = CHR$(27) THEN SHOWQUITEARLY()

ENDWHILE
END

'-------------------------------------------------------

SUB SHOWPRIME(INT I)
COLOR 12,0
STRING PC = USING("0########",I)
STRING PV = USING("##########",PRIMESLIST[I])
STRING CS = APPEND$(PC,"    ",PV)
PRINT CS
ENDSUB

'-------------------------------------------------------

SUB SHOWINSTRUCTIONS()
COLOR 11,0
STRING S
PRINT "YOU CAN QUIT THE PROGRAM AT ANYTIME,"
PRINT "BY PRESSING THE 'ESC' KEY."
PRINT
PRINT "PRESS 'ESC' TO QUIT NOW,"
PRINT "OR (ALMOST) ANY OTHER KEY TO BEGIN."
PRINT
WHILE TRUE
S=INKEY$
IF S > CHR$(0) THEN GOTO L3
ENDWHILE
LABEL L3
IF S=CHR$(27)
END
ELSE
RETURN
ENDIF
ENDSUB

'-------------------------------------------------------

SUB SHOWQUITEARLY()
COLOR 11,0
STRING S
PRINT
PRINT "YOU HAVE CHOSEN TO QUIT PREMATURELY."
PRINT "TO DO SO NOW, PRESS THE 'ESC' KEY AGAIN."
PRINT "OR, PRESS (ALMOST) ANY OTHER KEY, TO RESUME EXECUTION."
PRINT
WHILE TRUE
S=INKEY$
IF S > CHR$(0) THEN GOTO L4
ENDWHILE
LABEL L4
IF S=CHR$(27)
END
ELSE
RETURN
ENDIF
ENDSUB

'-------------------------------------------------------

SUB SHOWTERMINATION()
COLOR 11,0
PRINT
PRINT " PROGRAM DONE. PRESS (ALMOST) ANY KEY TO QUIT."
PRINT
COLOR 14,0
PRINT "(THANK YOU FOR COMING, AND SEE YOU AGAIN SOON.)"
WHILE TRUE
IF INKEY$ > CHR$(0) THEN END
ENDWHILE
ENDSUB

'-------------------------------------------------------
'-------------------------------------------------------