Sito Sundaram (do znajdowania liczb pierwszych)

13

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

Zach Gates
źródło
W twoim przykładzie n=30brakuje 29 na wyjściu.
isaacg
5
Problem z wyzwaniami wymagającymi użycia określonej metody polega na tym, że nie jest jasne, jakie modyfikacje można wprowadzić. Na przykład Twój opis sprawdza tylko za (i,j)pomocą i<=j, ale wynik nie zmienia się, jeśli zignorujemy to wymaganie. Czy możemy to zrobić, aby zaoszczędzić bajty?
xnor 30.09.15
Nigdy nie powiedziałem, że musisz sprawdzić, czy i <= j. To tylko część działania sita. Tak, możesz pominąć i <= jkod. @xnor
Zach Gates
2
Ile tu mamy swobody? Sito jest równoznaczne z wybraniem wszystkich liczb nieparzystych (ponieważ wyniki są w formie 2n+1), które nie są w formie 2(i + j + 2ij)+1- czy możemy przetestować tę właściwość bezpośrednio na potencjalnych liczbach pierwszych, czy też nasz kod musi w pewnym momencie wykonać czasy 2 plus 1 ?
Martin Ender
1
Jestem trochę zdezorientowany tym, co njest w całości. W opisie metody napisano, że wygeneruje wszystkie liczby pierwsze do 2 * n + 2. Ale w opisie wejścia / wyjścia napisano, że dane wejściowe są n, a dane wyjściowe są zawsze pierwsze n. Czy więc powinniśmy zastosować tę metodę, aby wygenerować wszystkie liczby pierwsze do 2 * n + 2, a następnie upuścić te większe niż ndla wyniku? Czy też powinniśmy obliczyć nw opisie metody na podstawie danych wejściowych n?
Reto Koradi

Odpowiedzi:

7

Pyth, 23 bajty

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

Demonstracja

Naprawdę po prostu implementuje podany algorytm.

isaacg
źródło
3

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

nimi
źródło
1

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.

Ben
źródło
1

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!

ETHprodukcje
źródło
0

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.
Tom Carpenter
źródło
0

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);
}
CoderCroc
źródło
1
N>=2-> N>1? A[i]==0-> A[i]<1?
lirtosiast
@ThomasKwa Tak masz rację. Dzięki.
CoderCroc
0

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.
Reto Koradi
źródło
0

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)
Brad Gilbert b2gills
źródło
0

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

Jörg Hülsermann
źródło
0

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

sundar - Przywróć Monikę
źródło