Square-free integers: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: added zkl header) |
(→{{header|zkl}}: added code) |
||
Line 719: | Line 719: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
<lang zkl>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 i in ([start..end]){ |
|||
free,n := True,i; |
|||
foreach j in ([0..numPrimes]){ |
|||
p,p2 := primes[j], p*p; |
|||
if(p2>i) break; |
|||
if(i%p2 == 0){ free=False; break; } |
|||
} |
|||
if(free){ sink.write(n); cnt+=1 } |
|||
} |
|||
return(cnt,sink.close()); |
|||
⚫ | |||
<lang zkl>println("Square-free integers from 1 to 145:"); |
|||
squareFree(1,145,True)[1].pump(Console.println, |
|||
T(Void.Read,14,False),fcn{ vm.arglist.apply("%4d ".fmt).concat() }); |
|||
println("\nSquare-free integers from 1000000000000 to 1000000000145:"); |
|||
squareFree(1000000000000,1000000000145,True)[1].pump(Console.println, |
|||
T(Void.Read,4,False),fcn{ vm.arglist.concat(" ") });</lang> |
|||
{{out}} |
|||
<pre style="height:35ex"> |
|||
Square-free integers from 1 to 145: |
|||
1 2 3 5 6 7 10 11 13 14 15 17 19 21 22 |
|||
23 26 29 30 31 33 34 35 37 38 39 41 42 43 46 |
|||
47 51 53 55 57 58 59 61 62 65 66 67 69 70 71 |
|||
73 74 77 78 79 82 83 85 86 87 89 91 93 94 95 |
|||
97 101 102 103 105 106 107 109 110 111 113 114 115 118 119 |
|||
122 123 127 129 130 131 133 134 137 138 139 141 142 143 145 |
|||
Square-free integers from 1000000000000 to 1000000000145: |
|||
1000000000001 1000000000002 1000000000003 1000000000005 1000000000006 |
|||
1000000000007 1000000000009 1000000000011 1000000000013 1000000000014 |
|||
1000000000015 1000000000018 1000000000019 1000000000021 1000000000022 |
|||
1000000000023 1000000000027 1000000000029 1000000000030 1000000000031 |
|||
1000000000033 1000000000037 1000000000038 1000000000039 1000000000041 |
|||
1000000000042 1000000000043 1000000000045 1000000000046 1000000000047 |
|||
1000000000049 1000000000051 1000000000054 1000000000055 1000000000057 |
|||
1000000000058 1000000000059 1000000000061 1000000000063 1000000000065 |
|||
1000000000066 1000000000067 1000000000069 1000000000070 1000000000073 |
|||
1000000000074 1000000000077 1000000000078 1000000000079 1000000000081 |
|||
1000000000082 1000000000085 1000000000086 1000000000087 1000000000090 |
|||
1000000000091 1000000000093 1000000000094 1000000000095 1000000000097 |
|||
1000000000099 1000000000101 1000000000102 1000000000103 1000000000105 |
|||
1000000000106 1000000000109 1000000000111 1000000000113 1000000000114 |
|||
1000000000115 1000000000117 1000000000118 1000000000119 1000000000121 |
|||
1000000000122 1000000000123 1000000000126 1000000000127 1000000000129 |
|||
1000000000130 1000000000133 1000000000135 1000000000137 1000000000138 |
|||
1000000000139 1000000000141 1000000000142 1000000000145 |
|||
</pre> |
|||
<lang zkl>n:=100; do(5){ |
|||
squareFree(1,n)[0]: |
|||
println("%,9d square-free integers from 1 to %,d".fmt(_,n)); |
|||
n*=10; |
|||
⚫ | |||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
61 square-free integers from 1 to 100 |
|||
608 square-free integers from 1 to 1,000 |
|||
6,083 square-free integers from 1 to 10,000 |
|||
60,794 square-free integers from 1 to 100,000 |
|||
607,926 square-free integers from 1 to 1,000,000 |
|||
</pre> |
</pre> |