Rosetta Code

Square-free integers: Difference between revisions

Page Discussion

Square-free integers (view source)

Revision as of 16:32, 9 February 2024

69,681 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Minor tidy
(→‎{{header|J}}: arrayify the counting tasks)
m (→‎{{header|Wren}}: Minor tidy)
 
(40 intermediate revisions by 21 users not shown)
Line 31:
:*   the Wikipedia entry:   [https://wikipedia.org/wiki/Square-free_integer square-free integer]
<br><br>
 
=={{header|11l}}==
{{trans|Python}}
 
<syntaxhighlight lang="11l">F SquareFree(_number)
V max = Int(sqrt(_number))
 
L(root) 2 .. max
I 0 == _number % (Int64(root) ^ 2)
R 0B
 
R 1B
 
F ListSquareFrees(Int64 _start, Int64 _end)
V count = 0
L(i) _start .. _end
I SquareFree(i)
print(i"\t", end' ‘’)
I count % 5 == 4
print()
count++
 
print("\n\nTotal count of square-free numbers between #. and #.: #.".format(_start, _end, count))
 
ListSquareFrees(1, 100)
ListSquareFrees(1000000000000, 1000000000145)</syntaxhighlight>
 
{{out}}
<pre>
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
 
Total count of square-free numbers between 1 and 100: 61
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
 
Total count of square-free numbers between 1000000000000 and 1000000000145: 89
</pre>
 
=={{header|ALGOL 68}}==
<langsyntaxhighlight lang="algol68">BEGIN
# count/show some square free numbers #
# a number is square free if not divisible by any square and so not divisible #
Line 114 ⟶ 179:
INT sf 1 000 000 := sf 100 000 + count square free( 100 001, 1 000 000 );
print( ( "square free numbers between 1 and 1 000 000: ", whole( sf 1 000 000, -6 ), newline ) )
END</langsyntaxhighlight>
{{out}}
<pre>Square free numbers from 1 to 145
Line 146 ⟶ 211:
square free numbers between 1 and 100 000: 60794
square free numbers between 1 and 1 000 000: 607926</pre>
 
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">squareFree?: function [n][
mx: to :integer sqrt n
loop 2..mx 'r ->
if zero? n % r ^ 2 -> return false
 
return true
]
 
sqFreeUpTo145: [1 2 3] ++ select 1..145 => squareFree?
print "Square-free integers from 1 to 145:"
loop split.every: 20 sqFreeUpTo145 'x ->
print map x 's -> pad to :string s 4
 
print ""
 
sqFreeUpToTrillion: select 1000000000000..1000000000145 => squareFree?
print "Square-free integers from 1000000000000 to 1000000000145:"
loop split.every: 5 sqFreeUpToTrillion 'x ->
print map x 's -> pad to :string s 14
 
print ""
 
print ["Number of square-free numbers between 1 and 100: " s100: <= 3 + enumerate 1..100 => squareFree?]
print ["Number of square-free numbers between 1 and 1000: " s1000: <= s100 + enumerate 101..1000 => squareFree?]
print ["Number of square-free numbers between 1 and 10000: " s10000: <= s1000 + enumerate 1001..10000 => squareFree?]
print ["Number of square-free numbers between 1 and 100000: " s100000: <= s10000 + enumerate 10001..100000 => squareFree?]
print ["Number of square-free numbers between 1 and 1000000: " s100000 + enumerate 100001..1000000 => squareFree?]</syntaxhighlight>
 
{{out}}
 
<pre>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
 
Number of square-free numbers between 1 and 100: 61
Number of square-free numbers between 1 and 1000: 608
Number of square-free numbers between 1 and 10000: 6083
Number of square-free numbers between 1 and 100000: 60794
Number of square-free numbers between 1 and 1000000: 607926</pre>
 
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SQUARE-FREE_INTEGERS.AWK
# converted from LUA
BEGIN {
main(1,145,1)
main(1000000000000,1000000000145,1)
main(1,100,0)
main(1,1000,0)
main(1,10000,0)
main(1,100000,0)
main(1,1000000,0)
exit(0)
}
function main(lo,hi,show_values, count,i,leng) {
printf("%d-%d: ",lo,hi)
leng = length(lo) + length(hi) + 3
for (i=lo; i<=hi; i++) {
if (square_free(i)) {
count++
if (show_values) {
if (leng > 110) {
printf("\n")
leng = 0
}
printf("%d ",i)
leng += length(i) + 1
}
}
}
printf("count=%d\n\n",count)
}
function square_free(n, root) {
for (root=2; root<=sqrt(n); root++) {
if (n % (root * root) == 0) {
return(0)
}
}
return(1)
}
</syntaxhighlight>
{{out}}
<pre>
1-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 count=90
 
1000000000000-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 count=89
 
1-100: count=61
 
1-1000: count=608
 
1-10000: count=6083
 
1-100000: count=60794
 
1-1000000: count=607926
</pre>
 
=={{header|C}}==
{{trans|Go}}
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <math.h>
Line 235 ⟶ 435:
free(sf);
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 273 ⟶ 473:
from 1 to 1000000 = 607926
</pre>
 
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <cstdint>
#include <iostream>
#include <string>
 
using integer = uint64_t;
 
bool square_free(integer n) {
if (n % 4 == 0)
return false;
for (integer p = 3; p * p <= n; p += 2) {
integer count = 0;
for (; n % p == 0; n /= p) {
if (++count > 1)
return false;
}
}
return true;
}
 
void print_square_free_numbers(integer from, integer to) {
std::cout << "Square-free numbers between " << from
<< " and " << to << ":\n";
std::string line;
for (integer i = from; i <= to; ++i) {
if (square_free(i)) {
if (!line.empty())
line += ' ';
line += std::to_string(i);
if (line.size() >= 80) {
std::cout << line << '\n';
line.clear();
}
}
}
if (!line.empty())
std::cout << line << '\n';
}
 
void print_square_free_count(integer from, integer to) {
integer count = 0;
for (integer i = from; i <= to; ++i) {
if (square_free(i))
++count;
}
std::cout << "Number of square-free numbers between "
<< from << " and " << to << ": " << count << '\n';
}
 
int main() {
print_square_free_numbers(1, 145);
print_square_free_numbers(1000000000000LL, 1000000000145LL);
print_square_free_count(1, 100);
print_square_free_count(1, 1000);
print_square_free_count(1, 10000);
print_square_free_count(1, 100000);
print_square_free_count(1, 1000000);
return 0;
}</syntaxhighlight>
 
{{out}}
<pre>
Square-free numbers between 1 and 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 numbers between 1000000000000 and 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
Number of square-free numbers between 1 and 100: 61
Number of square-free numbers between 1 and 1000: 608
Number of square-free numbers between 1 and 10000: 6083
Number of square-free numbers between 1 and 100000: 60794
Number of square-free numbers between 1 and 1000000: 607926
</pre>
 
=={{header|D}}==
{{trans|Java}}
<syntaxhighlight lang="d">import std.array;
import std.math;
import std.stdio;
 
long[] sieve(long limit) {
long[] primes = [2];
bool[] c = uninitializedArray!(bool[])(cast(size_t)(limit + 1));
long p = 3;
while (true) {
long p2 = p * p;
if (p2 > limit) {
break;
}
for (long i = p2; i <= limit; i += 2 * p) {
c[cast(size_t)i] = true;
}
while (true) {
p += 2;
if (!c[cast(size_t)p]) {
break;
}
}
}
for (long i = 3; i <= limit; i += 2) {
if (!c[cast(size_t)i]) {
primes ~= i;
}
}
return primes;
}
 
long[] squareFree(long from, long to) {
long limit = cast(long)sqrt(cast(real)to);
auto primes = sieve(limit);
long[] results;
 
outer:
for (long i = from; i <= to; i++) {
foreach (p; primes) {
long p2 = p * p;
if (p2 > i) {
break;
}
if (i % p2 == 0) {
continue outer;
}
}
results ~= i;
}
 
return results;
}
 
enum TRILLION = 1_000_000_000_000L;
 
void main() {
writeln("Square-free integers from 1 to 145:");
auto sf = squareFree(1, 145);
foreach (i,v; sf) {
if (i > 0 && i % 20 == 0) {
writeln;
}
writef("%4d", v);
}
 
writefln("\n\nSquare-free integers from %d to %d:", TRILLION, TRILLION + 145);
sf = squareFree(TRILLION, TRILLION + 145);
foreach (i,v; sf) {
if (i > 0 && i % 5 == 0) {
writeln;
}
writef("%14d", v);
}
 
writeln("\n\nNumber of square-free integers:");
foreach (to; [100, 1_000, 10_000, 100_000, 1_000_000]) {
writefln(" from 1 to %d = %d", to, squareFree(1, to).length);
}
}</syntaxhighlight>
{{out}}
<pre>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
 
Number of square-free integers:
from 1 to 100 = 61
from 1 to 1000 = 608
from 1 to 10000 = 6083
from 1 to 100000 = 60794
from 1 to 1000000 = 607926</pre>
 
=={{header|Factor}}==
Line 278 ⟶ 684:
 
For instance, the prime factorization of <tt>12</tt> is <code>2 * 2 * 3</code>, or in other words, <code>2<sup>2</sup> * 3</code>. The <tt>2</tt> repeats, so we know <tt>12</tt> isn't square-free.
<langsyntaxhighlight lang="factor">USING: formatting grouping io kernel math math.functions
math.primes.factors math.ranges sequences sets ;
IN: rosetta-code.square-free
Line 297 ⟶ 703:
1 145 10 12 ^ dup 145 + [ sq-free-show ] 2bi@ ! part 1
2 6 [a,b] [ 10 swap ^ ] map [ sq-free-count ] each ! part 2</langsyntaxhighlight>
{{out}}
<pre>
Line 333 ⟶ 739:
607926 square-free integers from 1 to 1000000
</pre>
 
=={{header|Forth}}==
<syntaxhighlight lang="forth">: square_free? ( n -- ? )
dup 4 mod 0= if drop false exit then
3
begin
2dup dup * >=
while
0 >r
begin
2dup mod 0=
while
r> 1+ dup 1 > if
2drop drop false exit
then
>r
tuck / swap
repeat
rdrop
2 +
repeat
2drop true ;
\ print square-free numbers from n3 to n2, n1 per line
: print_square_free_numbers ( n1 n2 n3 -- )
2dup
." Square-free integers between "
1 .r ." and " 1 .r ." :" cr
0 -rot
swap 1+ swap do
i square_free? if
i 3 .r space
1+
dup 2 pick mod 0= if cr then
then
loop 2drop cr ;
 
: count_square_free_numbers ( n1 n2 -- n )
0 -rot
swap 1+ swap do
i square_free? if 1+ then
loop ;
 
: main
20 145 1 print_square_free_numbers cr
5 1000000000145 1000000000000 print_square_free_numbers cr
." Number of square-free integers:" cr
100
begin
dup 1000000 <=
while
dup 1
2dup ." from " 1 .r ." to " 7 .r ." : "
count_square_free_numbers . cr
10 *
repeat drop ;
 
main
bye</syntaxhighlight>
 
{{out}}
<pre>
Square-free integers between 1 and 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 between 1000000000000 and 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
 
Number of square-free integers:
from 1 to 100: 61
from 1 to 1000: 608
from 1 to 10000: 6083
from 1 to 100000: 60794
from 1 to 1000000: 607926
</pre>
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">' version 06-07-2018
' compile with: fbc -s console
 
Line 422 ⟶ 925:
Print : Print "hit any key to end program"
Sleep
End</langsyntaxhighlight>
{{out}}
<pre> 1 2 3 5 6 7 10 11 13 14 15 17 19 21 22 23 26 29 30 31
Line 456 ⟶ 959:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import (
Line 536 ⟶ 1,039:
fmt.Printf(" from %d to %d = %d\n", 1, n, len(squareFree(1, n)))
}
}</langsyntaxhighlight>
 
{{out}}
Line 577 ⟶ 1,080:
 
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">import Data.List.Split (chunksOf)
import Math.NumberTheory.Primes (factorise)
import Text.Printf (printf)
Line 617 ⟶ 1,120:
printSquareFrees 20 1 145
printSquareFrees 5 1000000000000 1000000000145
printSquareFreeCounts [100, 1000, 10000, 100000, 1000000] 1 1000000</langsyntaxhighlight>
 
{{out}}
Line 658 ⟶ 1,161:
=={{header|J}}==
'''Solution:'''
<langsyntaxhighlight lang="j">isSqrFree=: (#@~. = #)@q: NB. are there no duplicates in the prime factors of a number?
filter=: adverb def ' #~ u' NB. filter right arg using verb to left
countSqrFree=: +/@:isSqrFree
thru=: <. + i.@(+ *)@-~ NB. helper verb</langsyntaxhighlight>
 
'''Required Examples:'''
<langsyntaxhighlight lang="j"> isSqrFree filter 1 thru 145 NB. returns all results, but not all are displayed
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...
100 list isSqrFree filter 1000000000000 thru 1000000000145 NB. ensure that all results are displayed
Line 685 ⟶ 1,188:
608
1 countSqrFree@thru&> 10 ^ 2 3 4 5 6 NB. count square free ints for 1 to each of 100, 1000, 10000, 10000, 100000 and 1000000
61 608 6083 60794 607926</langsyntaxhighlight>
 
=={{header|Java}}==
{{trans|Go}}
<langsyntaxhighlight lang="java">import java.util.ArrayList;
import java.util.List;
 
Line 757 ⟶ 1,260:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 917 ⟶ 1,420:
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Primes
 
const maxrootprime = Int64(floor(sqrt(1000000000145)))
Line 960 ⟶ 1,463:
squarefreebetween(1000000000000, 1000000000145)
squarefreecount([100, 1000, 10000, 100000], 1000000)
</langsyntaxhighlight> {{output}} <pre>
The squarefree numbers between 1 and 145 are:
1 2 3 5 6 7 10 11 13 14 15 17 19 21 22 23
Line 996 ⟶ 1,499:
=={{header|Kotlin}}==
{{trans|Go}}
<langsyntaxhighlight lang="scala">// Version 1.2.50
 
import kotlin.math.sqrt
Line 1,051 ⟶ 1,554:
j -> println(" from 1 to $j = ${squareFree(1..j).size}")
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,093 ⟶ 1,596:
=={{header|Lua}}==
This is a naive method, runs in about 1 second on LuaJIT.
<langsyntaxhighlight lang="lua">function squareFree (n)
for root = 2, math.sqrt(n) do
if n % (root * root) == 0 then return false end
Line 1,125 ⟶ 1,628:
{1, 1000000}
}
for _, example in pairs(testCases) do run(unpack(example)) end</langsyntaxhighlight>
{{out}}
<pre>From 1 to 145:
Line 1,165 ⟶ 1,668:
From 1 to 1000000 = 607926</pre>
 
=={{header|MathematicaMaple}}==
 
<lang Mathematica>squareFree[n_Integer] := DeleteCases[Last /@ FactorInteger[n], 1] === {};
<syntaxhighlight lang="maple">
with(NumberTheory):
with(ArrayTools):
 
squareFree := proc(n::integer)
if mul(PrimeFactors(n)) = n then return true;
else return false; end if;
return true;
end proc:
 
sfintegers := Array([]):
 
for count from 1 to 145 do
if squareFree(count) then Append(sfintegers, count); end if;
end do:
 
print(sfintegers):
 
sfintegers := Array([]):
 
for count from 10^12 to 10^12+145 do
if squareFree(count) then Append(sfintegers, count); end if;
end do:
 
print(sfintegers):
 
sfgroups := Array([]):
sfcount := 0:
 
for number from 1 to 100 do
if squareFree(number) then sfcount += 1: end if:
end do:
Append(sfgroups, sfcount):
 
for expon from 3 to 6 do
for number from 10^(expon - 1) to 10^expon do
if squareFree(number) then sfcount += 1: end if:
end do:
Append(sfgroups, sfcount):
end do:
 
seq(cat(sfgroups[i], " from 1 to ", 10^(i+1)), i = 1..5);
</syntaxhighlight>
{{out}}<pre>
[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]
 
[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]
 
61 from 1 to 100, 608 from 1 to 1000, 6083 from 1 to 10000,
 
60794 from 1 to 100000, 607926 from 1 to 1000000
 
</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">squareFree[n_Integer] := DeleteCases[Last /@ FactorInteger[n], 1] === {};
findSquareFree[n__] := Select[Range[n], squareFree];
findSquareFree[45]
findSquareFree[10^9, 10^9 + 145]
Length[findSquareFree[10^6]]</langsyntaxhighlight>
{{out}}
<pre>{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}
Line 1,193 ⟶ 1,796:
1000000135, 1000000137, 1000000138, 1000000139, 1000000141, 1000000142}
 
607926</pre>
 
=={{header|Nanoquery}}==
{{trans|AWK}}
<syntaxhighlight lang="nanoquery">def is_square_free(n)
if n < 2^2
return true
end
 
for root in range(2, int(sqrt(n)))
if (n % (root ^ 2)) = 0
return false
end
end
return true
end
 
def square_free(low, high, show_values)
print format("%d-%d: ", low, high)
leng = len(str(low)) + len(str(high)) + 3
count = 0
for i in range(low, high)
if is_square_free(i)
count += 1
if show_values
if leng > 110
println
leng = 0
end
print format("%d ", i)
leng += len(str(i)) + 1
end
end
end
print format("count=%d\n\n", count)
end
 
square_free(1, 145, true)
square_free(10^12, 10^12 + 145, true)
square_free(1, 100, false)
square_free(1, 1000, false)
square_free(1, 10000, false)
square_free(1, 100000, false)
square_free(1, 1000000, false)</syntaxhighlight>
{{out}}
<pre>
1-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 count=90
 
1000000000000-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 count=89
 
1-100: count=61
 
1-1000: count=608
 
1-10000: count=6083
 
1-100000: count=60794
 
1-1000000: count=607926
</pre>
 
=={{header|Nim}}==
{{trans|Go}}
<syntaxhighlight lang="nim">import math, strutils
 
 
proc sieve(limit: Natural): seq[int] =
result = @[2]
var c = newSeq[bool](limit + 1) # Composite = true.
# No need to process even numbers > 2.
var p = 3
while true:
let p2 = p * p
if p2 > limit: break
for i in countup(p2, limit, 2 * p):
c[i] = true
while true:
inc p, 2
if not c[p]: break
for i in countup(3, limit, 2):
if not c[i]: result.add i
 
 
proc squareFree(fromVal, toVal: Natural): seq[int] =
let limit = int(sqrt(toVal.toFloat))
let primes = sieve(limit)
for i in fromVal..toVal:
block check:
for p in primes:
let p2 = p * p
if p2 > i: break
if i mod p2 == 0:
break check # Not square free.
result.add i
 
 
when isMainModule:
 
const Trillion = 1_000_000_000_000
 
echo "Square-free integers from 1 to 145:"
var sf = squareFree(1, 145)
for i, val in sf:
if i > 0 and i mod 20 == 0:
echo()
stdout.write ($val).align(4)
echo()
 
echo "\nSquare-free integers from $1 to $2:\n".format(Trillion, Trillion + 145)
sf = squareFree(Trillion, Trillion + 145)
for i, val in sf:
if i > 0 and i mod 5 == 0:
echo()
stdout.write ($val).align(14)
echo()
 
echo "\nNumber of square-free integers:\n"
for n in [100, 1_000, 10_000, 100_000, 1_000_000]:
echo " from $1 to $2 = $3".format(1, n, squareFree(1, n).len)</syntaxhighlight>
 
{{out}}
<pre>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
 
Number of square-free integers:
 
from 1 to 100 = 61
from 1 to 1000 = 608
from 1 to 10000 = 6083
from 1 to 100000 = 60794
from 1 to 1000000 = 607926
</pre>
=={{header|OCaml}}==
<syntaxhighlight lang="ocaml">
let squarefree (number: int) : bool =
let max = Float.of_int number |> sqrt |> Float.to_int |> (fun x -> x + 2) in
let rec inner i number2 =
if i == max
then true
else if number2 mod (i*i) == 0
then false
else inner (i+1) number2
in inner 2 number
;;
 
let list_squarefree_integers (x, y) =
let rec inner start finish output =
if start == finish
then output
else if squarefree start
then inner (start+1) finish (start :: output)
else inner (start+1) finish output
in inner x y []
;;
 
let print_squarefree_integers (x, y) =
let squarefrees_unrev = list_squarefree_integers (x, y) in
let squarefrees = List.rev squarefrees_unrev in
let rec inner sfs i count =
match sfs with
[] -> count
| h::t -> (if (i+1) mod 5 == 0 then (Printf.printf "%d\n" h) else (Printf.printf "%d " h); inner t (i+1) (count+1);)
in Printf.printf "\n\nTotal count of square-free numbers between %d and %d: %d\n" x y (inner squarefrees 0 0)
;;
 
let () =
print_squarefree_integers (1, 146);
print_squarefree_integers (1000000000000, 1000000000146)
;;
</syntaxhighlight>
 
{{out}}
 
<pre>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
 
 
Total count of square-free numbers between 1 and 146: 90
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
 
Total count of square-free numbers between 1000000000000 and 1000000000146: 89
</pre>
 
=={{header|Pascal}}==
{{works with|Free Pascal}}
As so often, marking/sieving multiples of square of primes to speed things up.
<syntaxhighlight lang="pascal">program SquareFree;
{$IFDEF FPC}
{$MODE DELPHI}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
const
//needs 1e10 Byte = 10 Gb maybe someone got 128 Gb :-) nearly linear time
BigLimit = 10*1000*1000*1000;
TRILLION = 1000*1000*1000*1000;
primeLmt = trunc(sqrt(TRILLION+150));
 
var
primes : array of byte;
sieve : array of byte;
 
procedure initPrimes;
var
i,lmt,dp :NativeInt;
Begin
setlength(primes,80000);
setlength(sieve,primeLmt);
sieve[0] := 1;
sieve[1] := 1;
i := 2;
repeat
IF sieve[i] = 0 then
Begin
lmt:= i*i;
while lmt<primeLmt do
Begin
sieve[lmt] := 1;
inc(lmt,i);
end;
end;
inc(i);
until i*i>=primeLmt;
//extract difference of primes
i := 0;
lmt := 0;
dp := 0;
repeat
IF sieve[i] = 0 then
Begin
primes[lmt] := dp;
dp := 0;
inc(lmt);
end;
inc(dp);
inc(i);
until i >primeLmt;
setlength(sieve,0);
setlength(Primes,lmt+1);
end;
 
procedure SieveSquares;
//mark all powers >=2 of prime => all powers = 2 is sufficient
var
pSieve : pByte;
i,sq,k,prime : NativeInt;
Begin
pSieve := @sieve[0];
prime := 0;
For i := 0 to High(primes) do
Begin
prime := prime+primes[i];
sq := prime*prime;
k := sq;
if sq > BigLimit then
break;
repeat
pSieve[k] := 1;
inc(k,sq);
until k> BigLimit;
end;
end;
 
procedure Count_x10;
var
pSieve : pByte;
i,lmt,cnt: NativeInt;
begin
writeln(' square free count');
writeln('[1 to limit]');
 
pSieve := @sieve[0];
lmt := 10;
i := 1;
cnt := 0;
repeat
while i <= lmt do
Begin
inc(cnt,ORD(pSieve[i] = 0));
inc(i);
end;
writeln(lmt:12,' ',cnt:12);
IF lmt >= BigLimit then
BREAK;
lmt := lmt*10;
IF lmt >BigLimit then
lmt := BigLimit;
until false;
end;
 
function TestSquarefree(N:Uint64):boolean;
var
i,prime,sq : NativeUint;
Begin
prime := 0;
result := false;
For i := 0 to High(primes) do
Begin
prime := prime+primes[i];
sq := sqr(prime);
IF sq> N then
BREAK;
IF N MOD sq = 0 then
EXIT;
end;
result := true;
end;
var
i,k : NativeInt;
Begin
InitPrimes;
setlength(sieve,BigLimit+1);
SieveSquares;
 
writeln('Square free numbers from 1 to 145');
k := 80 div 4;
For i := 1 to 145 do
If sieve[i] = 0 then
Begin
write(i:4);
dec(k);
IF k = 0 then
Begin
writeln;
k := 80 div 4;
end;
end;
writeln;writeln;
 
writeln('Square free numbers from ',TRILLION,' to ',TRILLION+145);
k := 4;
For i := TRILLION to TRILLION+145 do
Begin
if TestSquarefree(i) then
Begin
write(i:20);
dec(k);
IF k = 0 then
Begin
writeln;
k := 4;
end;
end;
end;
writeln;writeln;
 
Count_x10;
end.</syntaxhighlight>
{{out}}
<pre style="height:35ex">Square free numbers 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 numbers 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
 
square free count
[1 to limit]
10 7
100 61
1000 608
10000 6083
100000 60794
1000000 607926
10000000 6079291
100000000 60792694
1000000000 607927124
10000000000 6079270942
 
real 0m13,908s</pre>
 
=={{header|Perl}}==
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use ntheory qw/is_square_free moebius/;
 
sub square_free_count {
Line 1,219 ⟶ 2,286:
my $c = square_free_count(10**$n);
print "The number of square-free numbers between 1 and 10^$n (inclusive) is: $c\n";
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,234 ⟶ 2,301:
The number of square-free numbers between 1 and 10^6 (inclusive) is: 607926
</pre>
 
=={{header|Perl 6}}==
{{works with|Rakudo|2018.06}}
The prime factoring algorithm is not really the best option for finding long runs of sequential square-free numbers. It works, but is probably better suited for testing arbitrary numbers rather than testing every sequential number from 1 to some limit. If you know that that is going to be your use case, there are faster algorithms.
 
<lang perl6># Prime factorization routines
sub prime-factors ( Int $n where * > 0 ) {
return $n if $n.is-prime;
return [] if $n == 1;
my $factor = find-factor( $n );
flat prime-factors( $factor ), prime-factors( $n div $factor );
}
 
sub find-factor ( Int $n, $constant = 1 ) {
return 2 unless $n +& 1;
if (my $gcd = $n gcd 6541380665835015) > 1 {
return $gcd if $gcd != $n
}
my $x = 2;
my $rho = 1;
my $factor = 1;
while $factor == 1 {
$rho *= 2;
my $fixed = $x;
for ^$rho {
$x = ( $x * $x + $constant ) % $n;
$factor = ( $x - $fixed ) gcd $n;
last if 1 < $factor;
}
}
$factor = find-factor( $n, $constant + 1 ) if $n == $factor;
$factor;
}
 
# Task routine
sub is-square-free (Int $n) { my @v = $n.&prime-factors.Bag.values; @v.sum/@v <= 1 }
 
# The Task
# Parts 1 & 2
for 1, 145, 1e12.Int, 145+1e12.Int -> $start, $end {
say "\nSquare─free numbers between $start and $end:\n",
($start .. $end).hyper(:4batch).grep( *.&is-square-free ).list.fmt("%3d").comb(84).join("\n");
}
 
# Part 3
for 1e2, 1e3, 1e4, 1e5, 1e6 {
say "\nThe number of square─free numbers between 1 and {$_} (inclusive) is: ",
+(1 .. .Int).race.grep: *.&is-square-free;
}</lang>
{{out}}
<pre>
Square─free numbers between 1 and 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 numbers between 1000000000000 and 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
 
The number of square─free numbers between 1 and 100 (inclusive) is: 61
 
The number of square─free numbers between 1 and 1000 (inclusive) is: 608
 
The number of square─free numbers between 1 and 10000 (inclusive) is: 6083
 
The number of square─free numbers between 1 and 100000 (inclusive) is: 60794
 
The number of square─free numbers between 1 and 1000000 (inclusive) is: 607926</pre>
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<lang Phix>function square_free(atom start, finish)
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
sequence res = {}
<span style="color: #008080;">function</span> <span style="color: #000000;">square_frees</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">start</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">finish</span><span style="color: #0000FF;">)</span>
if start=1 then res = {1} start = 2 end if
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
while start<=finish do
<span style="color: #004080;">integer</span> <span style="color: #000000;">maxprime</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_maxprime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">finish</span><span style="color: #0000FF;">)</span>
sequence pf = prime_factors(start, duplicates:=true)
<span style="color: #008080;">while</span> <span style="color: #000000;">start</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">finish</span> <span style="color: #008080;">do</span>
for i=2 to length(pf) do
<span style="color: #008080;">if</span> <span style="color: #7060A8;">square_free</span><span style="color: #0000FF;">(</span><span style="color: #000000;">start</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxprime</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
if pf[i]=pf[i-1] then
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">start</span>
pf = {}
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
exit
<span style="color: #000000;">start</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
end for
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
if pf!={} then
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
res &= start
end if
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show_range</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">start</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">finish</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">jb</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">fmt</span><span style="color: #0000FF;">)</span>
start += 1
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">square_frees</span><span style="color: #0000FF;">(</span><span style="color: #000000;">start</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">finish</span><span style="color: #0000FF;">)</span>
end while
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"There are %d square-free integers from %,d to %,d:\n%s\n"</span><span style="color: #0000FF;">,</span>
return res
<span style="color: #0000FF;">{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #000000;">start</span><span style="color: #0000FF;">,</span><span style="color: #000000;">finish</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">jb</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">)})</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
 
<span style="color: #000000;">show_range</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">145</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%4d"</span><span style="color: #0000FF;">)</span>
function format_res(sequence res, string fmt)
<span style="color: #000000;">show_range</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1e12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1e12</span><span style="color: #0000FF;">+</span><span style="color: #000000;">145</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%14d"</span><span style="color: #0000FF;">)</span>
for i=1 to length(res) do
res[i] = sprintf(fmt,res[i])
end for
return res
end function
 
constant ONE_TRILLION = 1_000_000_000_000
 
procedure main()
sequence res = square_free(1,145)
printf(1,"There are %d square-free integers from 1 to 145:\n",length(res))
puts(1,join_by(format_res(res,"%4d"),1,20,""))
res = square_free(ONE_TRILLION,ONE_TRILLION+145)
printf(1,"\nThere are %d square-free integers from %,d to %,d:\n",
{length(res),ONE_TRILLION, ONE_TRILLION+145})
puts(1,join_by(format_res(res,"%14d"),1,5,""))
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nNumber of square-free integers:\n"</span><span style="color: #0000FF;">);</span>
printf(1,"\nNumber of square-free integers:\n");
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">6</span> <span style="color: #008080;">do</span>
for i=2 to 6 do
<span style="color: #004080;">integer</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">),</span>
integer lim = power(10,i),
<span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">square_frees</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">))</span>
len = length(square_free(1,lim))
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" from %,d to %,d = %,d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len</span><span style="color: #0000FF;">})</span>
printf(1," from %,d to %,d = %,d\n", {1,lim,len})
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<!--</syntaxhighlight>-->
end procedure
main()</lang>
{{out}}
<pre>
Line 1,404 ⟶ 2,370:
 
=={{header|Python}}==
<syntaxhighlight lang="python">
<lang Python>
import math
 
Line 1,427 ⟶ 2,393:
ListSquareFrees( 1, 100 )
ListSquareFrees( 1000000000000, 1000000000145 )
</syntaxhighlight>
</lang>
 
'''Output:'''
Line 1,464 ⟶ 2,430:
=={{header|Racket}}==
 
<langsyntaxhighlight lang="racket">#lang racket
 
(define (not-square-free-set-for-range range-min (range-max (add1 range-min)))
Line 1,506 ⟶ 2,472:
(count-square-free-numbers 10000)
(count-square-free-numbers 100000)
(count-square-free-numbers 1000000))</langsyntaxhighlight>
 
{{out}}
Line 1,540 ⟶ 2,506:
60794
607926</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2018.06}}
The prime factoring algorithm is not really the best option for finding long runs of sequential square-free numbers. It works, but is probably better suited for testing arbitrary numbers rather than testing every sequential number from 1 to some limit. If you know that that is going to be your use case, there are faster algorithms.
 
<syntaxhighlight lang="raku" line># Prime factorization routines
sub prime-factors ( Int $n where * > 0 ) {
return $n if $n.is-prime;
return [] if $n == 1;
my $factor = find-factor( $n );
flat prime-factors( $factor ), prime-factors( $n div $factor );
}
 
sub find-factor ( Int $n, $constant = 1 ) {
return 2 unless $n +& 1;
if (my $gcd = $n gcd 6541380665835015) > 1 {
return $gcd if $gcd != $n
}
my $x = 2;
my $rho = 1;
my $factor = 1;
while $factor == 1 {
$rho *= 2;
my $fixed = $x;
for ^$rho {
$x = ( $x * $x + $constant ) % $n;
$factor = ( $x - $fixed ) gcd $n;
last if 1 < $factor;
}
}
$factor = find-factor( $n, $constant + 1 ) if $n == $factor;
$factor;
}
 
# Task routine
sub is-square-free (Int $n) { my @v = $n.&prime-factors.Bag.values; @v.sum/@v <= 1 }
 
# The Task
# Parts 1 & 2
for 1, 145, 1e12.Int, 145+1e12.Int -> $start, $end {
say "\nSquare─free numbers between $start and $end:\n",
($start .. $end).hyper(:4batch).grep( &is-square-free ).list.fmt("%3d").comb(84).join("\n");
}
 
# Part 3
for 1e2, 1e3, 1e4, 1e5, 1e6 {
say "\nThe number of square─free numbers between 1 and {$_} (inclusive) is: ",
+(1 .. .Int).race.grep: &is-square-free;
}</syntaxhighlight>
{{out}}
<pre>
Square─free numbers between 1 and 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 numbers between 1000000000000 and 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
 
The number of square─free numbers between 1 and 100 (inclusive) is: 61
 
The number of square─free numbers between 1 and 1000 (inclusive) is: 608
 
The number of square─free numbers between 1 and 10000 (inclusive) is: 6083
 
The number of square─free numbers between 1 and 100000 (inclusive) is: 60794
 
The number of square─free numbers between 1 and 1000000 (inclusive) is: 607926</pre>
 
=={{header|REXX}}==
<langsyntaxhighlight lang="rexx">/*REXX program displays square─free numbers (integers > 1) up to a specified limit. */
numeric digits 20 /*be able to handle larger numbers. */
parse arg LO HI . /*obtain optional arguments from the CL*/
Line 1,548 ⟶ 2,599:
if HI=='' | HI=="," then HI= 145 /* " " " " " " */
sw= linesize() - 1 /*use one less than a full line. */
count# = 0 /*count of square─free numbers found. */
$= /*variable that holds a line of numbers*/
do j=LO to abs(HI) /*process all integers between LO & HI.*/
if \isSquareFree(j) then iterate /*Not square─free? Then skip this #. */
count#= count# + 1 /*bump the count of square─free numbers*/
if HI<0 then iterate /*Only counting 'em? Then look for more*/
if length($ || j)<sw then $= strip($ j) /*append the number to the output list.*/
Line 1,559 ⟶ 2,610:
 
if $\=='' then say $ /*are there any residuals to display ? */
TheNum@theNum= 'The number of square─free numbers between '
if HI<0 then say TheNum@theNum LO " and " abs(HI) ' (inclusive) is: ' count#
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
isSquareFree: procedure; parse arg #x; if #x<1 then return 0 /*is the number too small?*/
odd=# x//2 /*ODD=1 if #X is odd, ODD=0 if even.*/
do k=2+odd to iSqrt(#x) by 1+odd /*use all numbers, or just odds*/
if #x // k**2 == 0 then return 0 /*Is # X divisible by a square? */
end /*k*/ /* [↑] Yes? Then ^¬ square─free*/
return 1 /* [↑] // is REXX's ÷ remainder.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
iSqrt: procedure; parse arg x; q= 1; do while q<=x; q= q * 4
do while q<=x; q= q end /*while 4q<=x*/
end /*while q<=x*/
r= 0
do while q>1; q= q % 4; _= x - r - q; r= r % 2
if _>=0 then do; x= _; r= r + q; end
end /*while q>1*/
return r /*R is the integer square root of X. */</langsyntaxhighlight>
This REXX program makes use of &nbsp; '''linesize''' &nbsp; REXX program (or BIF) &nbsp; which is used to determine the screen width (or linesize) of the terminal (console); &nbsp; not all REXXes have this BIF.
 
Line 1,615 ⟶ 2,665:
 
The number of square─free numbers between 1 and 1000000 (inclusive) is: 607926
</pre>
 
=={{header|RPL}}==
{{trans|Python}}
≪ DUP √ CEIL → n max
≪ 1 SF
2 max '''FOR''' root
'''IF''' n root SQ MOD NOT '''THEN''' 1 CF max 'root' STO '''END'''
'''NEXT'''
1 FS?
≫ ≫ '<span style="color:blue">SQFREE?</span>' STO
≪ {} ROT ROT '''FOR''' n '''IF''' n <span style="color:blue">SQFREE?</span> '''THEN''' n + '''END NEXT'''
≫ '<span style="color:blue">TASK1</span>' STO
≪ 0 ROT ROT '''FOR''' n '''IF''' n <span style="color:blue">SQFREE?</span> '''THEN''' 1 + '''END NEXT'''
≫ '<span style="color:blue">TASK2</span>' STO
 
1 145 <span style="color:blue">TASK1</span>
1 1000 <span style="color:blue">TASK2</span>
{{out}}
<pre>
2: { 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 }
1: 608
</pre>
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">require "prime"
 
class Integer
Line 1,639 ⟶ 2,713:
puts "#{count} square-frees upto #{n}" if markers.include?(n)
end
</syntaxhighlight>
</lang>
{{out}}
<pre>1 2 3 5 6 7 10 11 13 14 15 17 19 21 22 23 26 29 30 31
Line 1,670 ⟶ 2,744:
 
</pre>
 
=={{header|Rust}}==
{{trans|C++}}
<syntaxhighlight lang="rust">fn square_free(mut n: usize) -> bool {
if n & 3 == 0 {
return false;
}
let mut p: usize = 3;
while p * p <= n {
let mut count = 0;
while n % p == 0 {
count += 1;
if count > 1 {
return false;
}
n /= p;
}
p += 2;
}
true
}
 
fn print_square_free_numbers(from: usize, to: usize) {
println!("Square-free numbers between {} and {}:", from, to);
let mut line = String::new();
for i in from..=to {
if square_free(i) {
if !line.is_empty() {
line.push_str(" ");
}
line.push_str(&i.to_string());
if line.len() >= 80 {
println!("{}", line);
line.clear();
}
}
}
if !line.is_empty() {
println!("{}", line);
}
}
 
fn print_square_free_count(from: usize, to: usize) {
let mut count = 0;
for i in from..=to {
if square_free(i) {
count += 1;
}
}
println!(
"Number of square-free numbers between {} and {}: {}",
from, to, count
)
}
 
fn main() {
print_square_free_numbers(1, 145);
print_square_free_numbers(1000000000000, 1000000000145);
let mut n: usize = 100;
while n <= 1000000 {
print_square_free_count(1, n);
n *= 10;
}
}</syntaxhighlight>
 
{{out}}
<pre>
Square-free numbers between 1 and 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 numbers between 1000000000000 and 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
Number of square-free numbers between 1 and 100: 61
Number of square-free numbers between 1 and 1000: 608
Number of square-free numbers between 1 and 10000: 6083
Number of square-free numbers between 1 and 100000: 60794
Number of square-free numbers between 1 and 1000000: 607926
</pre>
===Rust FP===
<syntaxhighlight lang="rust">fn square_free(x: usize) -> bool {
fn iter(x: usize, start: usize, prev: usize) -> bool {
let limit = (x as f64).sqrt().ceil() as usize;
match (start..=limit).skip_while(|i| x % i > 0).next() {
Some(v) => if v == prev {false}
else {iter(x / v, v, v)},
None => x != prev
}
}
iter(x, 2, 0)
}
 
fn main() {
for (up, to, nl_limit) in vec!((1, 145, 20), (1000000000000, 1000000000145, 6)) {
let free_nums = (up..=to).into_iter().filter(|&sf| square_free(sf));
println!("square_free numbers between {} and {}:", up, to);
for (index, free_num) in free_nums.enumerate() {
let spnl = if (index + 1) % nl_limit > 0 {' '} else {'\n'};
print!("{:3}{}", free_num, spnl)
}
println!("\n");
}
 
for limit in (2..7).map(|e| 10usize.pow(e)) {
let start = std::time::Instant::now();
let number = (1..=limit).into_iter().filter(|&sf| square_free(sf)).count();
let duration = start.elapsed().as_millis();
println!("Number of square-free numbers between 1 and {:7}: {:6} [time(ms) {:5}]",
limit, number, duration)
}
}</syntaxhighlight>
{{out}}
<pre>square_free numbers between 1 and 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 numbers between 1000000000000 and 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
 
Number of square-free numbers between 1 and 100: 61 [time(ms) 0]
Number of square-free numbers between 1 and 1000: 608 [time(ms) 0]
Number of square-free numbers between 1 and 10000: 6083 [time(ms) 2]
Number of square-free numbers between 1 and 100000: 60794 [time(ms) 62]
Number of square-free numbers between 1 and 1000000: 607926 [time(ms) 1638]</pre>
 
=={{header|Scala}}==
This example uses a brute-force approach to check whether a number is square-free, and builds a lazily evaluated list of all square-free numbers with a simple filter. To get the large square-free numbers, it avoids computing the beginning of the list by starting the list at a given number.
<syntaxhighlight lang="scala">import spire.math.SafeLong
import spire.implicits._
 
import scala.annotation.tailrec
 
object SquareFreeNums {
def main(args: Array[String]): Unit = {
println(
s"""|1 - 145:
|${formatTable(sqrFree.takeWhile(_ <= 145).toVector, 10)}
|
|1T - 1T+145:
|${formatTable(sqrFreeInit(1000000000000L).takeWhile(_ <= 1000000000145L).toVector, 6)}
|
|Square-Free Counts...
|100: ${sqrFree.takeWhile(_ <= 100).length}
|1000: ${sqrFree.takeWhile(_ <= 1000).length}
|10000: ${sqrFree.takeWhile(_ <= 10000).length}
|100000: ${sqrFree.takeWhile(_ <= 100000).length}
|1000000: ${sqrFree.takeWhile(_ <= 1000000).length}
|""".stripMargin)
}
def chkSqr(num: SafeLong): Boolean = !LazyList.iterate(SafeLong(2))(_ + 1).map(_.pow(2)).takeWhile(_ <= num).exists(num%_ == 0)
def sqrFreeInit(init: SafeLong): LazyList[SafeLong] = LazyList.iterate(init)(_ + 1).filter(chkSqr)
def sqrFree: LazyList[SafeLong] = sqrFreeInit(1)
def formatTable(lst: Vector[SafeLong], rlen: Int): String = {
@tailrec
def fHelper(ac: Vector[String], src: Vector[String]): String = {
if(src.nonEmpty) fHelper(ac :+ src.take(rlen).mkString, src.drop(rlen))
else ac.mkString("\n")
}
val maxLen = lst.map(n => f"${n.toBigInt}%,d".length).max
val formatted = lst.map(n => s"%,${maxLen + 2}d".format(n.toBigInt))
fHelper(Vector[String](), formatted)
}
}</syntaxhighlight>
 
{{out}}
<pre>1 - 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
 
1T - 1T+145:
1,000,000,000,001 1,000,000,000,002 1,000,000,000,003 1,000,000,000,005 1,000,000,000,006 1,000,000,000,007
1,000,000,000,009 1,000,000,000,011 1,000,000,000,013 1,000,000,000,014 1,000,000,000,015 1,000,000,000,018
1,000,000,000,019 1,000,000,000,021 1,000,000,000,022 1,000,000,000,023 1,000,000,000,027 1,000,000,000,029
1,000,000,000,030 1,000,000,000,031 1,000,000,000,033 1,000,000,000,037 1,000,000,000,038 1,000,000,000,039
1,000,000,000,041 1,000,000,000,042 1,000,000,000,043 1,000,000,000,045 1,000,000,000,046 1,000,000,000,047
1,000,000,000,049 1,000,000,000,051 1,000,000,000,054 1,000,000,000,055 1,000,000,000,057 1,000,000,000,058
1,000,000,000,059 1,000,000,000,061 1,000,000,000,063 1,000,000,000,065 1,000,000,000,066 1,000,000,000,067
1,000,000,000,069 1,000,000,000,070 1,000,000,000,073 1,000,000,000,074 1,000,000,000,077 1,000,000,000,078
1,000,000,000,079 1,000,000,000,081 1,000,000,000,082 1,000,000,000,085 1,000,000,000,086 1,000,000,000,087
1,000,000,000,090 1,000,000,000,091 1,000,000,000,093 1,000,000,000,094 1,000,000,000,095 1,000,000,000,097
1,000,000,000,099 1,000,000,000,101 1,000,000,000,102 1,000,000,000,103 1,000,000,000,105 1,000,000,000,106
1,000,000,000,109 1,000,000,000,111 1,000,000,000,113 1,000,000,000,114 1,000,000,000,115 1,000,000,000,117
1,000,000,000,118 1,000,000,000,119 1,000,000,000,121 1,000,000,000,122 1,000,000,000,123 1,000,000,000,126
1,000,000,000,127 1,000,000,000,129 1,000,000,000,130 1,000,000,000,133 1,000,000,000,135 1,000,000,000,137
1,000,000,000,138 1,000,000,000,139 1,000,000,000,141 1,000,000,000,142 1,000,000,000,145
 
Square-Free Counts...
100: 61
1000: 608
10000: 6083
100000: 60794
1000000: 607926</pre>
 
=={{header|Sidef}}==
In Sidef, the functions ''is_square_free(n)'' and ''square_free_count(min, max)'' are built-in. However, we can very easily reimplement them in Sidef code, as fast integer factorization methods are also available in the language.
 
<langsyntaxhighlight lang="ruby">func is_square_free(n) {
 
n.abs! if (n < 0)
Line 1,707 ⟶ 3,016:
var c = square_free_count(10**n)
say "The number of square─free numbers between 1 and 10^#{n} (inclusive) is: #{c}"
}</langsyntaxhighlight>
 
{{out}}
Line 1,744 ⟶ 3,053:
The number of square─free numbers between 1 and 10^5 (inclusive) is: 60794
The number of square─free numbers between 1 and 10^6 (inclusive) is: 607926
</pre>
 
=={{header|Swift}}==
 
{{libheader|AttaSwift BigInt}}
 
<syntaxhighlight lang="text">import BigInt
import Foundation
 
extension BinaryInteger {
@inlinable
public var isSquare: Bool {
var x = self / 2
var seen = Set([x])
 
while x * x != self {
x = (x + (self / x)) / 2
 
if seen.contains(x) {
return false
}
 
seen.insert(x)
}
 
return true
}
 
@inlinable
public var isSquareFree: Bool {
return factors().dropFirst().reduce(true, { $0 && !$1.isSquare })
}
 
@inlinable
public func factors() -> [Self] {
let maxN = Self(Double(self).squareRoot())
var res = Set<Self>()
 
for factor in stride(from: 1, through: maxN, by: 1) where self % factor == 0 {
res.insert(factor)
res.insert(self / factor)
}
 
return res.sorted()
}
}
 
let sqFree1to145 = (1...145).filter({ $0.isSquareFree })
 
print("Square free numbers in range 1...145: \(sqFree1to145)")
 
let sqFreeBig = (BigInt(1_000_000_000_000)...BigInt(1_000_000_000_145)).filter({ $0.isSquareFree })
 
print("Square free numbers in range 1_000_000_000_000...1_000_000_000_045: \(sqFreeBig)")
 
var count = 0
 
for n in 1...1_000_000 {
if n.isSquareFree {
count += 1
}
 
switch n {
case 100, 1_000, 10_000, 100_000, 1_000_000:
print("Square free numbers between 1...\(n): \(count)")
case _:
break
}
}</syntaxhighlight>
 
{{out}}
 
<pre>Square free numbers in range 1...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 numbers in range 1_000_000_000_000...1_000_000_000_045: [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]
Square free numbers between 1...100: 61
Square free numbers between 1...1000: 608
Square free numbers between 1...10000: 6083
Square free numbers between 1...100000: 60794
Square free numbers between 1...1000000: 607926</pre>
 
=={{header|Tcl}}==
<syntaxhighlight lang="tcl">proc isSquarefree {n} {
for {set d 2} {($d * $d) <= $n} {set d [expr {($d+1)|1}]} {
if {0 == ($n % $d)} {
set n [expr {$n / $d}]
if {0 == ($n % $d)} {
return 0 ;# no, just found dup divisor
}
}
}
return 1 ;# yes, no dup divisor found
}
 
proc unComma {str {comma ,}} {
return [string map [list $comma {}] $str]
}
 
proc showRange {lo hi} {
puts "Square-free integers in range $lo..$hi are:"
set lo [unComma $lo]
set hi [unComma $hi]
set L [string length $hi]
set perLine 5
while {($perLine * 2 * ($L+1)) <= 80} {
set perLine [expr {$perLine * 2}]
}
set k 0
for {set n $lo} {$n <= $hi} {incr n} {
if {[isSquarefree $n]} {
puts -nonewline " [format %${L}s $n]"
incr k
if {$k >= $perLine} {
puts "" ; set k 0
}
}
}
if {$k > 0} {
puts ""
}
}
 
proc showCount {lo hi} {
set rangtxt "$lo..$hi"
set lo [unComma $lo]
set hi [unComma $hi]
set k 0
for {set n $lo} {$n <= $hi} {incr n} {
incr k [isSquarefree $n]
}
puts "Counting [format %6s $k] square-free integers in range $rangtxt"
}
 
showRange 1 145
showRange 1,000,000,000,000 1,000,000,000,145
 
foreach H {100 1000 10000 100000 1000000} {
showCount 1 $H
}
</syntaxhighlight>
{{out}}
<pre>Square-free integers in range 1..145 are:
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 in range 1,000,000,000,000..1,000,000,000,145 are:
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
Counting 61 square-free integers in range 1..100
Counting 608 square-free integers in range 1..1000
Counting 6083 square-free integers in range 1..10000
Counting 60794 square-free integers in range 1..100000
Counting 607926 square-free integers in range 1..1000000</pre>
 
=={{header|Visual Basic .NET}}==
{{trans|D}}
<syntaxhighlight lang="vbnet">Module Module1
 
Function Sieve(limit As Long) As List(Of Long)
Dim primes As New List(Of Long) From {2}
Dim c(limit + 1) As Boolean
Dim p = 3L
While True
Dim p2 = p * p
If p2 > limit Then
Exit While
End If
For i = p2 To limit Step 2 * p
c(i) = True
Next
While True
p += 2
If Not c(p) Then
Exit While
End If
End While
End While
For i = 3 To limit Step 2
If Not c(i) Then
primes.Add(i)
End If
Next
Return primes
End Function
 
Function SquareFree(from As Long, to_ As Long) As List(Of Long)
Dim limit = CType(Math.Sqrt(to_), Long)
Dim primes = Sieve(limit)
Dim results As New List(Of Long)
 
Dim i = from
While i <= to_
For Each p In primes
Dim p2 = p * p
If p2 > i Then
Exit For
End If
If (i Mod p2) = 0 Then
i += 1
Continue While
End If
Next
results.Add(i)
i += 1
End While
 
Return results
End Function
 
ReadOnly TRILLION As Long = 1_000_000_000_000
 
Sub Main()
Console.WriteLine("Square-free integers from 1 to 145:")
Dim sf = SquareFree(1, 145)
For index = 0 To sf.Count - 1
Dim v = sf(index)
If index > 1 AndAlso (index Mod 20) = 0 Then
Console.WriteLine()
End If
Console.Write("{0,4}", v)
Next
Console.WriteLine()
Console.WriteLine()
 
Console.WriteLine("Square-free integers from {0} to {1}:", TRILLION, TRILLION + 145)
sf = SquareFree(TRILLION, TRILLION + 145)
For index = 0 To sf.Count - 1
Dim v = sf(index)
If index > 1 AndAlso (index Mod 5) = 0 Then
Console.WriteLine()
End If
Console.Write("{0,14}", v)
Next
Console.WriteLine()
Console.WriteLine()
 
Console.WriteLine("Number of square-free integers:")
For Each to_ In {100, 1_000, 10_000, 100_000, 1_000_000}
Console.WriteLine(" from 1 to {0} = {1}", to_, SquareFree(1, to_).Count)
Next
End Sub
 
End Module</syntaxhighlight>
{{out}}
<pre>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
 
Number of square-free integers:
from 1 to 100 = 61
from 1 to 1000 = 608
from 1 to 10000 = 6083
from 1 to 100000 = 60794
from 1 to 1000000 = 607926</pre>
 
=={{header|Wren}}==
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
 
var isSquareFree = Fn.new { |n|
var i = 2
while (i * i <= n) {
if (n%(i*i) == 0) return false
i = (i > 2) ? i + 2 : i + 1
}
return true
}
 
var ranges = [ [1..145, 3, 20], [1e12..1e12+145, 12, 5] ]
for (r in ranges) {
System.print("The square-free integers between %(r[0].min) and %(r[0].max) inclusive are:")
var count = 0
for (i in r[0]) {
if (isSquareFree.call(i)) {
count = count + 1
System.write("%(Fmt.d(r[1], i)) ")
if (count %r[2] == 0) System.print()
}
}
System.print("\n")
}
System.print("Counts of square-free integers:")
var count = 0
var lims = [0, 100, 1000, 1e4, 1e5, 1e6]
for (i in 1...lims.count) {
System.write(" from 1 to (inclusive) %(Fmt.d(-7, lims[i])) = ")
for (j in lims[i-1]+1..lims[i]) {
if (isSquareFree.call(j)) count = count + 1
}
System.print(count)
}</syntaxhighlight>
 
{{out}}
<pre>
The square-free integers between 1 and 145 inclusive are:
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
 
The square-free integers between 1000000000000 and 1000000000145 inclusive are:
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
 
Counts of square-free integers:
from 1 to (inclusive) 100 = 61
from 1 to (inclusive) 1000 = 608
from 1 to (inclusive) 10000 = 6083
from 1 to (inclusive) 100000 = 60794
from 1 to (inclusive) 1000000 = 607926
</pre>
 
=={{header|zkl}}==
<langsyntaxhighlight 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
Line 1,767 ⟶ 3,443:
}
return(cnt,sink.close());
}</langsyntaxhighlight>
<langsyntaxhighlight 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() });
Line 1,774 ⟶ 3,450:
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(" ") });</langsyntaxhighlight>
{{out}}
<pre style="height:35ex">
Line 1,806 ⟶ 3,482:
</pre>
 
<langsyntaxhighlight lang="zkl">n:=100; do(5){
squareFree(1,n)[0]:
println("%,9d square-free integers from 1 to %,d".fmt(_,n));
n*=10;
}</langsyntaxhighlight>
{{out}}
<pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/282956...353541"