Wyzwanie

Zaimplementuj sito Sundaram, aby znaleźć liczby pierwsze poniżej n. Weź liczbę całkowitą wejściową ni wyślij liczby pierwsze poniżej n. Możesz założyć, że nzawsze będzie mniejszy lub równy milionowi.

Sito

1. Zacznij od listy liczb całkowitych od 1do n.

2. Usuń wszystkie liczby, które mają postać i + j + 2ij:

   • ii jsą mniejsze niż n. jjest zawsze większa lub równa i, która jest większa lub równa 1.
     
     

   • i + j + 2ij jest mniejsza lub równa n
     
     

3. Pomnóż pozostałe liczby przez 2i dodaj 1.

Spowoduje to, że wszystkie liczby pierwsze (oprócz 2, które powinny być uwzględnione w wynikach) będą mniejsze niż 2n + 2.

Oto animacja sita wykorzystywanego do znajdowania liczb pierwszych poniżej 202.

Wynik

Wynikiem powinna być każda liczba całkowita pierwsza ≤ n(w porządku rosnącym), po której następuje nowa linia:

2
3
5

Gdzie njest 5.

Przykłady

> 10
2
3
5
7

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

Wejścia są oznaczone symbolem >.

Pyth, 23 bajty

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

Demonstracja

Naprawdę po prostu implementuje podany algorytm.

Haskell, 93 90 bajtów

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]

Jak to działa: [i+j+2*i*j|j<-r,i<-r]czy wszystkie i+j+2ijsą usuwane ( \\) z [1..n]. Skaluj 2x+1i zamień je w string ( show). Dołącz za pomocą NL ( unlines).

Scala, 115 124 122 115 114 bajtów

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

Anonimowa funkcja; bierze n jako argument i wypisuje wynik na standardowe wyjście.

JavaScript (ES7), 107 105 bajtów

Rozumienia tablic są niesamowite! Ale zastanawiam się, dlaczego JS nie ma składni zakresu (np. [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]}

Zostało to pomyślnie przetestowane w przeglądarce Firefox 40. Podział:

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
}

Alternatywne rozwiązanie przyjazne dla ES6 (111 bajtów):

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

Sugestie mile widziane!

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

I w czytelnej formie

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 bajtów

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

Aby uzyskać większą liczbę, można użyć typu danych o szerokim zakresie. Nie musimy iterować, ponieważ całe Nindeksy N/2są wystarczające.

Aby właściwie zrozumieć, należy zastosować równoważną metodę.

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 bajtów

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

Wypróbuj online

Wydaje się to dość długie w stosunku do rozwiązania Pyth firmy isaacg, ale to ... to, co mam.

Wyjaśnienie:

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 bajtów

Jeśli ściśle przestrzegam opisu, najkrótszy, jaki udało mi się uzyskać, to 96 bajtów.

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

Gdybym mógł wykonać 2n + 1inicjalizację tablicy, wstępne wstawienie 2i ograniczenie tego tylko do wartości mniejszych lub równych n; można go zmniejszyć do 84 bajtów.

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

Jeśli zignoruję jto, co najmniej tak powinno być i, mogę zmniejszyć to do 82 bajtów.

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

Przykładowe użycie:

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 bajtów

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

Wersja online

Julia 0.6 , 65 bajtów

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

Wypróbuj online!

Nie jest to duże wyzwanie pod względem golfa, ale musiałem to zrobić dla tej nazwy. :)