13
\$\begingroup\$

The Challenge

Implement the Sundaram sieve for finding prime numbers below n. Take an input integer, n, and output the prime numbers below n. You can assume that n will always be less than or equal to one million.


Sieve

  1. Start with a list of the integers from 1 to n.

  2. Remove all numbers that are in the form i + j + 2ij where:

    • i and j are less than n. j is always greater than or equal to i, which is greater than or equal to 1.

    • i + j + 2ij is less than or equal to n

  3. Multiply the remaining numbers by 2, and add 1.

This will yield all the prime numbers (except 2, which should be included in your output) less than 2n + 2.


Here is an animation of the sieve being used to find primes below 202.


Output

Your output should be every prime integer ≤ n (in ascending order) followed by a newline:

2
3
5

Where n is 5.


Examples

> 10
2
3
5
7

> 30
2
3
5
7
11
13
17
19
23
29

Inputs are denoted by >.

\$\endgroup\$
  • \$\begingroup\$ Your example with n=30 is missing 29 in the output. \$\endgroup\$ – isaacg Sep 30 '15 at 18:57
  • 5
    \$\begingroup\$ A trouble with challenges that ask to use a specific method is that it's not clear what modifications one can make. For example, your description checks only (i,j) with i<=j, but the result doesn't change if we ignore this requirement. Can we do so to save bytes? \$\endgroup\$ – xnor Sep 30 '15 at 19:25
  • \$\begingroup\$ I never said that you had to check if i <= j. It's just part of how the sieve works. So yes, you can leave out the i <= j in your code. @xnor \$\endgroup\$ – Zach Gates Sep 30 '15 at 19:37
  • 2
    \$\begingroup\$ How much leeway do we have here? The sieve is equivalent to selecting all odd numbers (because the results are of the form 2n+1) which are not of the form 2(i + j + 2ij)+1 - can we test this property directly on the potential primes or does our code have to do the times 2 plus 1 at some point? \$\endgroup\$ – Martin Ender Sep 30 '15 at 20:22
  • 1
    \$\begingroup\$ I'm a little confused by what n is in the whole thing. In the method description, it says that it will generate all primes up to 2 * n + 2. But in the input/output description, it says that the input is n, and the output all primes up to n. So are we supposed to apply the method to generate all primes up to 2 * n + 2, and then drop the ones larger than n for the output? Or should we calculate the n in the method description from the input n? \$\endgroup\$ – Reto Koradi Oct 1 '15 at 3:56

10 Answers 10

7
\$\begingroup\$

Pyth, 23 bytes

2j@JSQmhyd-Jm+sdy*Fd^J2

Demonstration

Really just implements the algorithm as given.

\$\endgroup\$
3
\$\begingroup\$

Haskell, 93 90 bytes

import Data.List
g n=unlines[show$2*x+1|r<-[[1..n]],x<-2:(r\\[i+j+2*i*j|j<-r,i<-r]),2*x<n]

How it works: [i+j+2*i*j|j<-r,i<-r] are all i+j+2ij which are removed (\\) from [1..n]. Scale to 2x+1 and turn them into a string (show). Join with NL (unlines).

\$\endgroup\$
1
\$\begingroup\$

Scala, 115 124 122 115 114 bytes

n=>{println(2);for{m<-1 to n;if !(for{j<-1 to n;i<-1 to j}yield i+j+2*i*j).contains(m);o=2*m+1;if o<=n}println(o)}

An anonymous function; takes n as an argument and prints the result to stdout.

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES7), 107 105 bytes

Array comprehensions are awesome! But I wonder why JS has no range syntax (e.g. [1..n])...

n=>{for(a=[i=1];i<n;a[i++]=i);for(i=0;i++<n;)for(j=0;j<n;a[i+j+++2*i*j]=0);return[for(i of a)if(i)i*2+1]}

This was tested successfully in Firefox 40. Breakdown:

n=>{
  for(a=[i=1];i<n;a[i++]=i); // fill a list with 1..n
  for(i=0;i++<n;)            // for each integer i in 0..n
    for(j=0;j<n;)            //   for each integer j in 0..n
      a[i+j+++2*i*j-1]=0;    //     set the corresponding item of the list to 0
  return[for(i of a)         // filter the list by:
          if(i)              //   item != 0 AND item != undefined
           i*2+1]            // and return each result * 2 + 1
}

Alternative, ES6-friendly solution (111 bytes):

n=>{for(a=[i=1];i<n;a[i++]=i);for(i=0;i++<n;)for(j=0;j<n;a[i+j+++2*i*j]=0);return a.filter(x=>x).map(x=>x*2+1)}

Suggestions welcome!

\$\endgroup\$
0
\$\begingroup\$

MATLAB, 98

n=1:input('');m=n;for p=m for i=1:p j=i:p;for k=i+j+2*i*j n(n==k)=[];end;end;end;disp(2*n'+1);

And in a readable form

n=1:input(''); %Ask for the input number (e.g. 100) and form a range
m=n; %Back up the range as we will be editing 'n', but need 'm' as a loop list
for p=m %For each number between 1 and n inclusive
    for i=1:p %'i' is all numbers greater than or equal to 1 up to p
        j=i:p; %'j' is all numbers greater than or equal to i up to p
        for k=i+j+2*i*j %Calculate the numbers to remove, and loop through them
            n(n==k)=[]; %Remove that value from the 'n' array
        end
    end
end
disp([2;2*n'+1]); %An display the list including the number 2 seperated by a new line.
\$\endgroup\$
0
\$\begingroup\$

Java8 : 168 165 bytes

N->{int[]A=new int[N*N];int i=1,j;N=N/2;for(;i<N;i++)for(j=i;j<N;)A[i+j+2*i*j++]=1;System.out.println(N>1?2:\"\");for(i=1;i<N;i++)if(A[i]<1)System.out.println(2*i+1);}

For more bigger number data type with wide range can be used. We do not need to iterate for whole N indexes N/2 is sufficient.

To understand properly following is the equivalent method.

static void findPrimeSundar(int N){
    int[] A = new int[N*N];
    int i=1,j;
    N=N/2;
    for(;i<N;i++)
      for(j=i;j<N;)
        A[i+j+2*i*j++]=1;
    System.out.println(N>1?2:"");
    for(i=1;i<N;i++)
        if(A[i]<1)System.out.println(2*i+ 1);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ N>=2 -> N>1? A[i]==0 -> A[i]<1? \$\endgroup\$ – lirtosiast Oct 1 '15 at 4:18
  • \$\begingroup\$ @ThomasKwa Yes you are right. Thanks. \$\endgroup\$ – CoderCroc Oct 1 '15 at 4:26
0
\$\begingroup\$

CJam, 35 bytes

2li:V,:)__2m*{_:+\:*2*+}%m2f*:)&+N*

Try it online

This seems somewhat lengthy relative to isaacg's Pyth solution, but it's... what I have.

Explanation:

2       Push a 2, will be part of final output.
li      Get input and convert to integer n.
:V      Save in variable V for later use.
,       Generate list [0 ... n-1].
:)      Increment list elements to get list [1 ... n].
__      Create two copies, one for sieve, and for clamping results.
2m*     Cartesian power, generating all i,k pairs.
{       Loop over all i,j pairs.
  _     Copy pair.
  :+    Calculate sum i + j.
  \     Swap copy of pair to top.
  :*    Calculate product i * j.
  2*    Multiply by 2, to get 2 * i * j.
  +     Add both values, to get i + j + 2 * i * j.
}%      End loop over all i,j pairs.
m       Sieve operation, remove the calculated values from the list of all values.
2f*     Multiply the remaining values by 2...
:)      ... and add 1 to the. We now have the list of all primes up to 2 * n + 2.
&       Intersect with [1 ... n] list, because output is only values <= n.
+       Concatenate with the 2 we pushed at the start.
N*      Join with newlines.
\$\endgroup\$
0
\$\begingroup\$

Perl 6, 96 bytes

If I strictly follow the description the shortest I managed to get is 96 bytes.

->\n {$_=@=1..n;for 1..n {for $^i..n {.[$i+$^j+2*$i*$j-1]=0}};2,|.[0..n].map(* *2+1).grep(3..n)}
->\n {
  $_=@=1..n; # initialize array
  for 1..n { # $i
    for $^i..n { # $j
      .[$i+$^j+2*$i*$j-1]=0 # remove value
    }
  };
  2,|.[0..n].map(* *2+1).grep(3..n)
}

If I could do the 2n + 1 on initialization of the array, pre-inserting 2, and limiting that to only the values less than or equal to n; it can be reduced to 84 bytes.

->\n {$_=@=2,{++$*2+1}...^*>n;for 1..n {for $^i..n {.[$i+$^j+2*$i*$j]=$}};.grep(?*)}

If I also ignore that j is supposed to be at least i, I can reduce it to 82 bytes.

->\n {$_=@=2,{++$*2+1}...^*>n;for 1..n X 1..n ->(\i,\j){.[i+j+2*i*j]=$};.grep(?*)}

Example usage:

my $code = ->\n {...} # insert one of the lambdas from above

say $code(30).join(',');
# 2,3,5,7,11,13,17,19,23,29

my &code = $code;
say code 11;
# (2 3 5 7 11)
\$\endgroup\$
0
\$\begingroup\$

PHP, 126 Bytes

$r=range(1,$n=$argn/2-1);for(;++$i**2<=$n;)for($j=$i;$n>=$d=$j+$i+2*$i*$j++;)unset($r[$d-1]);foreach($r as$v)echo 1+2*$v."\n";

Online Version

\$\endgroup\$
0
\$\begingroup\$

Julia 0.6, 65 bytes

n->[2;(p=setdiff(1:n,[i+j+2i*j for i=1:n for j=i:n])*2+1)[p.<=n]]

Try it online!

Not a great challenge in terms of golfing, but I just had to do it for the name. :)

\$\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.