# Square free Numbers

Given a number N, write the shortest complete program to find the number of square-free integers below N.

Sample Input
100000
Sample Output
60794


Constraints:

1. Should work for all positive N below 1,000,000
2. Should not take more than 10 secs.
• What do you mean with no builtin functions? If I use haskell, I might not even use + or * - they all are functions. – FUZxxl Feb 12 '11 at 23:38
• @fuzxxl No you can use them, but no functions that directly give you the answer to the question like in Mathematica. – fR0DDY Feb 13 '11 at 5:38
• Basically a copy of the following endless problem on anagol (that one has the limit fixed at 500): golf.shinh.org/p.rb?Square+free+integer. – Nabb Feb 13 '11 at 16:02
• @nabb Aha! I did not know about it. Anyways it is not against the spirit of analog. – fR0DDY Feb 13 '11 at 16:16

## J, 21 chars

+/(]=&#~.)@:q:"0>:i.N


Checks for each integer from 1 to N if any prime factor appears more than once.

eg:

+/(]=&#~.)@:q:"0>:i.10000
6083
+/(]=&#~.)@:q:"0>:i.100000
60794


Takes ~3secs for N=1,000,000 (@2GHz,1core)

• I'm not sure if it existed before but as of J 6.02, there is the ~: verb known as NubSieve which returns a mask based on the input array where each index is 1 the first time it appears and 0 if it appears again. This allows for a solution using 18 bytes as [:+/*/@~:@q:@>:@i.. – miles Jun 6 '16 at 23:17

## Python 2: 71 chars

i=n=input()
A=[1]*n
while~-i:A[i*i::i*i]=~-n/i/i*[0];i-=1
print~-sum(A)


Basically an optimization of Keith Randall's solution of zeroing out numbers that are multiples of squares. The main improvement is directly zeroing out the sublist A[i*i::i*i], which requires awkwardly calculating its length or else Python refuses to do the slice assignment.

Lots of ~- are used for -1. The ~-sum(A) corrects for 0 being falsely counted as a squarefree number.

## Python, 84 characters

n=input()
R=range(n)
A=[1]*n
for i in R[2:]:
for x in R[::i*i]:A[x]=0
print sum(A)


Java Solution

import java.io.*;
public class Main{
public static void main(String[] args)throws Exception {
int list[]=new int[N];
for (int i=0;i<N;i++){
list[i]=(i+1);
}
for (int i=1;i<N;i++){
if (Math.sqrt(list[i])-Math.floor(Math.sqrt(list[i]))==0){
for(int j=i;j<N;j+=(i+1)){
list[j]=-1;
}}}
int c=0;
for (int i=0;i<N;i++){
if (list[i]!=-1){
c++;
}}System.out.println(c);}}


IDEONE http://ideone.com/Yf467

• Hope using sqrt is fine? – Aman ZeeK Verma Feb 12 '11 at 20:36
• The question says complete program. – fR0DDY Feb 12 '11 at 20:45
• :( that costed me a lot of characters :( – Aman ZeeK Verma Feb 12 '11 at 20:58
• It's almost a crime to golf in Java. :) – fR0DDY Feb 13 '11 at 5:37

# Python solution - 105

s=input()
C=set()
for q in [k*k for k in range(2,s+1)]:
i=1
print s-len(C)


# Wolfram Language (Mathematica), 24 bytes

Count[√Range@#,_^_|1]&


Try it online!

SquareFreeQ is too long anyways.

# APL (Dyalog Extended), 11 bytes

+/≡∘∪⍨⍤⍭¨⍤⍳


Try it online!

Bubbler's tacit form. (-4 bytes)

# APL (Dyalog Extended), 16 bytes

{+/{(⊢≡∪)⍭⍵}¨⍳⍵}


Try it online!

Same approach as the J answer, 100000 runs under 10 secs on tio, so it should be all good.

## Explanation

{+/{(⊢≡∪)⍭⍵}¨⍳⍵}
{(⊢≡∪)⍭⍵}     square-free checking function
{     ⍭⍵}     prime factors of ⍵
(⊢≡∪)        are the unique values equal to the originals?
function ends
¨⍳⍵  map function to range 1-n
+/              sum the resulting boolean array

• Tacit 12 bytes. – Bubbler Sep 20 '20 at 23:28
• (⊢≡∪)≡∘∪⍨ – Adám Apr 19 at 9:04

# Ruby - 119 114

I=gets.to_i
m=[]
(s=->i{(I>i*i)?s[i+1]+[i*i]:[]})[2].map{|s|(1..I).map{|x|s*x<I||break;m<<s*x}}
p ([*1...I]-m).size

• Try using ((a=*1...I)-m).size in the last line. – Dogbert Feb 13 '11 at 17:33

## C

144 Chars

#define m 1000001
x[m];
main(s,o,f){
for(o=2;o*o<m;o++)
for(f=s=o*o;f<m;f+=s)x[f]=1;
scanf("%d",&f);
for(s=0,o=1;o<f;o++)if(!x[o])s++;
printf("%d",s);
}


Instantaneous Solution on my crummy PC! :)

# Java - 278 Characters

A golfed version of the Java answer already demonstrated here without changing the spirit of the answer, because the original poster's idea golfed could have saved 50%, which is huge compared to most other languages!

class T {public static void main(String[] a) {int n,i,j;double k;n=Integer.parseInt(a[0]);int l[]=new int[n];for(i=0;i<n;)l[i]=1+i++;for (i=1;i<n;i++) {k=Math.sqrt(l[i]);if(k==Math.floor(k))for (j=i;j<n;j+=i+1)l[j]=-1;}j=0;for(i=0;i<n;)if(l[i++]!=-1)j++;System.out.println(j);}}


Specifically, a few Java golfing tricks were used to optimize this:

• Removed long variable names
• Removed the use of a Reader in favor of using an argument (saves a huge amount of characters, including import, Exception handling, and casting the reader in general)
• Removed extra brackets and parentheses using single-line actions for ifs and fors where applicable
• Declare ints beforehand together to reduce calls to int
• Declare a double and optimize square calculation
• Extracted ++ where possible

This shows that the original ungolfed solution of 565 characters can be brought down to a very respectable <300 character answer even with a more structured language like Java.

### Ungolfed

class T {
public static void main(String[] a) {
int n, i, j;
double k;
n = Integer.parseInt(a[0]);
int l[] = new int[n];
for (i = 0; i < n;)
l[i] = 1 + i++;
for (i = 1; i < n; i++) {
k = Math.sqrt(l[i]);
if (k == Math.floor(k))
for (j = i; j < n; j += i + 1)
l[j] = -1;
}
j = 0;
for (i = 0; i < n;)
if (l[i++] != -1)
j++;
System.out.println(j);
}
}

• Can be 272 with some stray whitespace removed. I think you can use (int)k instead of Math.floor(k), bringing the total down to 265. – DLosc Nov 25 '14 at 22:42
• @DLosc I got a can't cast String to int when I did that. Would have if I could :( – Compass Nov 25 '14 at 22:43
• Huh... even though k is a double? I don't really know Java, but that just seems odd to me. – DLosc Nov 27 '14 at 5:55
• @DLosc I'll check again tomorrow. Maybe I'm confused. – Compass Nov 27 '14 at 9:53

# GNU coreutils, 44 bytes

seq $1|factor|sed '$d;/$$.*$$\1\b/d'|wc -l


This factors every number up to N, removes the last line (as we're only counting results strictly less than N), and removes any line with a repeated word. Finally, we count the remaining lines.

The regular expression $$.*$$\1\b looks over-generous, but it takes advantage of what we know about the output of factor - the factors will be in ascending order, with exactly one space between each.

With N=1,000,000, this completes on my machine in about ¼ second.

# Japt-x, 8 bytes

õ_=k)eZâ


Try it

õ_=k)eZâ     :Implicit input of integer U
õ            :Range [1,U]
_           :Map each Z
=          :  Reassign to Z
k         :  Prime factors of Z
)        :  End reassignment
e       :  Test equality with
Zâ     :  Z deduplicated
:Implicit output of sum of resulting array