Finden der n-ten Primzahl so, dass die Primzahl - 1 durch n teilbar ist

33

Problem

Das Ziel ist, wie der Titel sagt, die n-te Primzahl so zu finden, dass die Primzahl-1 durch n teilbar ist.

Erläuterung

Hier ist ein Beispiel, damit Sie die Frage verstehen. Dies ist nicht unbedingt die Art und Weise, wie sie gelöst werden sollte. Es ist nur ein Weg, um die Frage zu erklären

Bei einer Eingabe von 3 würden wir uns zuerst alle Primzahlen ansehen

 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 ...

Dann wählen wir die Primzahlen so aus, dass die Primzahl - 1 durch n teilbar ist (in diesem Fall 3).

 7 13 19 31 37 43 61 67 73 79 97 103 107 109 127 ...

Wir wählen dann den n-ten Term in dieser Reihenfolge aus

Wir würden 19 für eine Eingabe von 3 ausgeben

Hinweis

Wir können uns dies auch als die n-te Primzahl in der Folge {1, n + 1, 2n + 1, 3n + 1 ... kn + 1} vorstellen, wobei k eine beliebige natürliche Zahl ist

Testfälle

  1 --> 2
  2 --> 5
  3 --> 19
  4 --> 29
100 --> 39301
123 --> 102337
Ando Bando
quelle
Sie sagen N-te Primzahl [...] teilbar durch n . Sind N und n die gleiche Zahl?
Dennis
Entschuldigung, ja, sie sind die gleichen, ich hätte es jetzt
reparieren
3
A077317
Gabriel Benamy
4
Möglicherweise möchten Sie den Testfällen 1 -> 2 hinzufügen . Bei einer meiner Antworten war es irgendwann falsch.
Dennis
Ein anderer Weg, dies auszudrücken, ist "Finde die n-te Primzahl in der arithmetischen Folge 1, n + 1,2n + 1, ..., kn + 1, ... (wobei Dirichlets Thm garantiert unendlich viele Primzahlen hat). )
hardmath

Antworten:

9

05AB1E , 9 8 Bytes

05AB1E verwendet die CP-1252- Codierung.

Dank Osable wurde ein Byte gespeichert

µN¹*>Dp½

Probieren Sie es online!

Erläuterung

µ          # for N in [1 ...] loop until counter == input
 N¹*>      # N*input+1 (generate multiples of input and increment)
     D     # duplicate
      p½   # if prime, increase counter
           # implicitly output last prime
Emigna
quelle
3
Anstatt zu brachialisieren, würde ich vorschlagen, zuerst ein Vielfaches von N zu generieren und dann zu prüfen, ob es sich um Primzahlen handelt. Ich bin auf µN¹*>Dp½die Idee gekommen, die ein Byte spart und die Berechnung beschleunigt.
Osable
2
@Osable: Ah natürlich! Das ist in der Tat ein viel besserer Ansatz. Danke :)
Emigna
7

Python 2, 58 Bytes

n=N=input();m=k=1
while N:m*=k*k;k+=1;N-=m%k>~-k%n
print k
Dennis
quelle
5

Mathematica, 48 Bytes

Select[Array[Prime,(n=#)^3],Mod[#-1,n]==0&][[n]]&

Unbenannte Funktion, die ein einzelnes Argument verwendet, das sie benennt n. Erzeugt eine Liste der ersten n^3Primzahlen, wählt die Primzahlen aus, die zu 1 Modulo kongruent sind n, und nimmt dann das ndritte Element des Ergebnisses. Es läuft in einigen Sekunden am Eingang 123.

Es ist derzeit nicht bekannt, ob es unter den ersten n^3Primzahlen immer nur eine einzige Primzahl gibt, die zu 1 Modulo kongruent ist n, viel weniger n. nUnter der Annahme der verallgemeinerten Riemannschen Hypothese kann der Algorithmus jedoch (zumindest für große ) als richtig erwiesen werden !

Greg Martin
quelle
5

Haskell, 59 47 Bytes

f n=[p|p<-[1,n+1..],all((<2).gcd p)[2..p-1]]!!n

Anwendungsbeispiel: f 4-> 29.

Wie es funktioniert:

[p|p<-[1,n+1..]                     ]    -- make a list of all multiples of n+1
                                         -- (including 1, as indexing is 0-based)
           ,all((<2).gcd p)[2..p-1]      -- and keep the primes
                              !!n       -- take the nth element

Bearbeiten: Vielen Dank an @Damien für 12 Bytes, indem der Teilbarkeitstest entfernt und zunächst nur die Vielfachen betrachtet werden.

nimi
quelle
f n=[p|p<-[1,n+1..],all((<2).gcd p)[2..p-1]]!!n
Damien
@ Damien: Wow, eine Byte-Ersparnis von 20%. Vielen Dank!
nimi
3

Gelee , 9 Bytes

‘ÆP>%ð#Ṫ‘

Probieren Sie es online!

Wie es funktioniert

‘ÆP>%ð#Ṫ‘  Main link. Argument: n

     ð#    Call the dyadic chain to the left with right argument n and left
           argument k = n, n+1, n+2, ... until n of them return 1.
‘          Increment; yield k+1.
 ÆP        Test k+1 for primality, yielding 1 or 0.
    %      Compute k%n.
   >       Compare the results to both sides, yielding 1 if and only if k+1 is
           prime and k is divisible by n.
       Ṫ   Tail; extract the last k.
        ‘  Increment; yield k+1.
Dennis
quelle
3

Java 7, 106 Bytes

int c(int n){for(int z=1,i=2,j,x;;i++){x=i;for(j=2;j<x;x=x%j++<1?0:x);if(x>1&(i-1)%n<1&&z++==n)return i;}}

Ungolfed:

int c(int n){
  for(int z = 1, i = 2, j, x; ; i++){
    x = i;
    for(j = 2; j < x; x = x % j++ < 1
                           ? 0
                           : x);
    if(x > 1 & (i-1) % n < 1 && z++ == n){
      return i;
    }
  }
}

Testcode:

Versuchen Sie es hier (letzten Testfall führt zu einer Zeitüberschreitung auf ideone)

class M{
  static int c(int n){for(int z=1,i=2,j,x;;i++){x=i;for(j=2;j<x;x=x%j++<1?0:x);if(x>1&(i-1)%n<1&&z++==n)return i;}}

  public static void main(String[] a){
    System.out.println(c(1));
    System.out.println(c(2));
    System.out.println(c(3));
    System.out.println(c(4));
    System.out.println(c(100));
    System.out.println(c(123));
  }
}

Ausgabe:

2
5
19
29
39301
102337
Kevin Cruijssen
quelle
Schön, den ungolfed Code zum Vergleich zu sehen, aber die Tests müssten auf dem golfed Code sein, um aussagekräftig zu sein ...
Trichoplax
@trichoplax Nun, ich poste immer das vollständige Testprogramm im Ungolfed & Test Code Teil meiner Antworten. Die System.out.printlnwerden meistens hinzugefügt, damit Sie sehen, welche Eingabe ich verwendet habe, um die angezeigte Ausgabe zu geben, und alles wird auch angegeben, falls jemand es in seine IDE kopieren und einfügen möchte, um damit herumzuspielen.
Kevin Cruijssen
1
Mein Kommentar war nicht wirklich ernst gemeint - es könnte einige Leute glauben lassen, Sie hätten den Code erst vor dem Golfen getestet . Sie könnten immer drei Abschnitte haben: Golf, Ungolf und Golf mit Testcode, wenn Sie diese Annahme ablehnen möchten ...
Trichoplax
1
@trichoplax Ah ok, in diesem Fall ist es in der Tat ein berechtigter und guter Kommentar. :) Ich werde diese bearbeiten und sie für zukünftige Herausforderungen berücksichtigen.
Kevin Cruijssen
3

Nasm 679 Bytes (Anweisung Intel 386 CPU 120 Bytes)

isPrime1:  
push ebp
mov ebp,dword[esp+ 8]
mov ecx,2
mov eax,ebp
cmp ebp,1
ja .1
.n: xor eax,eax
jmp short .z
.1: xor edx,edx
cmp ecx,eax
jae .3
div ecx
or edx,edx
jz .n
mov ecx,3
mov eax,ebp
.2: xor edx,edx
cmp ecx,eax
jae .3
mov eax,ebp
div ecx
or edx,edx
jz .n
inc ecx
inc ecx
jmp short .2
.3: xor eax,eax
inc eax
.z: pop   ebp
ret 4
Np:  
push esi
push edi
mov esi,dword[esp+ 12]
xor edi,edi
or esi,esi
ja .0
.e: xor eax,eax
jmp short .z
.0: inc esi
jz .e
push esi
call isPrime1
add edi,eax
dec esi
cmp edi,dword[esp+ 12]
jae .1
add esi,dword[esp+ 12]
jc .e
jmp short .0
.1: mov eax,esi
inc eax
.z: pop edi
pop esi
ret 4

Dies ist eine ungolfed und die Ergebnisse

;0k,4ra,8Pp
isPrime1: 
          push    ebp
          mov     ebp,  dword[esp+  8]
          mov     ecx,  2
          mov     eax,  ebp
          cmp     ebp,  1
          ja      .1
.n:       xor     eax,  eax
          jmp     short  .z
.1:       xor     edx,  edx
          cmp     ecx,  eax
          jae     .3
          div     ecx
          or      edx,  edx
          jz      .n
          mov     ecx,  3
          mov     eax,  ebp
.2:       xor     edx,  edx
          cmp     ecx,  eax
          jae     .3
          mov     eax,  ebp
          div     ecx
          or      edx,  edx
          jz      .n
          inc     ecx
          inc     ecx
          jmp     short  .2
.3:       xor     eax,  eax
          inc     eax
.z:       
          pop     ebp
          ret     4

; {1, n+1, 2n+1, 3n+1 }
; argomento w, return il w-esimo primo nella successione di sopra
;0j,4i,8ra,12P
Np:       
          push    esi
          push    edi
          mov     esi,  dword[esp+  12]
          xor     edi,  edi
          or      esi,  esi
          ja      .0
.e:       xor     eax,  eax
          jmp     short  .z
.0:       inc     esi
          jz      .e
          push    esi
          call    isPrime1
          add     edi,  eax
          dec     esi
          cmp     edi,  dword[esp+  12]
          jae     .1
          add     esi,  dword[esp+  12]
          jc      .e
          jmp     short  .0
.1:       mov     eax,  esi
          inc     eax
.z:       
          pop     edi
          pop     esi
          ret     4

00000975  55                push ebp
00000976  8B6C2408          mov ebp,[esp+0x8]
0000097A  B902000000        mov ecx,0x2
0000097F  89E8              mov eax,ebp
00000981  81FD01000000      cmp ebp,0x1
00000987  7704              ja 0x98d
00000989  31C0              xor eax,eax
0000098B  EB28              jmp short 0x9b5
0000098D  31D2              xor edx,edx
0000098F  39C1              cmp ecx,eax
00000991  731F              jnc 0x9b2
00000993  F7F1              div ecx
00000995  09D2              or edx,edx
00000997  74F0              jz 0x989
00000999  B903000000        mov ecx,0x3
0000099E  89E8              mov eax,ebp
000009A0  31D2              xor edx,edx
000009A2  39C1              cmp ecx,eax
000009A4  730C              jnc 0x9b2
000009A6  89E8              mov eax,ebp
000009A8  F7F1              div ecx
000009AA  09D2              or edx,edx
000009AC  74DB              jz 0x989
000009AE  41                inc ecx
000009AF  41                inc ecx
000009B0  EBEE              jmp short 0x9a0
000009B2  31C0              xor eax,eax
000009B4  40                inc eax
000009B5  5D                pop ebp
000009B6  C20400            ret 0x4
68

000009B9  56                push esi
000009BA  57                push edi
000009BB  8B74240C          mov esi,[esp+0xc]
000009BF  31FF              xor edi,edi
000009C1  09F6              or esi,esi
000009C3  7704              ja 0x9c9
000009C5  31C0              xor eax,eax
000009C7  EB1D              jmp short 0x9e6
000009C9  46                inc esi
000009CA  74F9              jz 0x9c5
000009CC  56                push esi
000009CD  E8A3FFFFFF        call 0x975
000009D2  01C7              add edi,eax
000009D4  4E                dec esi
000009D5  3B7C240C          cmp edi,[esp+0xc]
000009D9  7308              jnc 0x9e3
000009DB  0374240C          add esi,[esp+0xc]
000009DF  72E4              jc 0x9c5
000009E1  EBE6              jmp short 0x9c9
000009E3  89F0              mov eax,esi
000009E5  40                inc eax
000009E6  5F                pop edi
000009E7  5E                pop esi
000009E8  C20400            ret 0x4
000009EB  90                nop
120


[0, 0] [1, 2] [2, 5] [3, 19] [4, 29] [5, 71] [6, 43] [7, 211] [8, 193] [9, 271] [1
0, 191] [11, 661] [12, 277] [13, 937] [14, 463] [15, 691] [16, 769] [17, 1531] [18
, 613] [19, 2357] [20, 1021] [21, 1723] [22, 1409] [23, 3313] [24, 1609] [25, 3701
] [26, 2029] [27, 3187] [28, 2437] [29, 6961] [30, 1741] [31, 7193] [32, 3617] [33
, 4951] [34, 3877] [35, 7001] [36, 3169] [37, 10657] [38, 6271] [39, 7879] [40, 55
21] [41, 13613] [42, 3823] [43, 15137] [44, 7349] [45, 9091] [46, 7499] [47, 18049
] [48, 6529] [49, 18229] [50, 7151] [51, 13159] [52, 10141] [53, 26501] [54, 7669]
 [55, 19801] [56, 11593] [57, 18127] [58, 13109] [59, 32569] [60, 8221] [61, 34649
] [62, 17981] [63, 21799] [64, 16001] [65, 28081] [66, 10429] [67, 39799] [68, 193
81] [69, 29947] [70, 14771] [71, 47713] [72, 16417] [73, 51539] [74, 25013] [75, 2
9101] [76, 26449] [77, 50051] [78, 16927] [79, 54037] [80, 23761] [81, 41149] [82,
 31489] [83, 68891] [84, 19237] [85, 51341] [86, 33713] [87, 45589] [88, 34057] [8
9, 84551] [90, 19531] [91, 64793] [92, 42689] [93, 54499] [94, 41737] [95, 76001]
[96, 27457] [97, 97583] [98, 40867] [99, 66529] [100, 39301] [101, 110899] [102, 2
9989] [103, 116803] [104, 49297] [105, 51871] [106, 56711] [107, 126047] [108, 385
57] [109, 133853] [110, 42901] [111, 76369] [112, 53089] [113, 142607] [114, 40129
] [115, 109481] [116, 63337] [117, 83071] [118, 67733] [119, 112337] [120, 41281]
[121, 152219] [122, 70639] [123, 102337]
RosLuP
quelle
2

Eigentlich 13 Bytes

Golfvorschläge willkommen! Probieren Sie es online!

;╗`PD╜@%Y`╓NP

Ungolfing

         Implicit input n.
;╗       Save a copy of n to register 0.
`...`╓   Push first n values where f(x) is truthy, starting with f(0).
  PD       Get the x-th prime - 1.
  ╜@%      Push (x_p - 1) % n.
  Y        If x_p-1 is divisible by n, return 1. Else, return 0.
NP       Get the n-th prime where n_p-1 is divisible by n.
         Implicit return.
Sherlock9
quelle
2

Common Lisp, 162 Bytes

(defun s(n)(do((b 2(loop for a from(1+ b)when(loop for f from 2 to(1- a)never(=(mod a f)0))return a))(a 0)(d))((= a n)d)(when(=(mod(1- b)n)0)(incf a)(setf d b))))

Verwendung:

* (s 100)

39301

Ungolfed:

(defun prime-search (n)
  (do ((prime 2 (loop for next from (1+ prime) when
                 (loop for factor from 2 to (1- next) never
                      (= (mod next factor) 0)) return next))
       (count 0) (works))
      ((= count n) works)
    (when (= (mod (1- prime) n) 0)
      (incf count)
      (setf works prime))))

Einige dieser loopKonstrukte können wahrscheinlich zu doSchleifen verkürzt werden, aber das ist, was ich jetzt habe.

künstlich
quelle
2

MATL , 12 Bytes

1i:"`_YqtqG\

Probieren Sie es online!

(Bei der Eingabe tritt 123im Online-Compiler eine Zeitüberschreitung auf, sie funktioniert jedoch offline.)

Erläuterung

1          % Push 1
i:         % Input n and push [1 2 ... n]
"          % For each (that is, do the following n times)
  `        %   Do...while
    _Yq    %     Next prime
    tq     %     Duplicate, subtract 1
    G      %     Push n again
    \      %     Modulo
           %   End (implicit). Exit loop if top of stack is 0; else next iteration
           % End (implicit)
           % Display (implicit)
Luis Mendo
quelle
1

Perl, 77 76 + 1 = 77 Bytes

for($p=2;@a<$_;$p++){push@a,$p if(1 x$p)!~/^(11+?)\1+$/&&($p%$_<2)}say$a[-1]

Verwendet den Regex prime-testing, um festzustellen, ob $pes sich um eine Primzahl handelt, und stellt sicher, dass sie zu 1 mod der Eingabe kongruent ist (die einzigen nicht-negativen Ganzzahlen unter 2 sind 0 und 1, aber es kann nicht 0 sein, wenn es eine Primzahl ist, also muss es sein 1. spart 1 Byte mehr ==1).

Gabriel Benamy
quelle
Dies scheint 3 für Eingabe 1 zu drucken (sollte 2 sein ).
Dennis
Sie können 10 Byte einsparen, indem Sie Folgendes tun (1 x++$.)!~/^(11+?)\1+$/&&($.%$_<2)&&push@a,$.while@a<$_;say$a[-1](worüber ich in meinem vorherigen Kommentar gesprochen habe). Allerdings scheint die Ausgabe (von beiden Versionen) für mindestens 2 und 3 falsch ...
Dada
1

Mathematica 44 Bytes

   Pick[x=Table[i #+1,{i,# #}],PrimeQ/@x][[#]]&

Sehr schnell. Verwendet die Idee aus dem "Hinweis"

% /@ {1, 2, 3, 4, 100, 123} // Timing

Ausgabe

{0.0156001, {2, 5, 19, 29, 39301, 102337}}
Kelly Lowder
quelle
1

Perl 6 ,  46 39  37 Bytes

->\n{(2..*).grep({.is-prime&&($_-1)%%n})[n-1]}
->\n{(1,n+1...*).grep(*.is-prime)[n-1]}
{(1,$_+1...*).grep(*.is-prime)[$_-1]}
Brad Gilbert b2gills
quelle
0

Java 8, 84 Bytes

Golf gespielt

(n)->{for(int s=n,i=1;;i+=n)for(int j=2;i%j>0&j<i;)if(++j==i&&--s<1)return n>1?i:2;}

Ungolfed

(n) -> { 
for (int s = n,      // Counting down to find our nth prime.
    i = 1;           // Counting up for each multiple of n, plus 1.
    ;                // No end condition specified for outer for loop.
    i += n)          // Add n to i every iteration.
for (int j = 2;      // Inner for loop for naive primality check.
     i % j > 0)      // Keep looping while i is not divisible by j 
                     // (and implicitly while j is less than i).
     if(++j==i       // Increment j. If j has reached i, we've found a prime
     &&              // Short-circutting logical AND, so that we only decrement s if a prime is found
     --s < 1)        // If we've found our nth prime...
     return n>1?i:2; // Return it. Or 2 if n=1, because otherwise it returns 3.
}

Erläuterung

Lösung inspiriert von mehreren anderen Antworten. Die Funktion ist ein Lambda, das ein einzelnes int erwartet.

Das n>1?i:2ist ein billiger Hack, weil ich keinen besseren Weg finden könnte, den Fall von n = 1 zu betrachten.

Diese Lösung läuft auch bei Ideone ab, wurde jedoch für alle Testfälle getestet. Es tritt eine Zeitüberschreitung auf, weil ich die explizite j<iPrüfung in der inneren Schleife ausgeführt habe , um ein paar Bytes zu sparen . Es ist meistens impliziert durch i%j>0... außer im Fall von i=1und j=2(die allererste Iteration), in welchem ​​Fall die Schleife läuft, bis j überläuft (nehme ich an). Dann funktioniert es problemlos für alle nachfolgenden Iterationen.

Eine Version, bei der keine Zeitüberschreitung auftritt und die einige Bytes länger ist, finden Sie hier!

Xanderhall
quelle
0

Schläger 109 Bytes

(let p((j 2)(k 0))(cond[(= 0(modulo(- j 1)n))(if(= k(- n 1))j(p(next-prime j)(+ 1 k)))][(p(next-prime j)k)]))

Ungolfed:

(define (f n)
  (let loop ((j 2)
             (k 0))
    (cond
      [(= 0 (modulo (sub1 j) n))
       (if (= k (sub1 n)) 
           j
           (loop (next-prime j) (add1 k)))]
      [else (loop (next-prime j) k)]  )))

Testen:

(f 1)
(f 2)
(f 3)
(f 4)
(f 100)
(f 123)

Ausgabe:

2
5
19
29
39301
102337
rnso
quelle
0

Ruby 64 Bytes

require'prime';f=->(n){t=n;Prime.find{|x|(x-1)%n==0&&(t-=1)==0}}

So genannt:

f.call(100)
# 39301

Diese Befehlszeilen-App funktioniert auch:

n=t=ARGV[0].to_i;p Prime.find{|x|(x-1)%n==0&&(t-=1)==0}

so genannt

ruby -rprime find_golf_prime.rb 100

aber ich bin nicht so sicher, wie ich die Zeichen zählen soll. Ich denke, ich kann den Namen der Sprache ignorieren, muss aber das -rprimeLeerzeichen und vor dem Namen des Skripts einfügen, damit er mit 63 etwas kürzer ist. . .

Neil Slater
quelle
0

R, 72 Bytes

n=scan();q=j=0;while(q<n){j=j+1;q=q+1*(numbers::isPrime(j)&!(j-1)%%n)};j

Schrecklich ineffizient und langsam, aber es funktioniert. Es liest die Eingabe von stdin und verwendet dann die isPrimeFunktion aus dem numbersPaket, um die Primzahlen zu finden. Der Rest prüft nur, ob prime - 1durch teilbar ist n.

Billywob
quelle
0

JavaScript (ES6), 65 Byte

f=(n,i=n,j=1)=>i?f(n,i-!/^(..+?)\1+$/.test('.'.repeat(j+=n)),j):j

Verwendet den regexp-Primalitätstester, da er a) 8 Byte kürzer und b) weniger rekursiv ist als mein rekursiver Ansatz.

Neil
quelle
0

Axiom 64 Bytes

f(n)==(n<0 or n>150=>0;[i*n+1 for i in 0..2000|prime?(i*n+1)].n)

weiß jemand, wie man mit Axiom-Streams schreibt? ... ein Beispiel

-> f(i)  for i in 1..150
   Compiling function f with type PositiveInteger -> NonNegativeInteger


   [2, 5, 19, 29, 71, 43, 211, 193, 271, 191, 661, 277, 937, 463, 691, 769,
    1531, 613, 2357, 1021, 1723, 1409, 3313, 1609, 3701, 2029, 3187, 2437,
    6961, 1741, 7193, 3617, 4951, 3877, 7001, 3169, 10657, 6271, 7879, 5521,
    13613, 3823, 15137, 7349, 9091, 7499, 18049, 6529, 18229, 7151, 13159,
    10141, 26501, 7669, 19801, 11593, 18127, 13109, 32569, 8221, 34649, 17981,
    21799, 16001, 28081, 10429, 39799, 19381, 29947, 14771, 47713, 16417,
    51539, 25013, 29101, 26449, 50051, 16927, 54037, 23761, 41149, 31489,
    68891, 19237, 51341, 33713, 45589, 34057, 84551, 19531, 64793, 42689,
    54499, 41737, 76001, 27457, 97583, 40867, 66529, 39301, 110899, 29989,
    116803, 49297, 51871, 56711, 126047, 38557, 133853, 42901, 76369, 53089,
    142607, 40129, 109481, 63337, 83071, 67733, 112337, 41281, 152219, 70639,
    102337, 75641, 126001, 42589, 176531, 85121, 107071, 62791, 187069, 55837,
    152419, 94873, 104761, 92753, 203857, 62929, 226571, 72661, 144103, 99401,
    193051, 69697, 168781, 112859, 133183, 111149, 250619, 60601]

Typ: Tuple NonNegativeInteger

RosLuP
quelle