Task

Write a function to test if a number is   square-free.



A   square-free   is an integer which is divisible by no perfect square other
than   1   (unity).

For this task, only positive square-free numbers will be used.



Show here (on this page) all square-free integers (in a horizontal format) that are between:

   1   ───►   145     (inclusive)
   1 trillion   ───►   1 trillion + 145     (inclusive)


(One trillion = 1,000,000,000,000)



Show here (on this page) the count of square-free integers from:

   1   ───►   one hundred     (inclusive)
   1   ───►   one thousand     (inclusive)
   1   ───►   ten thousand     (inclusive)
   1   ───►   one hundred thousand     (inclusive)
   1   ───►   one million     (inclusive)


See also

   the Wikipedia entry:   square-free integer


' version 06-07-2018
' compile with: fbc -s console
 
Const As ULongInt trillion = 1000000000000ull
Const As ULong max = Sqr(trillion + 145)
 
Dim As UByte list(), sieve()
Dim As ULong prime()
ReDim list(max), prime(max\12), sieve(max)
 
Dim As ULong a, b, c, i, k, stop_ = Sqr(max)
 
For i = 4 To max Step 2   ' prime sieve remove even numbers except 2
    sieve(i) = 1
Next
For i = 3 To stop_ Step 2 ' proces odd numbers
    If sieve(i) = 0 Then
        For a = i * i To max Step i * 2
            sieve(a) = 1
        Next
    End If
Next
 
For i = 2 To max          ' move primes to a list
    If sieve(i) = 0 Then
        c += 1
        prime(c) = i
    End If
Next
 
ReDim sieve(145): ReDim Preserve prime(c)
 
For i = 1 To c  ' find all square free integers between 1 and 1000000
    a = prime(i) * prime(i)
    If a > 1000000 Then Exit For
    For k = a To 1000000 Step a
        list(k) = 1
    Next
Next
 
k = 0
For i = 1 To 145          ' show all between 1 and 145
    If list(i) = 0 Then
        Print Using"####"; i;
        k +=1
        If k Mod 20 = 0 Then Print 
    End If
Next
Print : Print
 
sieve(0) = 1              ' = trillion
For i = 1 To 5            ' process primes 2, 3, 5, 7, 11
    a = prime(i) * prime(i)
    b = a - trillion Mod a
    For k = b To 145 Step a
        sieve(k) = 1
    Next
Next
 
For i = 6 To c            ' process the rest of the primes
    a = prime(i) * prime(i)
    k = a - trillion Mod a
    If k <= 145 Then sieve(k) = 1
Next
 
k = 0
For i = 0 To 145
    If sieve(i) = 0 Then
        Print Using "################"; (trillion + i);
        k += 1
        If k Mod 5 = 0 Then print
    End If
Next
Print : Print
 
a = 1 : b = 100 : k = 0
Do Until b > 1000000      ' count them
    For i = a To b
        If list(i) = 0 Then k += 1
    Next
    Print "There are "; k; " square free integers between 1 and "; b
    a = b : b *= 10
Loop
 
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End