Square free Numbers

Question

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.
3. Please do not use built in functions, please.

Answer 1

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.

Answer 2

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)

Answer 3

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)

Answer 4

Java Solution

import java.io.*;
    public class Main{
            public static void main(String[] args)throws Exception {
              int N=Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
              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

Answer 5

Wolfram Language (Mathematica), 24 bytes

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

Try it online!

SquareFreeQ is too long anyways.

Answer 6

APL (Dyalog Extended), 11 bytes

+/≡∘∪⍨⍤⍭¨⍤⍳

Try it online!

Bubbler's tacit form. (-4 bytes)

-1 byte from Adám.

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

Answer 7

Python - 105 bytes

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

Answer 8

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

Answer 9

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! :)

Answer 10

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);
    }
}

Answer 11

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.

Answer 12

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