Zadanie

Napisz program lub funkcję, która po przekazaniu danych numerycznych xdrukuje lub zwraca liczby pierwsze poniżej pierwiastka kwadratowego z x¹ , 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.

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

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}

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

Python 3 , 67 62 bajtów

f=lambda n,k=1,m=1:k*k<n and(m%k*n%k>0)*[k]+f(n,k+1,m*k*k)or[]

Wypróbuj online!

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.

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

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

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.

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

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.

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.

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)

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

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>

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

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
}

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

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.

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

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.