7
\$\begingroup\$

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.
\$\endgroup\$
  • 2
    \$\begingroup\$ What do you mean with no builtin functions? If I use haskell, I might not even use + or * - they all are functions. \$\endgroup\$ – FUZxxl Feb 12 '11 at 23:38
  • \$\begingroup\$ @fuzxxl No you can use them, but no functions that directly give you the answer to the question like in Mathematica. \$\endgroup\$ – fR0DDY Feb 13 '11 at 5:38
  • \$\begingroup\$ 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. \$\endgroup\$ – Nabb Feb 13 '11 at 16:02
  • \$\begingroup\$ @nabb Aha! I did not know about it. Anyways it is not against the spirit of analog. \$\endgroup\$ – fR0DDY Feb 13 '11 at 16:16
3
\$\begingroup\$

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)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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.. \$\endgroup\$ – miles Jun 6 '16 at 23:17
6
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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

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

Python solution - 105

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)
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Try using ((a=*1...I)-m).size in the last line. \$\endgroup\$ – Dogbert Feb 13 '11 at 17:33
0
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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);
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – DLosc Nov 25 '14 at 22:42
  • \$\begingroup\$ @DLosc I got a can't cast String to int when I did that. Would have if I could :( \$\endgroup\$ – Compass Nov 25 '14 at 22:43
  • \$\begingroup\$ Huh... even though k is a double? I don't really know Java, but that just seems odd to me. \$\endgroup\$ – DLosc Nov 27 '14 at 5:55
  • \$\begingroup\$ @DLosc I'll check again tomorrow. Maybe I'm confused. \$\endgroup\$ – Compass Nov 27 '14 at 9:53
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.