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