Le défi

Implémentez le tamis Sundaram pour trouver les nombres premiers ci-dessous n. Prenez un entier en entrée n, et sortez les nombres premiers ci-dessous n. Vous pouvez supposer qu'il nsera toujours inférieur ou égal à un million.

Tamis

1. Commencez par une liste des entiers de 1à n.

2. Supprimez tous les numéros du formulaire i + j + 2ijoù:

   • iet jsont inférieurs à n. jest toujours supérieur ou égal à i, ce qui est supérieur ou égal à 1.
     
     

   • i + j + 2ij est inférieur ou égal à n
     
     

3. Multipliez les nombres restants par 2et ajoutez 1.

Cela donnera tous les nombres premiers (sauf ceux 2qui devraient être inclus dans votre sortie) inférieurs à2n + 2 .

Voici une animation du tamis utilisé pour trouver les nombres premiers ci-dessous 202.

Production

Votre sortie doit être chaque entier premier ≤ n(dans l'ordre croissant) suivi d'une nouvelle ligne:

2
3
5

Où nest 5.

Exemples

> 10
2
3
5
7

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

Les entrées sont désignées par >.

Pyth, 23 octets

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

Manifestation

Implémente vraiment l'algorithme comme indiqué.

Haskell, 93 90 octets

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]

Comment ça marche: [i+j+2*i*j|j<-r,i<-r]sont tous ceux i+j+2ijqui sont supprimés ( \\) de [1..n]. Mettez-les à l'échelle 2x+1et transformez-les en chaîne ( show). Rejoignez NL ( unlines).

Scala, 115 124 122 122 115 114 octets

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

Une fonction anonyme; prend n comme argument et affiche le résultat sur stdout.

JavaScript (ES7), 107105 octets

La compréhension des tableaux est géniale! Mais je me demande pourquoi JS n'a pas de syntaxe de plage (par exemple [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]}

Cela a été testé avec succès dans Firefox 40. Répartition:

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
}

Solution alternative compatible ES6 (111 octets):

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 bienvenues!

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

Et sous une forme lisible

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.

Java8: 168 165 octets

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

Pour un nombre plus grand, un type de données avec une large plage peut être utilisé. Nous n'avons pas besoin d'itérer pour des Nindex entiersN/2 sont suffisants.

Pour bien comprendre ce qui suit est la méthode équivalente.

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

CJam, 35 octets

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

Essayez-le en ligne

Cela semble un peu long par rapport à la solution Pyth d'isaacg, mais c'est ... ce que j'ai.

Explication:

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.

Perl 6 , 96 octets

Si je suis strictement la description, la plus courte que j'ai réussi à obtenir est de 96 octets.

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

Si je pouvais faire l' 2n + 1initialisation du tableau, pré-insérer 2et limiter cela aux seules valeurs inférieures ou égales n; il peut être réduit à 84 octets.

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

Si j'ignore également que jc'est censé être au moins i, je peux le réduire à 82 octets.

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

Exemple d'utilisation:

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)

PHP, 126 octets

$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";

Version en ligne

Julia 0,6 , 65 octets

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

Essayez-le en ligne!

Pas un grand défi en termes de golf, mais je devais juste le faire pour le nom. :)