64 lines
1.5 KiB
Text
64 lines
1.5 KiB
Text
_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
|