Wydrukuj brakujące liczby pierwsze

18

Zadanie

Napisz program lub funkcję, która po przekazaniu danych numerycznych xdrukuje lub zwraca liczby pierwsze poniżej pierwiastka kwadratowego z x1 , które nie są czynnikami x.

Przykłady

Niech f(x)będzie funkcją o nazwie:

>>> f(4)
[]

>>> f(5)
[2]

>>> f(20)
[3]

>>> f(60)
[7]

>>> f(100)
[3, 7]

>>> f(10000)
[3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Zasady bonusów

  • Możesz użyć dowolnego wbudowanego języka.
  • Twój program musi obsługiwać xwejście tak wysokie, jak górna granica zdefiniowana przez Twój język.

1 Używanie pierwiastka kwadratowego, ponieważ tylko liczby pierwsze poniżej pierwiastka kwadratowego mogą być faktycznie uwzględnione w czynnikach x. Bez tego ograniczenia większe liczby miałyby dużo nadmiaru wydrukowanych liczb.

Addison Crump
źródło
3
„Rzeczywiście tylko liczby pierwsze poniżej pierwiastka kwadratowego mogą być zaangażowane w czynniki x” nie jest prawdą: liczba może mieć jeden czynnik pierwszy większy niż pierwiastek kwadratowy. Rzeczywiście, pierwsze dwa przykłady (5 i 20) mają tę właściwość, podobnie jak wszystkie liczby pierwsze, dwa razy wszystkie liczby nieparzyste, ...
Greg Martin
1
@GregMartin Tak, mogą - ale nie można ich znaleźć w pierwszej połowie czynników. Sensowne jest, aby nie uwzględniać 7 w brakujących liczbach pierwszych 48, ponieważ 7 ^ 2 jest większe niż 48. (moje rozumowanie tam leży)
Addison Crump

Odpowiedzi:

8

Galaretka, 6 bajtów na stronie kodowej Jelly

½ÆRḟÆf

Wypróbuj online!

Wyjaśnienie:

½ÆRḟÆf
 ÆR    All primes less than or equal to
½      the square root of the input
   ḟ   but with the following removed:
    Æf All prime factors of {the input, by default}

źródło
5
Jelly odpowiedzi często po prostu dosłownie opisują wyzwanie: P
ETHproductions
6

MATL , 10 9 bajtów

X^ZqGYfX-

Wypróbuj online!

Wyjaśnienie

X^    % Implicit input. Square root
Zq    % Array if primes up to that
G     % Push input again
Yf    % Array of prime factors
X-    % Set difference. Implicit display
Luis Mendo
źródło
5

MATLAB, 57 54 bajtów

function h(p);a=primes(p^.5);a(~ismember(a,factor(p)))

Całkiem proste, pobiera tablicę liczb pierwszych do sqrt (p), a następnie usuwa te, które są również czynnikami p. Domyślnie drukuje wyjście ostatniego wiersza, ponieważ średnik jest pominięty.

MattWH
źródło
1
Nigdy nie próbowałem MATLAB, ale zgodnie z tym, co o nim czytałem, sqrt (p) można zapisać jako p ^ 0,5, a może p ^ .5, chociaż nie jestem pewien co do drugiej sugestii
t-clausen.dk
Ładny! :) Wysłałem oświadczenie Octave przy użyciu tego samego podejścia.
Stewie Griffin,
4

Pyth, 10 bajtów

fP_T-S@Q2P

Program, który pobiera liczbę i drukuje listę.

Zestaw testowy

Jak to działa

fP_T-S@Q2P   Program. Input: Q
fP_T-S@Q2PQ  Implicit input fill
f            Filter
     S@Q2    the 1-indexed range up to floor(sqrt(Q))
    -    PQ  with the prime factors of Q removed
 P_T         by primality
             Implicitly print
TheBikingViking
źródło
4

05AB1E , 8 bajtów

tLDpϹfK

Wypróbuj online!

Wyjaśnienie

tL        # range [1 ... sqrt(input)]
  DpÏ     # keep only primes
     ¹fK  # remove factors of input
Emigna
źródło
3

PHP, 76 bajtów

for($n=1;++$n*$n<$x=$argv[1];){for($i=$n;$n%--$i;);if($i<2&&$x%$n)echo$n,_;}

używa mojego rozwiązania is_prime w golfa za $ n> 1

pobiera dane wejściowe z argumentu wiersza poleceń. Uruchom z -r.

Tytus
źródło
2

Mathematica, 46 bajtów

Select[Prime@Range@PrimePi@Sqrt[a=#],!#∣a&]&

Funkcja anonimowa. Pobiera liczbę jako dane wejściowe i zwraca listę liczb jako dane wyjściowe. Znak Unicode to U + 2223 DIVIDES dla \[Divides].

LegionMammal978
źródło
2

Rubinowy, 55 bajtów

require'prime'
->x{Prime.to_a(x**0.5).select{|n|x%n>0}}

Raczej leniwa odpowiedź przy użyciu wbudowanego głównego modułu wyliczającego.

JayDepp
źródło
2

Cud , 14 bajtów

@(_> > ^#0.5)P

Stosowanie:

(@(_> > ^#0.5)P)10

Pobiera elementy z nieskończonej listy liczb pierwszych, gdy element jest mniejszy niż pierwiastek kwadratowy argumentu.

Mama Fun Roll
źródło
2

Pyke, 10 bajtów

,BS#_P)QP-

Wypróbuj tutaj!

,B         -    int(sqrt(input))
  S        -   range(1, ^+1)
   #_P)    -  filter(^, is_prime)
         - - ^.remove(V)
       QP  -  factors(input)
niebieski
źródło
2

PowerShell v2 +, 71 bajtów

param($n)1..[math]::Sqrt($n)|?{$n%$_-and'1'*$_-match'^(?!(..+)\1+$)..'}

Iteracyjne rozwiązanie. Pobiera dane wejściowe $ni tworzy zakres od 1do Sqrt($n)(zwróć uwagę, że operator zakresu domyślnie rzuci górny koniec na [int]domyślnie wykonujący Zaokrąglanie bankiera). Następnie używa |?{...}( Where-Objectoperator, który działa jak filtr), aby wyciągnąć te liczby, które $n%$_są niezerowe (tj. Każda pozostała część modulo oznacza, że ​​nie jest to czynnik, a każda niezerowa jest prawdziwa)-and pierwsza próba zwykle regex jest $true. Pozostają one w przygotowaniu, a dane wyjściowe są niejawne.

Przykłady

(z dodatkowym formatowaniem, aby poprawić wyniki)

PS C:\Tools\Scripts\golfing> 5,20,60,100,10000|%{"f($_)";(.\print-the-missing-primes.ps1 $_)-join', ';""}
f(5)
2

f(20)
3

f(60)
7

f(100)
3, 7

f(10000)
3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Uwaga: Nie powiedzie się to we wcześniejszych wersjach, jeśli dane wejściowe są większe niż około 2500000000, ponieważ ..operator zakresu może obsłużyć maksymalnie 50 000 elementów. Ponieważ jednak jest ona większa niż [int]maksymalna wartość domyślnego typu danych 2147483647, przypuszczam, że jest OK. Na moim komputerze PSv4 Win8.1 mogę jednak przejść wyżej, ale nie mogę znaleźć dokumentacji wyjaśniającej różnicę.

AdmBorkBork
źródło
2

JavaScript (ES6), 79 76 bajtów

f=(q,n=2,x=n)=>n*n<q?[...--x<2&&q%n?[n]:[],...x>1&&n%x?f(q,n,x):f(q,n+1)]:[]

Na podstawie mojej funkcji testu pierwotności rekurencyjnej . Wydaje mi się, że powinno być kilka sposobów, aby to uprościć, ale nie wiem, jak ...

Testowy fragment kodu

f=(q,n=2,x=n)=>n*n<q?[...--x<2&&q%n?[n]:[],...x>1&&n%x?f(q,n,x):f(q,n+1)]:[]
<input type="number" step=1 min=4 value=4 oninput="O.innerHTML='['+f(this.value)+']'"><br>
<pre id=O>[]</pre>

ETHprodukcje
źródło
2

Oktawa, 44 bajty

Ta odpowiedź jest zainspirowana odpowiedzią MattWH MATLAB , ale grałem w nią w golfa, używając funkcji specyficznych dla Octave.

@(x)(y=primes(x^.5))(~ismember(y,factor(x)))

Jest to anonimowa funkcja, która pobiera dane wejściowe x. Oktawa ma wbudowane przypisywanie i indeksowanie zmiennych, co pozwala ynajpierw zostać utworzone w funkcji (niemożliwe w MATLAB), a następnie użyte jako część maski logicznej utworzonej przez ismember(ponownie, nie jest to możliwe w MATLAB).

Stewie Griffin
źródło
Bardzo ładnie, będzie musiał zajrzeć do Octave. Te cechy byłyby pomocne w golfie!
MattWH,
1

Perl 6 , 37 bajtów

{grep {$^a.is-prime&$_%$a},2.. .sqrt}

Rozszerzony:

{   # bare block lambda with implicit parameter 「$_」

  grep
  {
    $^a.is-prime  # check if it is prime
    &             # and junction
    $_ % $a       # check if the input is not evenly divisible by it
  },
  2.. .sqrt          # Range of values up-to and including squareroot
}
Brad Gilbert b2gills
źródło
1

TSQL, 130 bajtów

DECLARE @v int=10000

,@ INT=2SELECT 2p INTO #
g:INSERT # SELECT @ FROM # HAVING isnull(min(@%p),1)>0SET @+=1IF @*@<@v GOTO g
SELECT*FROM # WHERE @v%p>0

Wykona się to tylko raz, następnie musisz upuścić tabelę tymczasową, aby wykonać ponownie w tym samym edytorze

DROP TABLE #

Stworzyłem wersję do przetestowania, jest ona nieco dłuższa, ponieważ uprawnienia online do tworzenia tabel są niedostępne. Z tego samego powodu nie potrzebuje on tabeli zrzutu.

Wypróbuj online

t-clausen.dk
źródło
1

R 58 58 bajtów

for(i in 2:sqrt(x<-scan()))if(x%%i&numbers::isPrime(i))print(i)

Zapętla wszystkie wartości od 2 do sqrt(x)i sprawdza, czy są one pierwszorzędne w numberspakiecie. x%%ioblicza, x mod iktóra jest 0 -> Falsejeśli ijest dzielnikiem xi >0 -> Truejeślii nie jest.

+5 bajtów, ponieważ numbers::Primes(n)funkcja nie pozwala na ułamki dziesiętne, podczas gdy 2:sqrt(x)działa, dodano do ifinstrukcji sprawdzanie liczby pierwszej.

JAD
źródło
1

Haskell, 55 54 bajtów

f x=[y|y<-[2..x],y*y<x,[z|z<-[1..y],gcd(z*x)y>1]==[y]]

Przeważnie proste zestawienia zagnieżdżonych list. GCD wykonuje dwie role, sprawdzając, czy liczby poniżej y są współczynnikami y, a także sprawdzając, czy y jest współczynnikiem x.

Rozłożył się trochę:

f x = [ y|y<-[2..x],     y*y<x,     [z|z<-[1..y], gcd (z*x) y > 1] == [y] ]
James Hollis
źródło
Zapisz bajt za pomocą gcd(z*x)y>1.
Zgarb,
Na pierwszym miejscu umieściłem również kontrolę y * y <x, aby była nieco szybsza.
James Hollis,
0

Retina , 69 66 bajtów

.+
$*
(11\1|^1)+
$#1$*1:$&
M!&`(?!(11+)\1+:)(1+):(?!\2+$)
M%`1
^0

Drukuje liczby pierwsze na osobnych liniach, od największej do najmniejszej.

Wypróbuj online!(Zajmuje około 10 sekund z powodu dwóch ostatnich przypadków testowych. Nagłówek i stopka włączają pakiet testowy oddzielny od linii i konwertują dane wyjściowe do separacji przecinków dla zapewnienia czytelności).

Wyjaśnienie

.+
$*

Przekształć dane wejściowe w jednoargumentowe.

(11\1|^1)+
$#1$*1:$&

To poprzedza pierwiastek kwadratowy z danych wejściowych, oddzielony przez :. Pierwiastek kwadratowy jest obliczany na podstawie faktu, że kwadrat njest również sumą pierwszych nnieparzystych liczb całkowitych. Możemy dopasować kolejne nieparzyste liczby całkowite z referencją do przodu(11\1|^1) . W procesie grupa zostanie użyta dokładnie nrazy, gdzien jest największą liczbą, której kwadrat pasuje do wejścia.

Wstawiamy jednoargumentową reprezentację tego numeru $#1$*1, następnie dwukropek i sam mecz.

M!&`(?!(11+)\1+:)(1+):(?!\2+$)

To pasuje do wszystkich brakujących liczb pierwszych pasujących do pierwiastka kwadratowego. Wykrywanie liczb pierwszych opiera się na standardowym wyrażeniu regularnym sprawdzania liczb pierwszych , a następnie upewniamy się, że liczba pierwsza, którą właśnie przechwyciliśmy, nie dzieli danych wejściowych z drugim spojrzeniem w przód. Korzystając z &opcji, otrzymujemy nakładające się mecze, aby zapewnić, że otrzymamy wszystkie liczby pierwsze.

M%`1

Konwertuje każdą linię (tj. Każdą brakującą liczbę pierwszą) z powrotem na dziesiętną, dopasowując liczbę 1s. Jedynym problemem jest to, że wstawia zero, jeśli w ogóle nie znaleziono brakujących liczb pierwszych.

^0

Więc ten etap usuwa to zero, jeśli zostało dodane.

Martin Ender
źródło