Ist es eine schwache Primzahl?

26

Eine Primzahl ist schwach, wenn die nächste andere Primzahl kleiner ist. Bei Gleichstand ist der Prime nicht schwach.

Zum Beispiel ist 73 eine schwache Primzahl, weil 71 eine Primzahl ist, 75 aber zusammengesetzt ist.

Aufgabe

Schreiben Sie einen Computercode, der bei einer Primzahl größer als 2 als Eingabe bestimmt, ob es sich um eine schwache Primzahl handelt. Dies ist ein Standardentscheidungsproblem daher sollten Sie für jeden der beiden Fälle (z . B. weakund not weak) zwei eindeutige Werte ausgeben .

Dies ist daher gelten die Standardregeln für das Tag.

OEIS

Hier sind die ersten 47 schwachen Primzahlen:

3, 7, 13, 19, 23, 31, 43, 47, 61, 73, 83, 89, 103, 109, 113, 131, 139, 151, 167, 181, 193, 199, 229, 233, 241, 271, 283, 293, 313, 317, 337, 349, 353, 359, 383, 389, 401, 409, 421, 433, 443, 449, 463, 467, 491, 503, 509, 523, 547, 571, 577, 601, 619, 643, 647

Hier ist der OEIS für schwache Primzahlen (sollte zurückkehren weak) OEIS A051635

Hier ist der OEIS für ausgeglichene Primzahlen (sollte zurückkehren not weak) OEIS A006562

Hier ist der OEIS für starke Primzahlen (sollte zurückkehren not weak) OEIS A051634

Weizen-Assistent
quelle
not weakoder strong?
CalculatorFeline
7
@ CalculatorFeline nicht schwach ist anders als stark
Wheat Wizard

Antworten:

26

Gelee , 7 Bytes

Æn+Æp>Ḥ

Probieren Sie es online!

Erläuterung

           See if
Æn         the next prime
  +Æp      plus the previous prime
     >Ḥ    is greater than 2n

Als Bonus wechseln Sie >zu =oder <suchen nach ausgeglichenen bzw. starken Primzahlen.

PurkkaKoodari
quelle
Das sollte sein >, nein?
Dennis
2
Oh wow, das ist klug ...
ETHproductions
Ich habe auch nur so herausgearbeitet. Gute Arbeit!
Jonathan Allan
Das ist so schlau ...
Erik der Outgolfer
12

Mathematica, 24 Bytes

n=NextPrime;2#+n@-#<n@#&

Die NextPrimeeingebaute Funktion kann (ab?) Verwendet werden, um die vorherige Primzahl durch Eingabe eines negativen Arguments zu berechnen.

Martin Ender
quelle
6

Gelee , 9 Bytes

ḤÆRạÞ⁸ḊḢ>

Returns 1für schwach und 0für nicht schwach oder ausgeglichen (kehrt 1für einen Eingang 2)

Probieren Sie es online!

Wie?

ḤÆRạÞ⁸ḊḢ> - Link: prime number > 2, p
Ḥ         - double -> 2*p
 ÆR       - yield primes between 2 and 2*p inclusive
     ⁸    - chain's left argument, p
    Þ     - sort by:
   ạ      -   absolute difference (i.e. distance from p)
      Ḋ   - dequeue (removes p from the list, since it has distance zero)
       Ḣ  - head (gives us the nearest, if two the smallest of the two)
        > - greater than p?
Jonathan Allan
quelle
Ninja'd mir mit einer komplexen Lösung ...
Erik der Outgolfer
Es war ein Sekundenbruchteil!
Jonathan Allan
1
Nein, war es nicht, es war 9 volle Sekunden iirc. Nein, 10 Sekunden.
Erik der Outgolfer
So war es (in der Zeit gesehen), als ich es hier einreichte :)
Jonathan Allan
1
Nun, es sieht so aus, als hätten Sie nur schneller als ich Golf gespielt ... (es ist eine ziemliche Reise, zuerst von IIṠ⁼1nach II>0nach zu fahren I<\) ... Ihre ist jedoch ganz anders. Anscheinend denkst du anders als ich ... EDIT: Pietu1998 ist zurückgekehrt!
Erik der Outgolfer
5

PHP , 69 Bytes

druckt eine für schwache Primzahl und nichts für nicht schwache Primzahl

for(;!$t;$t=$d<2)for($n=$d=$argn+$i=-$i+$w^=1;$n%--$d;);echo$n<$argn;

Probieren Sie es online!

Jörg Hülsermann
quelle
3

Oktave, 93 84 Bytes

Danke an @LuisMendo und @ rahnema1 für das Speichern von Bytes!

function r=f(x);i=j=x;do--i;until(i<1|isprime(i));do++j;until(isprime(j));r=x-i<j-x;

Probieren Sie es online!

Steadybox
quelle
Kannst du nicht i-=1etc benutzen ? Auch endwird in der Funktion nicht benötigt; Sie können es in die Fußzeile verschieben
Luis Mendo
3

Maxima, 42 Bytes

f(n):=is(n-prev_prime(n)<next_prime(n)-n);

Probieren Sie es online!

rahnema1
quelle
3

MATL , 13 Bytes

qZq0)G_Yq+GE>

Andernfalls erfolgt die Ausgabe 1schwach 0.

Probieren Sie es online!

Erläuterung

q      % Implicit input, Subtract 1
Zq     % Vector of primes up to that
0)     % Get last one
G      % Push input again
_Yq    % Next prime
+      % Add
G      % Push input
E      % Multiply by 2
>      % Greater than? Implicit display
Luis Mendo
quelle
3

GNU APL 1.2, 78 Bytes

∇f N
X←(R←(~R∊R∘.×R)/R←1↓⍳N×2)⍳N
(|R[X-1]-N)<|R[X+1]-N
∇

∇f N deklariert eine Funktion, die ein Argument annimmt.

(~R∊R∘.×R)/R←1↓⍳N×2gibt eine Liste aller Primzahlen von 2 bis zum doppelten Argument an. Ich gehe davon aus, dass die nächste Primzahl weniger als das Doppelte des Originals ist. Wenn dies nicht wahr ist, N*2gibt es N im Quadrat und nimmt die gleiche Anzahl von Bytes (hoffentlich ist das groß genug, um die nächste Primzahl zu überschreiten). (Siehe die Erklärung von Wikipedia für die Funktionsweise der Prim-Finding)

X←(R←(...))⍳NWeist diese Liste dem Vektor zu R(überschreibt den vorherigen Inhalt), findet den Index der ursprünglichen Primzahl Nin dieser Liste und weist diesen Index dann zu X.

|R[X-1]-Nberechnet die Differenz zwischen der vorherigen Primzahl (da diese Rdie Primzahlen enthält, das X-1dritte Element die vorherige Primzahl ist N) und Nnimmt dann den absoluten Wert an (APL arbeitet von rechts nach links).

|R[X+1]-N tut dasselbe, aber für die nächste Primzahl.

(|R[X-1]-N)<|R[X+1]-NGibt 1 aus, wenn die vorherige Primzahl näher am Original liegt als die nächste Primzahl, andernfalls 0. Klammern werden für den Vorrang benötigt.

beendet die Funktion.

Arc676
quelle
2

Pyth, 15 Bytes

>-fP_ThQfPT_tQy

Probieren Sie es hier aus.

Verwendet den Pietu1998-Algorithmus.

Erik der Outgolfer
quelle
2

Perl 6 , 41 Bytes

{[>] map ->\n{$_+n,*+n...&is-prime},1,-1}

Probieren Sie es online!

$_ist das Argument für die Funktion. Die Zuordnungsfunktion -> \n { $_ + n, * + n ... &is-prime }nimmt eine Zahl nund gibt eine Folge von Zahlen zurück $_ + n, $_ + 2*n, ..., die endet, wenn sie eine Primzahl erreicht. Mappen Sie diese Funktion auf die beiden Zahlen 1und -1erzeugen Sie eine Folge von zwei Folgen. die erste beginnt $_ + 1und endet mit der ersten Primzahl größer als $_und die zweite beginnt $_ - 1und endet mit der ersten Primzahl kleiner als $_. [>]Reduziert diese Liste mit zwei Elementen mit dem Größer-als-Operator und gibt true zurück, wenn die erste Sequenz größer (dh länger) als die zweite ist.

Sean
quelle
2

Python 2.7 - 120 Bytes

from math import*
i=lambda x:factorial(x-1)%x==x-1
def f(n,c):return 1 if i(n-c)>i(n+c) else 0 if i(n+c)>0 else f(n,c+1)

Da Python keine eingebaute Prim-Funktion hat, können wir den Satz von Wilson verwenden, um einen schönen kurzen Prim-Checker zu erhalten. Wilsons Satz besagt, dass eine Zahl genau dann Primzahl ist, wenn (n-1)! ist kongruent zu -1 mod (n). Daher gibt die Funktion i 1 zurück, wenn die Zahl eine Primzahl ist, und 0, wenn dies nicht der Fall ist. Anschließend bestimmt die f-Funktion, ob die nächste Primzahl von dieser Zahl zuerst auftritt, wenn sie nach unten anstatt nach oben erhöht wird. Wenn keine der inkrementierten Zahlen eine Primzahl ist, wird sie nur erneut rekursiv aufgerufen.

Einige Beispiel-E / A

f(3,1)
1
f(15,1)
0
Joe Habel
quelle
2

Python 2 , 122 108 103 94 92 Bytes

def a(n):
 r=[2];x=2
 while r[-1]<=n:x+=1;r+=[x]*all(x%i for i in r)
 return sum(r[-3:])>3*n

Probieren Sie es online!

Verwendet Pietus Idee ... und spart dann 28 Bytes, indem kürzere Iteratoren der Primliste verwendet werden. dann 2 weitere durch den Austausch -3*n>0mit >3*n(d'oh!)

Chas Brown
quelle
2

Regex (die meisten Geschmacksrichtungen), 47 Bytes

^(?=(x*)(?!(x+)(\2\2x)+$)\1)x+(?!(xx+)\4+$)\1\1

Probieren Sie es online!

Nimmt unäre Eingaben auf. Gibt eine Übereinstimmung für schwache Primzahlen aus, keine Übereinstimmung für nicht schwache Primzahlen. Funktioniert in ECMAScript, Perl, PCRE, Python, Ruby.

Erläuterung:

Sei N die Eingabe, A die nächstliegende Primzahl <N und B die nächstliegende Primzahl> N. Die Hauptschwierigkeit eines Regex-Ansatzes für diese Herausforderung besteht darin, dass wir keine Zahlen darstellen können, die größer sind als die Eingabe, wie B. Stattdessen können wir finde das kleinste b so, dass 2b + 1 Primzahl ist und 2b + 1> N, was 2b + 1 = B sicherstellt.

(?=
  (x*)              # \1 = N - b, tail = b
  (?!(x+)(\2\2x)+$) # Assert 2b + 1 is prime
  \1                # Assert b ≥ \1 (and thus 2b + 1 > N)
)

Beachten Sie dann, dass wir A eigentlich nicht finden müssen. Solange eine Primzahl <N näher an N als B liegt, ist N eine schwache Primzahl.

x+                  # tail iterates over integers < N
(?!(xx+)\4+$)       # assert tail is prime
\1\1                # assert tail ≥ 2 * \1 (and thus tail + B > 2N)
Grimmig
quelle
1

JavaScript ES6, 162 154 Bytes

8 Bytes sparen, basierend auf Jörg Hülsermanns Trick "Nichts in einem Fall drucken". Keine Notwendigkeit ?"Y":"N"danachone<two

var isWeak=

a=>{p=[2];i=0;f=d=>{j=p[i];l:while(j++){for(x=0;p[x]*p[x]<=j;x++){if(j%p[x]==0){continue l}}return p[++i]=j}};while(p[i]<a+1){f()};return a*2<p[i]+p[i-2]}

[43,//true
53,//false
7901,//false
7907,//true
1299853,//true
1299869//false
].forEach(n=>{console.log(n,isWeak(n))})

Евгений Новиков
quelle
0

Python 3 , 149 Bytes

f=lambda n,k=1,P=1:n*[0]and P%k*[k]+f(n-P%k,k+1,P*k*k)
def a(n):p=f(n);return p.index(n)in filter(lambda i:p[i]-p[i-1]<p[i+1]-p[i],range(1,len(p)-1))

Probieren Sie es online!

Ich verwende eine Funktion zur Erzeugung von Primzahlen (oberste Zeile), die dieser alten Stapelaustauschantwort entnommen ist .

Wrymug
quelle
0

JavaScript, 98 Bytes

let test = _=>(o.innerHTML=f(+prime.value))
let f= 

n=>{P=n=>{for(i=n,p=1;--i>1;)p=p&&n%i};a=b=n;for(p=0;!p;P(--a));for(p=0;!p;P(++b));return n-a<b-n}
Enter Prime: <input id="prime">
<button type="button" onclick="test()">test if weak</button>
<pre id="o"></pre>

Weniger Golphed

n=>{
   P=  // is a Prime greater than 1, result in p
       n=>{
           for(i=n,p=1;--i>1;)
               p=p&&n%i
       };

   a=b=n; // initialize lower and upper primes to n
   for(p=0;!p;P(--a)); // find lower,
   for(p=0;!p;P(++b)); // find upper,
   return n-a<b-n // is weak result
}

Beachten Sie, dass der Testcode nicht überprüft, ob die Eingabe "prime" tatsächlich eine Primzahl ist.

traktor53
quelle
0

Braingasmus , 23 22 Bytes

Drucke 1für schwache Primzahlen und 0für nicht schwache.

;>0$+L[->+>2[>q[#:Q]]]

Exemplarische Vorgehensweise:

;                       Read a number to cell 0
 >0$+                   Go to cell 1 and copy the value of cell 0
     L                  Make the tape wrap around after cell 1
      [              ]  Loop:
       ->+>               Decrease cell 1 and increase cell 0
           2[       ]     Twice do:
             >              Go to the other cell
              q[   ]        If it's prime:
                #:Q         Print the current cell number and quit
daniero
quelle
0

Julia 0,6, 64 Bytes

g(x,i)=0∉x%(2:x-1)?1:1+g(x+i,i);x->g(x,1)&(g(x-1,-1)<g(x+1,1))
Tanj
quelle
0

Python 2 , 81 Bytes

n=input()
a=b=c=i=2;p=1
while b<n:
 p*=i;i+=1
 if p*p%i:a,b,c=b,c,i
print a+c>2*b

Probieren Sie es online!

Verwendet den Satz von Wilson für den Primalitätstest.

Meilen
quelle