Square-free integers: Difference between revisions
Content added Content deleted
m (→{{header|Lua}}) |
m (→{{header|Lua}}) |
||
| Line 683: | Line 683: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
This a naive method, runs in about 1 second on LuaJIT. |
This is a naive method, runs in about 1 second on LuaJIT. |
||
<lang lua>function squareFree (n) |
<lang lua>function squareFree (n) |
||
for root = 2, math.sqrt(n) do |
for root = 2, math.sqrt(n) do |
||
Revision as of 08:59, 13 July 2018
You are encouraged to solve this task according to the task description, using any language you may know.
- 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
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <math.h>
- define TRUE 1
- define FALSE 0
- define TRILLION 1000000000000
typedef unsigned char bool; typedef unsigned long long uint64;
void sieve(uint64 limit, uint64 *primes, uint64 *length) {
uint64 i, count, p, p2;
bool *c = calloc(limit + 1, sizeof(bool)); /* composite = TRUE */
primes[0] = 2;
count = 1;
/* no need to process even numbers > 2 */
p = 3;
for (;;) {
p2 = p * p;
if (p2 > limit) break;
for (i = p2; i <= limit; i += 2 * p) c[i] = TRUE;
for (;;) {
p += 2;
if (!c[p]) break;
}
}
for (i = 3; i <= limit; i += 2) {
if (!c[i]) primes[count++] = i;
}
*length = count;
free(c);
}
void squareFree(uint64 from, uint64 to, uint64 *results, uint64 *len) {
uint64 i, j, p, p2, np, count = 0, limit = (uint64)sqrt((double)to);
uint64 *primes = malloc((limit + 1) * sizeof(uint64));
bool add;
sieve(limit, primes, &np);
for (i = from; i <= to; ++i) {
add = TRUE;
for (j = 0; j < np; ++j) {
p = primes[j];
p2 = p * p;
if (p2 > i) break;
if (i % p2 == 0) {
add = FALSE;
break;
}
}
if (add) results[count++] = i;
}
*len = count;
free(primes);
}
int main() {
uint64 i, *sf, len, from = 1, to;
to = 145;
sf = malloc((to - from + 1) * sizeof(uint64));
printf("Square-free integers from 1 to 145:\n");
squareFree(1, 145, sf, &len);
for (i = 0; i < len; ++i) {
if (i > 0 && i % 20 == 0) {
printf("\n");
}
printf("%4lld", sf[i]);
}
printf("\n\nSquare-free integers from %ld to %ld:\n", TRILLION, TRILLION + 145);
squareFree(TRILLION, TRILLION + 145, sf, &len);
for (i = 0; i < len; ++i) {
if (i > 0 && i % 5 == 0) {
printf("\n");
}
printf("%14lld", sf[i]);
}
printf("\n\nNumber of square-free integers:\n");
squareFree(1, 100, sf, &len);
printf(" from %d to %d = %lld\n", 1, 100, len);
/* need to allocate a lot more memory to process remaining cases */
sf = realloc(sf, 1000000 * sizeof(uint64));
squareFree(1, 1000, sf, &len);
printf(" from %d to %d = %lld\n", 1, 1000, len);
squareFree(1, 10000, sf, &len);
printf(" from %d to %d = %lld\n", 1, 10000, len);
squareFree(1, 100000, sf, &len);
printf(" from %d to %d = %lld\n", 1, 100000, len);
squareFree(1, 1000000, sf, &len);
printf(" from %d to %d = %lld\n", 1, 1000000, len);
free(sf);
return 0;
}</lang>
- Output:
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
Factor
The sq-free? word merits some explanation. Per the Wikipedia entry on square-free integers, A positive integer n is square-free if and only if in the prime factorization of n, no prime factor occurs with an exponent larger than one.
For instance, the prime factorization of 12 is 2 * 2 * 3, or in other words, 22 * 3. The 2 repeats, so we know 12 isn't square-free.
<lang factor>USING: formatting grouping io kernel math math.functions
math.primes.factors math.ranges sequences sets ;
IN: rosetta-code.square-free
- sq-free? ( n -- ? ) factors all-unique? ;
! Word wrap for numbers.
- numbers-per-line ( m -- n ) log10 >integer 2 + 80 swap /i ;
- sq-free-show ( from to -- )
2dup "Square-free integers from %d to %d:\n" printf [ [a,b] [ sq-free? ] filter ] [ numbers-per-line group ] bi [ [ "%3d " printf ] each nl ] each nl ;
- sq-free-count ( limit -- )
dup [1,b] [ sq-free? ] count swap "%6d square-free integers from 1 to %d\n" printf ;
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</lang>
- Output:
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
61 square-free integers from 1 to 100
608 square-free integers from 1 to 1000
6083 square-free integers from 1 to 10000
60794 square-free integers from 1 to 100000
607926 square-free integers from 1 to 1000000
FreeBASIC
<lang freebasic>' 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</lang>
- Output:
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 There are 61 square free integers between 1 and 100 There are 608 square free integers between 1 and 1000 There are 6083 square free integers between 1 and 10000 There are 60794 square free integers between 1 and 100000 There are 607926 square free integers between 1 and 1000000
Go
<lang go>package main
import (
"fmt" "math"
)
func sieve(limit uint64) []uint64 {
primes := []uint64{2}
c := make([]bool, limit+1) // composite = true
// no need to process even numbers > 2
p := uint64(3)
for {
p2 := p * p
if p2 > limit {
break
}
for i := p2; i <= limit; i += 2 * p {
c[i] = true
}
for {
p += 2
if !c[p] {
break
}
}
}
for i := uint64(3); i <= limit; i += 2 {
if !c[i] {
primes = append(primes, i)
}
}
return primes
}
func squareFree(from, to uint64) (results []uint64) {
limit := uint64(math.Sqrt(float64(to))) primes := sieve(limit)
outer:
for i := from; i <= to; i++ {
for _, p := range primes {
p2 := p * p
if p2 > i {
break
}
if i%p2 == 0 {
continue outer
}
}
results = append(results, i)
}
return
}
const trillion uint64 = 1000000000000
func main() {
fmt.Println("Square-free integers from 1 to 145:")
sf := squareFree(1, 145)
for i := 0; i < len(sf); i++ {
if i > 0 && i%20 == 0 {
fmt.Println()
}
fmt.Printf("%4d", sf[i])
}
fmt.Printf("\n\nSquare-free integers from %d to %d:\n", trillion, trillion+145)
sf = squareFree(trillion, trillion+145)
for i := 0; i < len(sf); i++ {
if i > 0 && i%5 == 0 {
fmt.Println()
}
fmt.Printf("%14d", sf[i])
}
fmt.Println("\n\nNumber of square-free integers:\n")
fmt.Printf(" from %d to %d = %d\n", 1, 100, len(squareFree(1, 100)))
fmt.Printf(" from %d to %d = %d\n", 1, 1000, len(squareFree(1, 1000)))
fmt.Printf(" from %d to %d = %d\n", 1, 10000, len(squareFree(1, 10000)))
fmt.Printf(" from %d to %d = %d\n", 1, 100000, len(squareFree(1, 100000)))
fmt.Printf(" from %d to %d = %d\n", 1, 1000000, len(squareFree(1, 1000000)))
}</lang>
- Output:
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
Java
<lang java>import java.util.ArrayList; import java.util.List;
public class SquareFree {
private static List<Long> sieve(long limit) {
List<Long> primes = new ArrayList<Long>();
primes.add(2L);
boolean[] c = new boolean[(int)limit + 1]; // composite = true
// no need to process even numbers > 2
long p = 3;
for (;;) {
long p2 = p * p;
if (p2 > limit) break;
for (long i = p2; i <= limit; i += 2 * p) c[(int)i] = true;
for (;;) {
p += 2;
if (!c[(int)p]) break;
}
}
for (long i = 3; i <= limit; i += 2) {
if (!c[(int)i]) primes.add(i);
}
return primes;
}
private static List<Long> squareFree(long from, long to) {
long limit = (long)Math.sqrt((double)to);
List<Long> primes = sieve(limit);
List<Long> results = new ArrayList<Long>();
outer: for (long i = from; i <= to; i++) {
for (long p : primes) {
long p2 = p * p;
if (p2 > i) break;
if (i % p2 == 0) continue outer;
}
results.add(i);
}
return results;
}
private final static long TRILLION = 1000000000000L;
public static void main(String[] args) {
System.out.println("Square-free integers from 1 to 145:");
List<Long> sf = squareFree(1, 145);
for (int i = 0; i < sf.size(); i++) {
if (i > 0 && i % 20 == 0) {
System.out.println();
}
System.out.printf("%4d", sf.get(i));
}
System.out.print("\n\nSquare-free integers");
System.out.printf(" from %d to %d:\n", TRILLION, TRILLION + 145);
sf = squareFree(TRILLION, TRILLION + 145);
for (int i = 0; i < sf.size(); i++) {
if (i > 0 && i % 5 == 0) System.out.println();
System.out.printf("%14d", sf.get(i));
}
System.out.println("\n\nNumber of square-free integers:\n");
long[] tos = {100, 1000, 10000, 100000, 1000000};
for (long to : tos) {
System.out.printf(" from %d to %d = %d\n", 1, to, squareFree(1, to).size());
}
}
}</lang>
- Output:
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
Kotlin
<lang scala>// Version 1.2.50
import kotlin.math.sqrt
fun sieve(limit: Long): List<Long> {
val primes = mutableListOf(2L)
val c = BooleanArray(limit.toInt() + 1) // composite = true
// no need to process even numbers > 2
var p = 3L
while (true) {
val p2 = p * p
if (p2 > limit) break
for (i in p2..limit step 2 * p) c[i.toInt()] = true
do { p += 2 } while (c[p.toInt()])
}
for (i in 3..limit step 2)
if (!c[i.toInt()])
primes.add(i)
return primes
}
fun squareFree(r: LongProgression): List<Long> {
val primes = sieve(sqrt(r.last.toDouble()).toLong())
val results = mutableListOf<Long>()
outer@ for (i in r) {
for (p in primes) {
val p2 = p * p
if (p2 > i) break
if (i % p2 == 0L) continue@outer
}
results.add(i)
}
return results
}
const val TRILLION = 1000_000_000_000L
fun main(args: Array<String>) {
println("Square-free integers from 1 to 145:")
squareFree(1..145L).chunked(20).forEach {
println()
it.forEach { System.out.printf("%4d", it) }
}
println("\n\nSquare-free integers from $TRILLION to ${TRILLION + 145}:")
squareFree(TRILLION..TRILLION + 145).chunked(5).forEach {
println()
it.forEach { print(" $it") }
}
println("\n\nNumber of square-free integers:\n")
val out = fun (i: Long, j: Long) { println(" from $i to $j = ${squareFree(i..j).size}") }
out(1, 100)
out(1, 1000)
out(1, 10_000)
out(1, 100_000)
out(1, 1000_000)
}</lang>
- Output:
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
Lua
This is a naive method, runs in about 1 second on LuaJIT. <lang lua>function squareFree (n)
for root = 2, math.sqrt(n) do if n % (root * root) == 0 then return false end end return true
end
function run (lo, hi, showValues)
io.write("From " .. lo .. " to " .. hi)
io.write(showValues and ":\n" or " = ")
local count = 0
for i = lo, hi do
if squareFree(i) then
if showValues then
io.write(i, "\t")
else
count = count + 1
end
end
end
print(showValues and "\n" or count)
end
local testCases = {
{100, 145, true},
{1000000000000, 1000000000145, true},
{1, 100},
{1, 1000},
{1, 10000},
{1, 100000},
{1, 1000000}
} for _, example in pairs(testCases) do run(unpack(example)) end</lang>
Perl
<lang perl>use ntheory qw/is_square_free moebius/;
sub square_free_count {
my ($n) = @_;
my $count = 0;
foreach my $k (1 .. sqrt($n)) {
$count += moebius($k) * int($n / $k**2);
}
return $count;
}
print "Square─free numbers between 1 and 145:\n"; print join(' ', grep { is_square_free($_) } 1 .. 145), "\n";
print "\nSquare-free numbers between 10^12 and 10^12 + 145:\n"; print join(' ', grep { is_square_free($_) } 1e12 .. 1e12 + 145), "\n";
print "\n"; foreach my $n (2 .. 6) {
my $c = square_free_count(10**$n); print "The number of square-free numbers between 1 and 10^2 (inclusive) is: $c\n";
}</lang>
- Output:
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 10^12 and 10^12 + 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 The number of square-free numbers between 1 and 10^2 (inclusive) is: 61 The number of square-free numbers between 1 and 10^2 (inclusive) is: 608 The number of square-free numbers between 1 and 10^2 (inclusive) is: 6083 The number of square-free numbers between 1 and 10^2 (inclusive) is: 60794 The number of square-free numbers between 1 and 10^2 (inclusive) is: 607926
Perl 6
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>
- Output:
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
REXX
<lang rexx>/*REXX program displays square─free numbers (integers > 1) up to a specified limit. */ numeric digits 20 parse arg LO HI . /*obtain optional arguments from the CL*/ if LO== | LO=="," then LO= 1 /*Not specified? Then use the default.*/ 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.*/
else do; say $; $=j; end /*display a line of numbers.*/
end /*j*/
TheNum= 'The number of square─free numbers between ' if HI<0 then say TheNum LO " and " abs(HI) ' (inclusive) is: ' count if $\== then say $ /*are there any residuals to display ? */ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ isSquareFree: procedure; parse arg #; if #<1 then return 0 /*is the number too small?*/
limit= iSqrt(#) /*obtain the integer square root of #.?*/
odd=#//2 /*ODD=1 if # is odd, ODD=0 if even.*/
do k=2+odd to limit by 1+odd /*use all numbers, or just odds*/
if # // k**2 == 0 then return 0 /*Is # divisible by a square? */
end /*k*/ /* [↑] Yes? Then ^ square─free*/
return 1
/*──────────────────────────────────────────────────────────────────────────────────────*/ iSqrt: procedure; parse arg x; r=0; q=1; do while q<=x; q=q*4; end
do while q>1; q=q%4; _=x-r-q; r=r%2; if _>=0 then do;x=_;r=r+q; end; end
return r /*R is the integer square root of X. */</lang>
This REXX program makes use of linesize REXX program (or BIF) which is used to determine the screen width (or linesize) of the terminal (console); not all REXXes have this BIF.
The LINESIZE.REX REXX program is included here ──► LINESIZE.REX.
- output when using the default input:
(Shown at three-quarter size.)
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
- output when using the input of: 1000000000000 1000000000145
(Shown at three-quarter size.)
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
- output when using the (separate runs) inputs of: 1 -100 (and others)
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
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.
<lang ruby>func is_square_free(n) {
n.abs! if (n < 0) return false if (n == 0)
n.factor_exp + 1,1 -> all { .[1] == 1 }
}
func square_free_count(n) {
1 .. n.isqrt -> sum {|k|
moebius(k) * idiv(n, k*k)
}
}
func display_results(a, c, f = { _ }) {
a.each_slice(c, {|*s|
say s.map(f).join(' ')
})
}
var a = range( 1, 145).grep {|n| is_square_free(n) } var b = range(1e12, 1e12+145).grep {|n| is_square_free(n) }
say "There are #{a.len} square─free numbers between 1 and 145:" display_results(a, 17, {|n| "%3s" % n })
say "\nThere are #{b.len} square─free numbers between 10^12 and 10^12 + 145:" display_results(b, 5) say
for (2 .. 6) { |n|
var c = square_free_count(10**n)
say "The number of square─free numbers between 1 and 10^#{n} (inclusive) is: #{c}"
}</lang>
- Output:
There are 90 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 There are 89 square─free numbers between 10^12 and 10^12 + 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 The number of square─free numbers between 1 and 10^2 (inclusive) is: 61 The number of square─free numbers between 1 and 10^3 (inclusive) is: 608 The number of square─free numbers between 1 and 10^4 (inclusive) is: 6083 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
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 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());
}</lang> <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>
- Output:
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
<lang zkl>n:=100; do(5){
squareFree(1,n)[0]:
println("%,9d square-free integers from 1 to %,d".fmt(_,n));
n*=10;
}</lang>
- Output:
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