Ist es ein Mersenne Prime?

35

Eine Zahl ist eine Mersenne-Primzahl, wenn sie beide Primzahlen ist und in der Form 2 n -1 geschrieben werden kann , wobei n eine positive ganze Zahl ist.

Ihre Aufgabe ist es, bei einer positiven ganzen Zahl zu bestimmen, ob es sich um eine Mersenne-Primzahl handelt oder nicht. Sie können entweder eine Funktion übergeben, die einen Wahrheits- / Falschwert zurückgibt, oder ein vollständiges Programm, das E / A ausführt.

Regeln:

  • Da dies , sollten Sie versuchen, dies in möglichst kurzer Anzahl von Bytes zu tun . Builtins sind erlaubt.
  • Es gelten Standard-Golflöcher - Sie können die Mersenne-Primzahlen nicht aus externen Dateien lesen oder in Ihr Programm einprogrammieren.
  • Ihr Programm sollte für Werte innerhalb der Standard-Integer-Größe Ihrer Sprache funktionieren.

Testfälle

Als Referenz wird eine Liste von (bekannten) Mersenne - Primzahlen finden sich hier . Einige handliche Testfälle sind:

2  -> False
1  -> False 
20 -> False
51 -> False
63 -> False

3    -> True
31   -> True
8191 -> True

Frohe Weihnachten an alle! Haben Sie einen schönen Urlaub, was auch immer Sie feiern :)

FlipTack
quelle
2
Wenn ich könnte, würde ich dies als ein Betrug der isprime- Herausforderung abstimmen , da es nichts wirklich Neues hinzufügt.
Fehler
9
@flawr Sie sind sich sehr ähnlich - aber für diese Herausforderung gibt es weniger wahrscheinlich eine eingebaute und es gibt viele interessante Ansätze, um zu bestimmen, ob eine Zahl als2^n-1
FlipTack
1
Ich glaube, die Definition einer Mersenne-Zahl verlangt auch, dass n Primzahl ist (eine Bedingung, die ebenfalls als notwendig, aber nicht ausreichend erwiesen wurde, damit (2 ^ n) -1 Primzahl ist.)
SuperJedi224
4
@ SuperJedi224 nist immer prim, aber da sich nichts ändert, ist die Definition immer noch korrekt.
FlipTack
2
@TheBitByte Ja - wenn Sie einen wahrscheinlichkeitsbasierten Algorithmus implementieren, der nicht 100% der Zeit funktioniert, können Sie ihn trotzdem posten, aber er würde nicht konkurrieren :)
FlipTack

Antworten:

19

Gelee , 5 Bytes

&‘<ÆP

Probieren Sie es online!

Wie es funktioniert

&‘<ÆP  Main link. Argument: x

 ‘     Yield x+1.
&      Take the bitwise AND of x and x+1.
       This yields 0 iff x is a Mersenne number, i.e., iff x+1 is a power of 2.
   ÆP  Yield 1 if x is a prime, 0 if not.
  <    Compare the results to both sides,
       This yields 1 iff x is both a Mersenne number and a prime.
Dennis
quelle
Gleiches Problem wie Adnans Antwort. Siehe mothereff.in/byte-counter
Kelly Lowder
8
@ KellyLowder Dieser Byte-Zähler verwendet UTF-8. Sowohl Jelly als auch 05AB1E verwenden Einzelbyte-Zeichensätze.
Dennis
24

05AB1E , 5 Bytes

Eine positive Zahl in der Form 2 n - 1 in binärer Form besteht nur aus Einsen .

Code:

b`¹pP

Erläuterung:

b`      # Push each digit of the binary representation of the number onto the stack
  ¹p    # Check if the input is prime
    P   # Take the product of all these digits

Verwendet die CP-1252- Codierung. Probieren Sie es online! oder Überprüfen Sie alle Testfälle .

Adnan
quelle
5
Ich habe mich gefragt, wie lange es
gedauert hat,
¹ braucht 2 Bytes, das ist also 6.
Kelly Lowder
5
@ KellyLowder In UTF-8, ja. 05AB1E verwendet jedoch die CP-1252-Codierung anstelle der UTF-8-Codierung.
Adnan
10

Python , 45 Bytes

lambda n:-~n&n<all(n%i for i in range(2,n))<n

Probieren Sie es online!

Wie es funktioniert

Die drei Begriffe des verketteten Vergleichs

-~n&n<all(n%i for i in range(2,n))<n

Mach Folgendes:

  • -~n&nberechnet das bitweise UND von n + 1 und n . Da n nur aus 1 Bit besteht, wenn es eine Mersenne-Zahl ist, gibt das bitweise UND 0 zurück, wenn (und nur wenn) dies der Fall ist.

  • all(n%i for i in range(2,n))Gibt nur dann True zurück, wenn n mod i für alle Werte von i in [2,…, n - 1] ungleich Null ist , dh nur dann, wenn n außer 1 und n keine positiven Teiler hat .

    Mit anderen Worten, alle Erträge wahr , wenn und nur wenn n eine zusammengesetzte Zahl ist, dh n ist entweder 1 oder eine Primzahl.

  • n ist selbsterklärend.

Der verkettete Vergleich gibt nur dann True zurück, wenn die einzelnen Vergleiche dasselbe tun.

  • Da alle gibt entweder Wahr / 1 oder Falsch / 0 , -~n&n<all(n%i for i in range(2,n))kann nur zurück Wahr , wenn -~n&nAusbeuten 0 ( das heißt, wenn n eine Mersenne Zahl) und alle Rücksendungen Wahr (dh wenn n entweder 1 oder eine Primzahl).

  • Der Vergleich all(n%i for i in range(2,n))<ngilt immer dann, wenn n> 1 ist. Da jedoch bei n = 1 alle den Wert True zurückgeben , gilt dies in diesem Fall nicht.

Dennis
quelle
1
Wow, das ist unglaublich :)
ABcDexter
8

Brachylog , 7 Bytes

#p+~^h2

Probieren Sie es online!

Ein Brachylog Programm im Grunde eine Folge von Einschränkungen ist , die eine Kette bilden: der erste Eingrenzungs zwischen dem Eingang und einer anonymen unbekannt (nennen sie es ein für die Zwecke dieser Diskussion), ist die zweite Bedingung zwischen diesen anonymen unbekannten und einem zweiten anonymen unbekannt (was wir B nennen ) und so weiter. Als solches bricht das Programm folgendermaßen zusammen:

#p      Input = A, and is prime
+       B = A + 1
~^      B = X to the power Y, C = the list [X, Y]
h       D = the head of list C (= X)
2       D = 2

Alle diese Bedingungen können nur dann gleichzeitig erfüllt werden, wenn B eine Potenz von 2 ist, dh die Eingabe eine Potenz von 2 minus 1 ist und die Eingabe ebenfalls prim ist. (Brachylog verwendet intern einen Constraint-Solver, sodass das Programm nicht so ineffizient ist, wie es in der Auswertungsreihenfolge aussieht. Es ist jedoch klar, dass diese CForm vorliegt, [2, Y]bevor versucht wird, sie Bals Potenzierung zweier Zahlen auszudrücken .)

Interessanterweise #p+~^ fast funktioniert, weil Mersenne-Primzahlen wie nur 2 als Base in nicht-degenerierten Fällen (können Nachweis ), aber a) es nicht für Nicht-Mersenne - Primzahlen B -1 , wie sie ausgedrückt werden kann als B ¹ und b ) Der vorhandene Brachylog-Interpreter scheint durch ein Programm, das so wenig eingeschränkt ist, verwirrt zu sein (er geht in eine unendliche oder zumindest lange Schleife). Es ist also unwahrscheinlich, dass 7 Bytes in Brachylog geschlagen werden.


quelle
Ich bin beeindruckt! Das Endlosschleifenproblem ist auf die Überladung von Prädikaten zurückzuführen. Rückblickend denke ich, ich hätte keine Überladung für Prädikate implementieren sollen. Dies verursacht auch Probleme in Sachen Fundall.
Fatalize
7

Mathematica 26 Bytes

PerfectNumberQ[# (#+1)/2]&

Siehe diesen Beweis

Funktioniert, solange es keine ungeraden perfekten Zahlen gibt und keine bekannt ist.

Kelly Lowder
quelle
Ihre Antwort hat sich also als ungültig erwiesen?
Jonathan Frech
Ich denke nicht, dass Platz notwendig ist.
Jonathan Frech
@JonathanFrech Die Formel n(n+1)/2liefert (gerade) perfekte Zahlen, wenn nes sich um eine Mersenne-Primzahl (Euklid) handelt. Es scheint unbekannt zu sein, ob eine ungerade perfekte Zahl die Form haben kann n(n+1)/2, dh eine dreieckige Zahl. Alle geraden perfekten Zahlen sind dreieckig, wenn dies neine Mersenne-Primzahl (Euler) ist.
Jeppe Stig Nielsen
1
@JeppeStigNielsen Die Frage ist, ob es gültig ist, eine unbekannte Tatsache zu verwenden, um die eigene Lösung zu begründen.
Jonathan Frech
7

Mathematica, 29 26 Bytes

Bearbeiten: 3 Bytes dank Martin Ender gespeichert

PrimeQ@#&&IntegerQ@Log2[#+1]&

PrimeQ@#&&1>BitAnd[#,#+1]&

Ich vermute, dies wäre schneller, da die ersten 42 Exponenten fest codiert sind:

MersennePrimeExponentQ@Log2[#+1]&
Genisis
quelle
6
PrimeQ@#&&1>BitAnd[#,#+1]&
Martin Ender
5

Perl 6 , 29 Bytes

{.base(2)~~/^1*$/&&.is-prime}

Versuch es

Erweitert:

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

  .base(2)    # is its binary representation ( implicit method call on 「$_」 )
   ~~
  /^ 1* $/    # made entirely of 「1」s

  &&          # and

  .is-prime   # is it prime

}

Da Perl 6 willkürlich große Ints hat, füllt es die Vorderseite nicht .base(2)mit 0s auf.

Brad Gilbert b2gills
quelle
5

Python, 83 82 79 76 73 Bytes

def f(m):
 s,n=(m!=3)*4,m>>2
 while-~m&m<n:s,n=(s*s-2)%m,n>>1
 return s<1

Python 2, 71 Bytes

def f(m):
 s,n=(m!=3)*4,m/4
 while-~m&m<n:s,n=(s*s-2)%m,n/2
 return s<1

Diese Funktion implementiert den Lucas-Lehmer-Primalitätstest. Sie ist zwar nicht so kurz wie einige andere Python-Angebote, kann jedoch sehr viel schneller große Eingaben verarbeiten.


Hier ist ein Testcode, der auf Python 2 oder Python 3 ausgeführt wird.

from __future__ import print_function

def primes(n):
    """ Return a list of primes < n """
    # From http://stackoverflow.com/a/3035188/4014959
    sieve = [True] * (n//2)
    for i in range(3, int(n**0.5) + 1, 2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n - i*i - 1) // (2*i) + 1)
    return [2] + [2*i + 1 for i in range(1, n//2) if sieve[i]]

def lucas_lehmer_old(p):
    m = (1 << p) - 1
    s = 4
    for i in range(p - 2):
        s = (s * s - 2) % m
    return s == 0 and m or 0

# much faster
def lucas_lehmer(p):
    m = (1 << p) - 1
    s = 4
    for i in range(p - 2):
        s = s * s - 2
        while s > m:
            s = (s & m) + (s >> p)
    return s == 0 or s == m and m or 0

def f(m):
 s,n=(m!=3)*4,m>>2
 while-~m&m<n:s,n=(s*s-2)%m,n>>1
 return s<1

# Make a list of some Mersenne primes
a = [3]
for p in primes(608):
    m = lucas_lehmer(p)
    if m:
        print(p, m)
        a.append(m)
print()

# Test that `f` works on all the numbers in `a`
print(all(map(f, a))) 

# Test `f` on numbers that may not be Mersenne primes
for i in range(1, 525000):
    u = f(i)
    v = i in a
    if u or v:
        print(i, u, v)
    if u != v:
        print('Error:', i, u, v)

Ausgabe

3 7
5 31
7 127
13 8191
17 131071
19 524287
31 2147483647
61 2305843009213693951
89 618970019642690137449562111
107 162259276829213363391578010288127
127 170141183460469231731687303715884105727
521 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
607 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127

True
3 True True
7 True True
31 True True
127 True True
8191 True True
131071 True True
524287 True True

FWIW, hier ist eine etwas effizientere Version f, die nicht min jeder Schleife erneut getestet wird:

def f(m):
 s,n=m!=3and 4,m>>2
 if-~m&m<1:
  while n:
   s=(s*s-2)%m
   n>>=1
 return s<1
PM 2Ring
quelle
Sie können die while-Schleife alle in einer Zeile schreiben (kein Zeilenumbruch und kein Einzug
erforderlich
@FlipTack D'oh! Vielen Dank! Ich weiß wirklich nicht, warum ich das verpasst habe ... Und ich habe gerade bemerkt, dass ich durch die Rückkehr zu Python 2 ein paar Bytes mehr abschneiden kann.
PM 2Ring
4

R 41 40 Bytes

matlab::isprime(x<-scan())&!log2(x+1)%%1

Seltsamer in R die builtin mersennenimmt nals Argument nicht2^n-1 .

Dieser entnimmt xSTDIN, prüft anhand des matlabPakets , ob es sich um eine Primzahl handelt und prüft, ob das 2-log vonx+1 eine ganze Zahl ist, indem mod 1 genommen und auf 'nicht Null' überprüft wird.

Wenn Sie die mersenneeingebaute Funktion verwenden, ist sie zwar etwas kürzer, fühlt sich aber wie Schummeln an:

numbers::mersenne(log2(scan()+1))

1 Byte dank @Billywob gespeichert

JAD
quelle
Gepostet eine ähnliche Antwort, aber ich habe es jetzt gelöscht. Darf ich vorschlagen matlab::isprime, ein Byte zu speichern. Auch müssen Sie <-für In-Function-Zuweisung verwenden.
Billywob
@billywob Habe gerade mitbekommen, dass matlab :: isprime 1 Byte kürzer war. (hat einen 1-Sekunden-Peak bei Ihrer Lösung).
JAD
Sie können log2(x+1)stattdessen auch verwenden log(x+1,2).
Billywob
2

Pyke, 10 Bytes

_PQb2+}\1q

Probieren Sie es hier aus!

_P         -    is_prime(input)
     +     -   ^ + V
  Qb2      -    base_2(input)
      }    -  uniquify(^)
       \1q - ^ == "1"
Blau
quelle
2

Eigentlich 9 Bytes

;├╔'1=@p*

Probieren Sie es online!

Erläuterung:

Da jede Zahl der Form 2 n -1 alle Einsen in ihrer binären Darstellung hat, kann eine Mersenne-Primzahl als Primzahl mit dieser Qualität identifiziert werden.

;├╔'1=@p*
 ├╔'1=     only unique binary digit is 1
        *  and
;     @p   is prime
Mego
quelle
2

Gelee, 5 Bytes

Alternative Herangehensweise an @Dennis 'bestehende 5-Byte-Jelly-Antwort:

B;ÆPP

Probieren Sie es online!

Wie es funktioniert:

B      Returns the binary representation of the input as a list [1, 0, 1, 1, ...]
 ;     And attach to this list 
  ÆP   a 1 if the input is a prime, 0 otherwise
    P  Calculates the product of this list of 1's and 0's

Da eine Mersenne-Primzahl eine 1 weniger als eine Potenz von 2 ist, ist ihre binäre Darstellung ausschließlich 1er. Die Ausgabe hierfür ist 1 für Mersenne-Primzahlen und 0 in allen anderen Fällen.

steenbergh
quelle
2

Ceylon, 66 Bytes

Boolean m(Integer c)=>c>2&&c.and(c+1)<1&&!(2:c-2).any((d)=>c%d<1);

Formatiert (und kommentiert):

// Check whether a (positive integer) number is a mersenne prime number.
//
// Question:  http://codegolf.stackexchange.com/q/104508/2338
// My Answer: http://codegolf.stackexchange.com/a/104805/2338

Boolean m(Integer c) =>
        // check whether c+1 is a power of two
        c.and(c+1)<1 &&
        // the standard primality check by trial division
         !(2 : c-2).any((d) => c%d < 1) &&
        // we need to exclude 1, which is unfortunately
        // matched by both criteria above, but is no prime.
        c>1;

Durch Cheaten (Hardcodierung der Ergebnisse im Bereich von Ceylons Integer) können wir ein Byte kürzer machen (65):

Boolean h(Integer c) =>
        c.and(c+1)<1 && #20000000800a20ac.and(c+1)>0;

(Es sieht so aus, als würde der Syntax-Textmarker Ceylons Hexadezimalzahlen als Kommentaranfang missverstehen.)

Wenn eine anonyme Funktion in Ordnung ist, sind dies 49 Bytes:

[2,3,5,7,13,17,19,31,61].map((p)=>2^p-1).contains
Paŭlo Ebermann
quelle
2

Wolfram Language (Mathematica) , 23 Byte

PrimeQ[BitAnd[#,#+2]#]&

Probieren Sie es online!

1 wird richtig gehandhabt, weil PrimeQ[BitAnd[1,1+2]*1] == PrimeQ@1 == False. Ansonsten BitAnd[#,#+2]#brauchen wir, #um Primzahl zu sein, Primzahl und BitAnd[#,#+2] == 1, was passiert, wenn #es sich um eine Mersenne-Zahl handelt.

Lirtosiast
quelle
Schön gemacht! Als jemand, der Mathematica noch nie benutzt hat, war Ihr TIO-Code zunächst verwirrend. Dann wurde mir klar, dass Sie Ihre Funktion mit der des früheren Rekordhalters von ngenisis vergleichen . Ich denke, es wäre besser, nur die Ausgabe der Funktion zu zeigen und vielleicht einen zweiten Link zu haben, der sie mit den anderen Lösungen vergleicht.
Deadcode
2

ECMAScript-Regex, 42 31 Bytes

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

^
(?!(xx+)\1+$)      # Assert that N is prime or 0 or 1.
(x(x*)(?=\3$))+x$  # Assert that N is a power of 2 minus 1 and is >= 3.
                   # The >=3 part of this prevents the match of 0 and 1.

Probieren Sie es online!

Edit: Bis zu 31 Bytes dank Neil.

Der Grundtest "ist eine Potenz von 2 minus 1" ist ^(x(x*)(?=\2$))*$. Dies funktioniert, indem die Operation "subtrahiere 1, dividiere dann gleichmäßig durch 2" durchlaufen wird, bis dies nicht mehr möglich ist, und dann behauptet wird, dass das Ergebnis Null ist. Dies kann so geändert werden, dass es nur mit Zahlen ≥ 1 übereinstimmt, indem das letzte *in ein a geändert wird +, wodurch die Schleife gezwungen wird, mindestens einmal zu iterieren. Einfügen eines xvor dem letzten$ modifiziert es so, dass es nur mit Zahlen ≥3 übereinstimmt, indem behauptet wird, dass das Endergebnis nach mindestens einer Schleife 1 ist.

Der zugehörige "Ist eine Potenz von 2" -Test ist ^((x+)(?=\2$))*x$. Es gibt auch eine Abkürzung für Matching-Potenzen von 2 minus 2, die von Grimy entdeckt wurde :^((x+)(?=\2$)x)*$ . Alle drei Regexes sind gleich lang.

Alternative 31-Byte-Version von Grimy :

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

Probieren Sie es online!

# Match Mersenne primes in the domain ^x*$
^                   # N = input number
(?!                 # "(?!p|q)" is equivalent to "(?!p)(?!q)"; evaluate the
                    # logical AND of the following negative lookaheads:
    (xx+)\1+$       # Assert that N is prime or 0 or 1
|
    ((xx)+)(\2x)*$  # Assert that N is a power of 2 minus 1; this is based
                    # on "(?!(x(xx)+)\1*$)" which matches powers of 2.
)
xx                  # Assert that N >= 2, to prevent the unwanted match of
                    # 0 and 1 by both of the negative lookahead statements.
Deadcode
quelle
1
Sparen Sie 11 Bytes, indem Sie direkt nach einer Zahl suchen, die kleiner als eine Zweierpotenz ist: Probieren Sie es online aus!
Neil
@ Neil Vielen Dank! Ich wünschte, ich hätte daran gedacht, aber genau das wollte ich auch!
Deadcode
1
Eigentlich wäre x(x+)(?=\3$)es etwas effizienter darüber nachzudenken ?
Neil
Ja, du hast absolut recht.
Deadcode
2

Regex (ECMAScript), 29 Bytes

^(?!(xx+|(x(x))+)(\1\3)+$)xxx

Probieren Sie es online!

Inspiriert von Grimy im Chat

Der reguläre Ausdruck gibt an, dass die Eingabe größer als 3 ist und keine der folgenden Formen aufweist: (xx+)\1+oder ((xx)+)(\1x)+.

Der erste stimmt mit zusammengesetzten Zahlen überein.
Die Sekunde stimmt mit einer Zahl überein, die um 1 kleiner als ein Vielfaches einer ungeraden Zahl größer als 2 ist.

Die erste stimmt nicht mit den Primzahlen oder 0oder überein 1.
Die zweite stimmt nicht mit den Nummern des Formulars überein2n-1

Da 2 die einzige Primzahl ist, die 1 weniger als eine ungerade Primzahl ist, stimmt der negative Lookahead zusammen mit der Behauptung, dass die Eingabe größer als 3 ist, nur mit Mersenne-Primzahlen überein.

H.PWiz
quelle
1

Ruby, 47 Bytes

->b{!("%b"%(b/2)=~/0/||(2...b).find{|a|b%a<1})}
GB
quelle
1

Julia, 26 Bytes

n->isprime(n)&&ispow2(n+1)
Alephalpha
quelle
1

Python, 65 Bytes

f=lambda n,i=3:(n^i)-all(n%i for i in range(2,n))<0 or f(n,-~i|i)

Ausgänge über Exit Code. Rekursionsfehler für False. Kein Fehler für True.

Wie es funktioniert

Da 2^n-1in binär ganz aus Einsen gemacht wird, kommt die nächste2^n-1 Zahl durch generiert werdennumber|number+1 .

Diese Funktion verwendet dies, indem sie jede 2^n-1Zahl rekursiv überprüft, um festzustellen, ob es sich um eine Primzahl handelt, und um eine Gleichung für die Eingabe. Wenn die Zahl keine Mersenne-Primzahl ist, wird Python möglicherweise einen Fehler auslösen, da die maximale Rekursionstiefe überschritten worden wäre.

Cormac
quelle
1
Wenn ich mich nicht irre, <0~> 0>.
Jonathan Frech
1

Aufdringlich , 7 Bytes

oBoIpP#

Probieren Sie es online!

Dies nutzt die Tatsache aus, dass Mersenne-Zahlen nur Einsen in ihrer Binärdarstellung haben:

oB      \ Pop input, push its binary digits.
  oI    \ Re-push the input
    p   \ Test its primality (0/1)
     P# \ Print the product of the stack

Das Stack-Produkt wird nur sein, 1wenn die Zahl in ihrer binären Darstellung keine Nullen hat und ihre Primalität ist True.

FlipTack
quelle
1

Pyth , 8 Bytes

&.AjQ2P_

Überprüfen Sie alle Testfälle.

Pyth , 8 Bytes

<.&QhQP_

Überprüfen Sie alle Testfälle.


Wie?

Code-Aufschlüsselung # 1

&.AjQ2P_    Full program with implicit input.

      P_    Is Prime?
   jQ2      Convert the input to binary as a list of digits.
 .A         All the elements are truthy (i.e. all are 1).
&           Logical AND.
            Output implicitly.

Wie funktioniert das?

Eine Zahl der Form 2 n - 1 enthält immer nur 1 , wenn sie binär geschrieben ist. Daher testen wir, ob alle seine Binärziffern 1 sind und ob es eine Primzahl ist.

Code-Aufschlüsselung # 2

<.&QhQP_    Full program with implicit input.

      P_    Is Prime?
    hQ      Input + 1.
 .&Q        Bitwise AND between the input and ^.
<           Is smaller than? I.e. The bitwise AND results in 0 and the primality test results in 1.
            Output implicitly.

Wie funktioniert das?

Dieser Test prüft, ob die Eingabe + 1 eine Zweierpotenz ist (dh ob es sich um eine Mersenne-Zahl handelt), und führt dann den Primalitätstest durch. Ist in Python booleine Unterklasse von int, so wird die Wahrheit als 1 und die Falschheit als 0 behandelt . Um nicht explizit zu überprüfen, ob einer 0 und der andere 1 ist , vergleichen wir ihre Werte mit <(da wir nur 1 solchen Fall haben).

Mr. Xcoder
quelle
1

Java 8, 53 52 49 Bytes

n->{int i=1;for(;n%++i>0;);return(n&n+1|i^n)==0;}

Fehler behoben und dank @Nevay um 4 Bytes golfen .

Erläuterung:

Probieren Sie es hier aus.

n->{                // Method with integer parameter and boolean return-type
  int i=1;          //  Temp integer `i`, starting at 1
  for(;n%++i>0;);   //  Loop and increase `i` as long as `n` is divisible by `i`
  return(n&n+1|i^n) //  Then return if `n` bitwise-AND `n+1` bitwise-OR `i` bitwise-XOR `n`
          ==0;      //  is exactly 0
}                   // End of method
Kevin Cruijssen
quelle
Die aktuelle Lösung gibt truefür jede Primzahl> 2, nicht nur für Mersenne-Primzahlen, 56 Bytes zurück:n->{for(int i=2;i<n;n&=-n%i++>>-1);return(n&n+1)<1&n>2;}
Nevay,
1
52 Bytes:n->{int i=1;for(;++i<n&n%i>0;);return(n&n+1|i^n)<1;}
Nevay
@Nevay Danke .. Und nicht sicher, warum die Testfälle keine Primzahlen enthielten, die keine Mersenne-Primzahlen sind .. Fügte sie selbst hinzu, und Sie hatten in der Tat Recht.
Kevin Cruijssen
1
49 Bytes:n->{int i=1;for(;n%++i>0;);return(n&n+1|i^n)==0;}
Nevay
1

Python 3, 68 Bytes

a=int(input());print(a&-~a<1and a>1and all(a%b for b in range(2,a)))

Probieren Sie es hier aus

Python 2, 63 Bytes

a=input();print(a&-~a<1)and a>1and all(a%b for b in range(2,a))

Probieren Sie es hier aus


Danke für den Vorschlag Jonathan


Offen für Vorschläge zur Reduzierung des bytecount.

ABcDexter
quelle
1
1 and~> 1and.
Jonathan Frech
0

Python, 93 Bytes

def f(a):
 for b in range(a):
  if(a+1==2**b and not[i for i in range(2,a)if a%i<1]):return 1

Dieser Code würde sowohl in Python 2 als auch in Python 3 funktionieren, daher habe ich keine Version angegeben.

sonrad10
quelle
0

Schläger 76 Bytes

(define(g m)(for/or((i m))(= m(-(expt 2 i)1))))(if(and(prime? n)(g n))#t #f)

Ungolfed:

(require math)
(define(f n)
  (define (ispowerminus1 m)
    (for/or ((i m))
      (= m (-(expt 2 i)1))))
  (if (and (prime? n)
           (ispowerminus1 n))
      #t #f))

Testen:

(f 1)
(f 2)
(f 20)
(f 51)
(f 63)
(f 3)
(f 31)
(f 8191)

Ausgabe:

#f
#f
#f
#f
#f
#t
#t
#t
rnso
quelle
0

PHP, 53 Bytes

for($i=$n=$argv[1];--$i&&$n%$i;);echo!($i-1|$n+1&$n);

Übernimmt das Kommandozeilenargument; druckt 1für Mersenne prime, leere Zeichenfolge sonst. Laufen Sie mit-r .

Nervenzusammenbruch

for($i=$n=$argv[1];--$i&&$n%$i;);   // loop $i down from $n-1 until $i divides $n
                        // If $n is prime, loop ends with $i=1. ($n=1 -> $i=0)
echo!($i-1|$n+1&$n);    // If $i!=1, $n is not prime. If ($n+1&$n)>0, $n is not Mersenne.
                        // If either $i-1 or $n+1&$n is truthy, the negation will be false.
Titus
quelle
0

C 94 Bytes

g(n,i){return--i?g(2*n,i):n;}n,r;f(x){for(n=r=1;++n<x;)r=x%n?x^g(2,n)-1?r:r|2:r&2;return r>2;}

Gibt 1 zurück, wenn die Zahl eine Mersenne-Primzahl ist, andernfalls 0.

Steadybox
quelle
Schlagen Sie ~x+g(2,n)stattdessen vorx^g(2,n)-1
ceilingcat
0

Scala, 59 Bytes

def f(t:BigInt)=t.isProbablePrime(t.bitLength*9)&(1+t)%2==0

Für diese Funktion muss der Eingang a sein BigInt. Sie können einfach eine Zeichenfolge "162259276829213363391578010288127" (2 ** 107-1 ist eine Mersenne-Primzahl) in konvertieren, BigIntindem Sie tunBigInt("162259276829213363391578010288127") . Es könnte schief gehen, wie der Name der isProbablePrime()Methode vermuten lässt. Aber die Wahrscheinlichkeit ist nicht mehr als0.5^(t.bigLength)*9 .

Die eigenständige Skriptversion ist 72 Byte lang.

val t=BigInt(args(0));print(t.isProbablePrime(t.bitLength*9)&(1+t)%2==0)

Angenommen, wir speichern es als "t.scala", dann kann das Programm ausgeführt werden als

>scala t.scala 162259276829213363391578010288127
>true
Aria Axe
quelle
Sie können das Entfernen Probablevon , isProbablePrimewenn Scala eine hat isPrimeFunktion.
MilkyWay90
0

Perl 5 , 53 Bytes

52 Byte Code + 1 für -p

$f=0|sqrt;1while$_%$f--;$_=!$f*(sprintf'%b',$_)!~/0/

Probieren Sie es online!

Xcali
quelle
Laut -pMetakonsens wird die als eine andere Programmiersprache klassifiziert und zählt daher nicht zu Ihrem Bytecount.
MilkyWay90