101 lines
2.1 KiB
Plaintext
101 lines
2.1 KiB
Plaintext
PROGRAM "longprimes"
|
|
VERSION "0.0002"
|
|
|
|
DECLARE FUNCTION Entry()
|
|
INTERNAL FUNCTION Sieve(limit&, primes&[], count%)
|
|
INTERNAL FUNCTION FindPeriod(n&)
|
|
|
|
FUNCTION Entry()
|
|
DIM numbers&[7]
|
|
numbers&[0] = 500
|
|
numbers&[1] = 1000
|
|
numbers&[2] = 2000
|
|
numbers&[3] = 4000
|
|
numbers&[4] = 8000
|
|
numbers&[5] = 16000
|
|
numbers&[6] = 32000
|
|
numbers&[7] = 64000
|
|
numberUpperBound% = UBOUND(numbers&[])
|
|
DIM totals%[numberUpperBound%]
|
|
DIM primes&[6499]
|
|
PRINT "Please wait."
|
|
PRINT
|
|
Sieve(64000, @primes&[], @primeCount%)
|
|
DIM longPrimes&[primeCount% - 1] ' Surely longCount% < primeCount%
|
|
longCount% = 0
|
|
FOR i% = 0 TO primeCount% - 1
|
|
prime& = primes&[i%]
|
|
IF FindPeriod(prime&) = prime& - 1 THEN
|
|
longPrimes&[longCount%] = prime&
|
|
INC longCount%
|
|
END IF
|
|
NEXT i%
|
|
count% = 0
|
|
index% = 0
|
|
FOR i% = 0 TO longCount% - 1
|
|
IF longPrimes&[i%] > numbers&[index%] THEN
|
|
totals%[index%] = count%
|
|
INC index%
|
|
END IF
|
|
INC count%
|
|
NEXT i%
|
|
totals%[numberUpperBound%] = count%
|
|
PRINT "The long primes up to"; numbers&[0]; " are:"
|
|
PRINT "[";
|
|
FOR i% = 0 TO totals%[0] - 2
|
|
PRINT STRING$(longPrimes&[i%]); " ";
|
|
NEXT i%
|
|
IF totals%[0] > 0 THEN
|
|
PRINT STRING$(longPrimes&[totals%[0] - 1]);
|
|
END IF
|
|
PRINT "]"
|
|
PRINT
|
|
PRINT "The number of long primes up to:"
|
|
FOR i% = 0 TO numberUpperBound%
|
|
PRINT FORMAT$(" #####", numbers&[i%]); " is"; totals%[i%]
|
|
NEXT i%
|
|
END FUNCTION
|
|
|
|
FUNCTION Sieve(limit&, primes&[], count%)
|
|
DIM c@[limit&]
|
|
FOR i& = 0 TO limit&
|
|
c@[i&] = 0
|
|
NEXT i&
|
|
' No need to process even numbers
|
|
p% = 3
|
|
n% = 0
|
|
p2& = p% * p%
|
|
DO WHILE p2& <= limit&
|
|
FOR i& = p2& TO limit& STEP 2 * p%
|
|
c@[i&] = 1
|
|
NEXT i&
|
|
DO
|
|
p% = p% + 2
|
|
LOOP UNTIL !c@[p%]
|
|
p2& = p% * p%
|
|
LOOP
|
|
FOR i& = 3 TO limit& STEP 2
|
|
IFZ c@[i&] THEN
|
|
primes&[n%] = i&
|
|
INC n%
|
|
END IF
|
|
NEXT i&
|
|
count% = n%
|
|
END FUNCTION
|
|
|
|
' Finds the period of the reciprocal of n&
|
|
FUNCTION FindPeriod(n&)
|
|
r& = 1
|
|
period& = 0
|
|
FOR i& = 1 TO n& + 1
|
|
r& = (10 * r&) MOD n&
|
|
NEXT i&
|
|
rr& = r&
|
|
DO
|
|
r& = (10 * r&) MOD n&
|
|
INC period&
|
|
LOOP UNTIL r& = rr&
|
|
END FUNCTION period&
|
|
|
|
END PROGRAM
|