_max = 1000001
uint32 primeList( 80000 )

clear local fn makePrimeList
  // Creates list of primes using Sieve of Eratosthenes
  // with a bitmap of odd integers
  uint8  primeBits( 62500 ) // Bits for 500000 odd integers
  uint64 i, n, count = 1
  for n = 3 to _max step 2
    if primeBits(n >> 4) & bit((n & 15) >> 1) then continue
    primeList( count++ ) = n
    i = n * n
    while i < _max
      primeBits(i >> 4) |= bit((i & 15) >> 1)
      i += n << 1
    wend
  next
end fn

bool local fn squareFree( n as uint64 )
// Determines whether n is square-free
// by checking each squared prime
uint64 i = 1, square = 4
while square <= n
  if !(n % square) then return no
  square = primeList(i++)^2
wend
end fn = yes

local fn printList( n as uint64, tgt as uint64 )
  int wid = len(str(tgt))+1, cols = 64	/wid, count = 0
  CFStringRef form = concat( @"%",mid(str(wid),1),@"ld\b")
  printf @"\n  square-free numbers from %ld to %ld:", n, tgt
  while n <= tgt
    if fn squareFree( n )
      print fn StringWithFormat( form, n )
      count++
      if !( count % cols ) then print
    end if
    n++
  wend
  print @"\n"
end fn


window 1, @"square-free integers",(0, 0, 455, 640)
CFtimeInterval t : t = fn CACurrentMediatime

fn makePrimeList
fn printList(1, 145)
fn printList(1000000000000, 1000000000145)

uint32 tgt = 10, count = 0, i
do
  tgt *= 10
  for i = 1 to tgt
    count += fn squareFree( i )
  next
  printf @"  square-free numbers <= %7d: %d", tgt, count
until tgt >= 1000000

printf @"\n  Calc time: %.3fsec", fn CACurrentMediatime - t

HandleEvents