Determine whether an integer is square-free
An integer is called square-free if it is not a multiple of a perfect square other than 1. For example, 42 is square-free, but 44 is not because it is a multiple of the perfect square 4 = 2².
Your task is to write a program or function that takes a positive integer, and returns a truthy value if the integer is square-free and a falsey value otherwise.
This is code golf, the shortest code wins.
The square-free numbers are OEIS sequence A005117 (thanks to Razetime for pointing this out).
Some test cases:
1 true
2 true
3 true
4 false
5 true
6 true
7 true
8 false
9 false
10 true
12 false
14 true
16 false
18 false
20 false
30 true
40 false
50 false
100 false
110 true
111 true
Vyxal, 4 bytes ``` K∆²a ``` …
3y ago
Python3, 39 bytes ```python …
3y ago
Scala, 41 bytes ```scala x=> …
3y ago
Ruby, 27 bytes ```ruby ->n …
3y ago
Japt, 5 bytes k eU …
2y ago
Myby, 12 5 bytes ``` primf=p …
2y ago
J, 7 char ``` ./:q: ``` …
2y ago
MATL, 6 bytes ``` YftuX= `` …
2y ago
J, 17 bytes ```J {{./y|:2+ …
2y ago
BQN, 13 bytesSBCS ```none ∧´ …
3y ago
JavaScript, 31 bytes Output …
2y ago
Factor, 108 bytes ``` USIN …
2y ago
Japt, 6 bytes -1 byte thank …
2y ago
13 answers
Vyxal, 4 bytes
K∆²a
Outputs 0 for square-free, 1 for not.
K # Factors
∆² # Is perfect square
a # Any true?
0 comment threads
Scala, 41 bytes
x=>2 to x forall(d=>x%d+math.sqrt(d)%1>0)
Pretty straightforward
0 comment threads
Myby, 12 5 bytes
primf=primfd
primf : prime factors
= : equals
primfd : unique prime factors
Evaluated as a monadic fork in J (f y) g (h y)
.
The test cases (retested) can be viewed here and were generated using this ruby script.
1 comment thread
J, 7 char
*./~:q:
How it works:
'q:' produces prime factors of number on right
'~:' replaces the first instance of unique numbers with a 1, the rest 0
'*./' tests for all ones
Sample runs:
*./~:q: 30
1
*./~:q: 40
0
*./~:q: 50
0
*./~:q: 100
0
*./~:q: 110
1
*./~:q: 111
1
Alternative 10 char solution:
(#=#@~.)q:
How it works:
'q:' of the number on the right produces its prime factors
'#' counts how many there are
'~.' eliminates repeats.
if the counts of factors before and after removing repeats are equal, then the number is square-free.
Sample runs:
(#@q:=#@~.@q:) 30
1
(#@q:=#@~.@q:) 40
0
(#@q:=#@~.@q:) 50
0
(#@q:=#@~.@q:) 100
0
(#@q:=#@~.@q:) 110
1
(#@q:=#@~.@q:) 111
1
0 comment threads
J, 17 bytes
{{*./y|~*:2+i.y}}
A direct definition closest to Razetime's infuriatingly good train solution. Outputs a non-zero number for true and 0 for false.
0 comment threads
JavaScript, 31 bytes
Outputs 0
for falsey and a non-zero value for truthy. If the 2 values must be consistent then replace the last *
with &&
to output true
instead.
n=>(g=d=>d++>n||n%d**2*g(d))(1)
0 comment threads
Factor, 108 bytes
USING: assocs kernel math math.primes.factors ;
IN: s
: ? ( n -- ? ) group-factors [ nip 2 < ] assoc-all? ;
2 comment threads