Wenn eine Zahl n gegeben ist, drucken Sie die n-te Primzahl Fermat, wobei die Fermat-Zahlen die Form 2 ^{2 ^k} + 1 haben. Dieser Code sollte theoretisch Arbeit für jeden n (dh sie codieren es nicht), obwohl es nicht für n beenden , wird erwartet , dass> 4. (Es sollte nicht 4294967297 Rück für n = 5, als 4294967297 keine Primzahl ist.)

Beachten Sie, dass zwar alle Fermat-Primzahlen die Form 2 ^{2 ⁿ} + 1 haben, jedoch nicht alle Zahlen der Form 2 ^{2 ⁿ} + 1 Primzahlen sind. Das Ziel dieser Herausforderung ist es, die n-te Primzahl zurückzugeben.

Testfälle

0 -> 3
1 -> 5
2 -> 17
3 -> 257
4 -> 65537

Regeln

Standardlücken sind nicht zulässig.
0-Indizierung und 1-Indizierung sind beide akzeptabel.
Dies ist Code-Golf , niedrigste Byte-Anzahl gewinnt.

Verwandte: Konstruierbare n-Gons

code-golf primes poi830
quelle

1

Bin ich oder interpretieren einige der Antworten die Herausforderung falsch? Schreiben wir nicht einfach ein Programm, das ausgibt 2^(2^n) + 1, wo nist die Eingabe? Dies stimmt mit Ihren Testfällen überein (von denen wir wissen, dass sie bereits erstklassig sind, sodass keine Überprüfung erforderlich ist). Und Sie erwarten nicht, dass das Programm funktioniert, wenn n> 4 ist (und n = 5 die erste Nicht-Primzahl ist).

jstnthms

Das Programm sollte theoretisch für n> 4 funktionieren, obwohl dies in der Praxis niemals funktionieren wird, da wir nur 5 Fermat-Primzahlen kennen.

Poi830

Ich verstehe den Zweck, theoretisch für alle Fermat-Primzahlen zu arbeiten, nicht wirklich, da nur 5 Begriffe bekannt sind.

Herr Xcoder

2

@CodyGray Die Testfälle sind irreführend, da dies funktioniert n=1:4. Alle Fermat-Primzahlen haben die Form 2^2^n+1, aber das bedeutet nicht, dass alle Zahlen der Form 2^2^n+1tatsächlich Primzahlen sind. Dies ist zum Beispiel der Fall n=1:4, aber nicht n=5zum Beispiel.

JAD

3

Ich denke, dass ein Teil der Verwirrung darin besteht, dass Sie sagen, dass die Eingabe ist nund die Ausgabe von der Form sein muss 2^(2^n)+1. Wenn Sie unterschiedliche Variablen für die Eingabe und den Exponenten verwenden, kann dies zu Verwirrung führen. Es kann auch hilfreich sein, wenn Sie ausdrücklich angeben, dass "n = 5 nicht in angemessener Zeit ausgegeben werden muss, aber nicht 4294967297"

Kamil Drakari,

6

Python 2 , 53 Bytes

k=input();F=2
while k:F*=F;k-=3**(F/2)%-~F/F
print-~F

Probieren Sie es online aus!

Verwendet Pépins Test .

Python 2 , 54 Bytes

f=lambda k,F=4:k and f(k-3**(F/2)%-~F/F,F*F)or F**.5+1

Probieren Sie es online aus!

xnor
quelle

3

Gelee , 13 11 Bytes

ÆẸ⁺‘©ÆPµ#ṛ®

Verwendet 1-basierte Indizierung.

Probieren Sie es online aus!

Wie es funktioniert

ÆẸ⁺‘©ÆPµ#ṛ®  Main link. No argument.

        #    Read an integer n from STDIN and call the chain to the left with
             arguments k = 0, 1, 2, ... until n matches were found.
ÆẸ           Find the integer with prime exponents [k], i.e., 2**k.
  ⁺          Repeat the previous link, yielding 2**2**k.
   ‘         Increment, yielding 2**2**k+1 and...
    ©        copy the result to the register.
     ÆP      Test the result for primality.
          ®  Yield the value from the register, i.e., the n-th Fermar prime.
         ṛ   Yield the result to the right.

Dennis
quelle

Oh, also verwendet man ṛ, um das Ergebnis zu löschen ... TIL

Leaky Nun

Oh, also verwendet man ÆẸstatt 2*für eine einzelne ganze Zahl ... BIS

Erik der Outgolfer

2

Perl 6 , 45 42 Bytes

{({1+[**] 2,2,$++}...*).grep(*.is-prime)[$_]}

Versuch es

{({1+2**2**$++}...*).grep(*.is-prime)[$_]}

Versuch es

Erweitert:

{  # bare block lambda with implicit parameter ｢$_｣

  (  # generate a sequence of the Fermat numbers

    {
      1 +
      2 ** 2 **
        $++            # value which increments each time this block is called
    }
    ...                # keep generating until:
    *                  # never stop

  ).grep(*.is-prime)\  # reject all of the non-primes
  [$_]                 # index into that sequence
}

Brad Gilbert b2gills
quelle

1

Mathematica, 56 Bytes

(t=n=0;While[t<=#,If[(PrimeQ[s=2^(2^n)+1]),t++];n++];s)&

Probieren Sie es online aus!

J42161217
quelle

0

Pyth , 14 Bytes

e.f&P_ZsIltZQ3

Probieren Sie es online aus!

Verwendet 1-Indizierung.

notjagan
quelle

0

Pyth , 14 Bytes

Lh^2^2byfP_yTQ

Versuchen Sie es online.

Hauptidee "entlehnt" von xnors Antwort in einer anderen Frage

Lh^2^2byfP_yTQ

L                    define a function with name y and variable b, which:
 h^2^2b                returns 1+2^2^b
       y             call the recently defined function with argument:
        f    Q         the first number T >= Q (the input) for which:
         P_yT            the same function with argument T returns a prime
                     and implicitly print

Gassen
quelle

0

05AB1E , 8 Bytes

Code:

Die Ergebnisse sind 1-indiziert.

µN<oo>Dp

Verwendet die 05AB1E- Codierung. Probieren Sie es online aus!

Erläuterung:

µ              # Run the following n succesful times..
 N             #   Push Nn
  oo           #   Compute 2 ** (2 ** n)
    >          #   Increment by one
     D         #   Duplicate
      p        #   Check if the number is prime
               # Implicit, output the duplicated number which is on the top of the stack

Adnan
quelle

0

Javascript, 12 46 Bytes

k=>eval('for(i=n=2**2**k+1;n%--i;);1==i&&n')

Der größte Teil des Codes wird von der Hauptprüfung übernommen, die von hier stammt .

SuperStormer
quelle

Beachten Sie, dass die n-te Fermat- Primzahl zurückgegeben werden muss , nicht nur die n-te Fermat-Nummer.

Poi830

@ poi830 jetzt nimmt der Prime Check den größten Teil der Funktion ein :(

SuperStormer

Ich denke, Sie können sagen, i <2 statt i == 1, weil Null auch hier gut ist? das sollte 2 Byte reduzieren

DanielIndie

0

Dyalog APL (29 Zeichen)

Ich bin mir fast sicher, dass dies verbessert werden kann.

{2=+/0=(⍳|⊢)a←1+2*2*⍵:a⋄∇⍵+1}

Dies ist eine rekursive Funktion, die die Anzahl der Teiler von 1 + 2 ^ 2 ^ ⍵ überprüft, wobei ⍵ das richtige Argument der Funktion ist. Wenn die Anzahl der Teiler 2 ist, ist die Zahl eine Primzahl und gibt sie zurück. Andernfalls ruft sie die Funktion erneut mit ⍵ + 1 als rechtem Argument auf.

Beispiel

{2=+/0=(⍳|⊢)a←1+2*2*⍵:a ⋄ ∇ ⍵+1}¨⍳4
      5 17 257 65537

Hier rufe ich die Funktion auf jedem von ⍳4 (die Zahlen 1-4) auf. Es wendet es der Reihe nach auf jede Zahl an.

James Heslip
quelle

0

Haskell , 61 Bytes

p n=2^2^n;f=(!!)[p x+1|x<-[0..],all((>)2.gcd(p x+1))[2..p x]]

Probieren Sie es online aus!

0-basierter Index

Erläuterung

p n=2^2^n;                                          -- helper function 
                                                    -- that computes what it says
f=                                                  -- main function
  (!!)                                              -- partially evaluate 
                                                    -- index access operator
      [p x+1|                                       -- output x-th fermat number
             x<-[0..],                              -- try all fermat number indices
                      all                 [2..p x]  -- consider all numbers smaller F_x
                                                    -- if for all of them...
                         ((>)2                      -- 2 is larger than...
                              .gcd(p x+1))          -- the gcd of F_x 
                                                    -- and the lambda input 
                                                    -- then it is a Fermat prime!   
                                                  ]

SEJPM
quelle

Fermat-Primzahlen erzeugen

Testfälle

Regeln

Antworten:

Python 2 , 53 Bytes

Gelee , 13 11 Bytes

Wie es funktioniert

Perl 6 , 45 42 Bytes

Erweitert:

Mathematica, 56 Bytes

Pyth , 14 Bytes

Pyth , 14 Bytes

05AB1E , 8 Bytes

Code:

Erläuterung:

Javascript, 12 46 Bytes

Dyalog APL (29 Zeichen)

Beispiel

Haskell , 61 Bytes