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


const Limit=1 + (1e12 + 145).sqrt();	// 1000001 because it fits this task
var [const] 
   BI=Import.lib("zklBigNum"),    // GNU Multiple Precision Arithmetic Library
   primes=List.createLong(Limit); // one big allocate (vs lots of allocs)
 
// GMP provide nice way to generate primes, nextPrime is in-place
p:=BI(0); while(p<Limit){ primes.append(p.nextPrime().toInt()); } // 78,499 primes
 
fcn squareFree(start,end,save=False){ //-->(cnt,list|n)
   sink := Sink(if(save) List else Void);  // Sink(Void) is one item sink
   cnt, numPrimes := 0, (end - start).toFloat().sqrt().toInt() - 1;
   foreach n in ([start..end]){
      foreach j in ([0..numPrimes]){
         p,p2 := primes[j], p*p;
	 if(p2>n) break;
	 if(n%p2==0) continue(2);  // -->foreach n
      }
      sink.write(n); cnt+=1
   }
   return(cnt,sink.close());
}