Die Goldbach-Vermutung besagt, dass jede gerade Zahl größer als zwei als die Summe zweier Primzahlen ausgedrückt werden kann. Beispielsweise,

4 = 2 + 2
6 = 3 + 3
8 = 5 + 3

Sobald wir jedoch 10 sind, passiert etwas Interessantes. Nicht nur 10 kann als geschrieben werden

5 + 5

es kann aber auch so geschrieben werden

7 + 3

Da 10 auf zwei Arten als die Summe zweier Primzahlen ausgedrückt werden kann , sagen wir, dass die "Goldbach-Partition" 10 ist 2. Oder allgemeiner

Die Goldbach-Teilung einer Zahl ist die Gesamtzahl der unterschiedlichen Schreibweisen, bei n = p + qdenen pund qPrimzahlen und sindp >= q

Ihre Herausforderung besteht darin, ein Programm oder eine Funktion zu schreiben, die die Goldbach-Partition einer Zahl findet. Technisch wird der Begriff "Goldbach-Partition" nur für gerade Zahlen verwendet. Da die ungerade ganze Zahl p + 2 auch als Summe zweier Primzahlen ausgedrückt werden kann, wenn p> 2 eine Primzahl ist, wird dies auf alle positiven ganzen Zahlen ausgedehnt ( A061358 ).

Sie können davon ausgehen, dass Ihre Eingabe immer eine positive Ganzzahl ist, und Sie können Eingaben und Ausgaben in einer unserer zulässigen Standardmethoden vornehmen, z. B. Funktionsargumente und Rückgabewerte, STDIN und STDOUT, Lesen und Schreiben in eine Datei usw.

Die Goldbach-Partitionen der positiven ganzen Zahlen bis zu 100 sind:

0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 2, 1, 2, 1, 3, 0, 3, 1,
3, 0, 2, 0, 3, 1, 2, 1, 4, 0, 4, 0, 2, 1, 3, 0, 4, 1, 3, 1, 4, 0, 5, 1, 4,
0, 3, 0, 5, 1, 3, 0, 4, 0, 6, 1, 3, 1, 5, 0, 6, 0, 2, 1, 5, 0, 6, 1, 5, 1,
5, 0, 7, 0, 4, 1, 5, 0, 8, 1, 5, 0, 4, 0, 9, 1, 4, 0, 5, 0, 7, 0, 3, 1, 6

Wie üblich gelten Standardlücken und die kürzeste Antwort in Bytes gewinnt!

Gelee , 8 Bytes

_ÆRÆPSHĊ

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

_ÆRÆPSHĊ  Main link. Argument: n (positive integer)

 ÆR       Prime range; yield [2, 3, 5, ..., n].
_         Subtract all primes in this range from n.
   ÆP     Compute the primality of the resulting differences.
          This returns 1 for each prime p such that n - p is also prime.
     S    Compute the sum of the resulting Booleans.
      H   Divide it by 2, since [p, n - p] and [n - p, p] have both been counted.
       Ċ  Ceil; round the resulting quotient up (needed if n = 2p).

Python 2, 76 Bytes

g=lambda n,k=2:n/k/2and all(x%i for x in[k,n-k]for i in range(2,x))+g(n,k+1)

Kriecht rekursiv von k=2bis n/2und addiert Werte, bei denen beide kund n-kPrimzahlen sind. Es sei schön, zu zählen , nstatt zur gleichen Zeit nach unten, aber das hat ein Problem , das k=0und k=1fälschlicherweise prime genannt werden:

g=lambda n,k=0:n/k and all(x%i for x in[k,n]for i in range(2,x))+g(n-1,k+1)

Die Primalitätsprüfung ist eine Probedivision, die durch die Prüfung beider kund n-kzusammen verkürzt wird . Ich fand dies kürzer als die Verwendung eines Wilson-Theorem-Generators (79 Bytes):

f=lambda n,k=1,P=1,l=[]:n/k and P%k*(n-k in l+P%k*[k])+f(n,k+1,P*k*k,l+P%k*[k])

Die Idee für dieses ist, eine Liste aller Primzahlen in der unteren Hälfte zu führen, um sie zu überprüfen, bis wir in der oberen Hälfte sind, aber für den Mittelpunkt k=n/2hatten wir keine Zeit n-k, die Liste zu erweitern, wenn wir ankommen k. Eine iterative Version umgeht dies, hat aber 82 Bytes:

n=input()
s=P=k=1;l=[]
while k<n:l+=P%k*[k];s+=P%k*(n-k in l);P*=k*k;k+=1
print~-s

MATL , 8 Bytes

tZq&+=Rz

Probieren Sie es online!

Erläuterung

Betrachten Sie die Eingabe 8als Beispiel

      % Take input implicitly
t     % Duplicate
      % STACK: 8, 8
Zq    % All primes up to that number
      % STACK: 8, [2 3 5 7]
&+    % Matrix with all pairwise additions
      % STACK: 8, [4  5  7  9
                   5  6  8 10
                   7  8 10 12
                   9 10 12 14]
=     % True for entries that equal the input
      % STACK: [0 0 0 0
                0 0 1 0
                0 1 0 0
                0 0 0 0]
R     % Extract upper triangular part (including diagonal). 
      % This removes pairs that are equal up to order
      % STACK: [0 0 0 0
                0 0 1 0
                0 0 0 0
                0 0 0 0]
z     % Number of nonzero entries
      % STACK: 1
      % Display implicitly

Es ist interessant, das Diagramm der Sequenz mit einer leicht modifizierten Version des Codes zu beobachten:

:"@       % Input n implicitly. For each k from 1 to n, push k
tZq&+=Rz  % Same code as above. Pushes the result for each k
]v'.'&XG  % End. Concatenate all results into a vector. Plot as dots

Für die Eingabe ist 10000das Ergebnis

Sie können es bei MATL Online ausprobieren (Aktualisieren Sie die Seite, wenn sich die Schaltfläche "Ausführen" nicht in "Töten" ändert, wenn Sie darauf klicken ). Es dauert einige ungefähr 25 Sekunden, um das Diagramm für die Eingabe zu erzeugen 3000. Eingaben über ein paar Tausend werden auslaufen.

JavaScript (ES6), 77 73 70 Byte

3 Bytes dank @Arnauld eingespart

f=(n,x=n)=>--x<2||n%x&&f(n,x)
g=(a,b=a>>1)=>b>1?f(b)*f(a-b)+g(a,b-1):0

fist eine Primalitätstestfunktion; die relevante Funktion ist g.

farbeitet, indem rekursiv von n-1 heruntergezählt wird ; Der Kontrollfluss in jeder Phase sieht folgendermaßen aus:

• x<2||Wenn x <2 ist , ist die Zahl eine Primzahl; return 1 .
• n%x&&Wenn andernfalls n mod x = 0 ist , ist die Zahl keine Primzahl; zurückkehren n%x.
• f(n,x-1)Andernfalls kann die Zahl eine Primzahl sein oder nicht. Dekrementiere x und versuche es erneut.

gfunktioniert ähnlich, allerdings mit weniger Kontrollfluss. Es funktioniert, indem f (b) mit f (ab) für jede ganze Zahl b im Bereich [2, Etage (a / 2)] multipliziert und dann die Ergebnisse summiert werden. Dies gibt uns die Anzahl der Paare, die sich zu einer Summe summieren, bei der beide Zahlen im Paar Primzahlen sind, und genau das ist, was wir wollen.

05AB1E , 10 8 Bytes

Extrem ineffizient.

D!f-pO;î

Probieren Sie es online! oder Versuchen Sie es mit einer weniger effizienten Methode zum Generieren von Primzahlen

Erläuterung

n = 10 als Beispiel verwendet.

D          # duplicate
           # STACK: 10, 10 
 !         # factorial
           # STACK: 10, 3628800
  f        # unique prime factors
           # STACK: 10, [2,3,5,7]
   -       # subtract
           # STACK: [8,7,5,3]
    p      # is prime
           # STACK: [0,1,1,1]
     O     # sum
           # STACK: 3
      ;    # divide by 2
           # STACK: 1.5
       î   # round up
           # STACK: 2
           # implicit output

GAP , 57 Bytes

n->Number([2..QuoInt(n,2)],k->IsPrime(k)and IsPrime(n-k))

Ich denke nicht, dass GAP einen kürzeren Weg als diesen offensichtlichen hat. Numberzählt, wie viele Elemente einer Liste ein Prädikat erfüllen.

Verwenden Sie es, um die ersten 100 Werte zu berechnen:

gap> List([1..100],n->Number([2..QuoInt(n,2)],k->IsPrime(k)and IsPrime(n-k)));
[ 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 2, 1, 2, 1, 3, 0, 3, 1, 
  3, 0, 2, 0, 3, 1, 2, 1, 4, 0, 4, 0, 2, 1, 3, 0, 4, 1, 3, 1, 4, 0, 5, 1, 4, 
  0, 3, 0, 5, 1, 3, 0, 4, 0, 6, 1, 3, 1, 5, 0, 6, 0, 2, 1, 5, 0, 6, 1, 5, 1, 
  5, 0, 7, 0, 4, 1, 5, 0, 8, 1, 5, 0, 4, 0, 9, 1, 4, 0, 5, 0, 7, 0, 3, 1, 6 ]

Brachylog , 22 Bytes

:{,A:B>=.:#pa+?,.=}fl

Probieren Sie es online!

Erläuterung

Eine direkte Abschrift des Problems.

:{                }f       Find all valid outputs of the predicate in brackets for the Input
                    l      Output is the number of valid outputs found

  ,A:B>=.                  Output = [A, B] with A >= B
         :#pa              Both A and B must be prime numbers
             +?,           The sum of A and B is the Input
                .=         Label A and B as integers that verify those constraints

Mathematica, 52 Bytes

Count[IntegerPartitions[#,{2}]//PrimeQ,{True,True}]&

Das Ergebnis wird als anonyme Funktion bereitgestellt. Versuchen Sie, ein Diagramm darüber zu zeichnen:

DiscretePlot[
 Count[IntegerPartitions[#, {2}] // PrimeQ, {True, True}] &[i], {i, 1,
   1000}]

Der Code hat übrigens die gleiche Länge wie die Funktionsversion des Demo-Codes auf OEIS.

Gelee , 12 Bytes

HRð,_@ÆPð×/S

TryItOnline
1-100

Wie?

HRð,_@ÆPð×/S - Main link: n    e.g. 22
H            - halve
 R           - range          [1,2,3,4,5,6,7,8,9,10,11] (note this will be 1 to n//2)
  ð          - dyadic chain separation
   ,         - pair with
    _@       - n -           [[1,2,3,4,5,6,7,8,9,10,11],[21,20,19,18,17,16,15,14,13,12,11]]
      ÆP     - is prime? (1 if prime 0 if not)
                            [[0,1,1,0,1,0,1,0,0,0,1],[0,0,1,0,1,0,0,0,1,0,1]]
        ð    - dyadic chain separation
         ×/  - reduce with multiplication
                             [0,0,1,0,1,0,0,0,0,0,1]
           S - sum           3

Schläger 219 Bytes

(let*((pl(for/list((i n) #:when(prime? i))i))(ll(combinations(append pl pl)2))(ol'()))(for/list((i ll))(define tl(sort i >))
(when(and(= n(apply + i))(not(ormap(λ(x)(equal? x tl))ol)))(set! ol(cons tl ol))))(length ol))

Ungolfed:

(define(f n)
 (let* ((pl                                   ; create a list of primes till n
          (for/list ((i n) #:when (prime? i))
            i))
         (ll (combinations (append pl pl) 2)) ; get a list of combinations of 2 primes
         (ol '()))                            ; initialize output list
    (for/list ((i ll))                        ; test each combination
      (define tl (sort i >))
      (when (and (= n (apply + i))            ; sum is n
                 (not(ormap (lambda(x)(equal? x tl)) ol))) ; not already in list
        (set! ol (cons tl ol))))              ; if ok, add to list
    (println ol)                              ; print list
    (length ol)))                             ; print length of list

Testen:

(f 10)
(f 100)

Ausgabe:

'((5 5) (7 3))
2
'((97 3) (89 11) (83 17) (71 29) (59 41) (53 47))
6

Eigentlich 11 Bytes

;R`p`░@-♂bΣ

Probieren Sie es online!

Erläuterung:

;R`p`░@-♂bΣ
 R`p`░       prime values in [1, n]
;     @-     subtract each value from n
        ♂b   convert each value to boolean
          Σ  sum

05AB1E , 6 Bytes

;ÅP-pO

Probieren Sie es online!

Erläuterung:

                  # implicit input (example: 10)
;                 # divide input by 2 (5)
 ÅP               # primes up to that ([2, 3, 5])
   -              # subtract from the implict input ([8, 7, 5])
    p             # isPrime? ([0, 1, 1])
     O            # sum (2), implicit output

Haskell, 73 Bytes

f n|r<-[a|a<-[2..n],all((<2).gcd a)[2..a-1]]=sum[1|p<-r,q<-r,q<=p,p+q==n]

Anwendungsbeispiel: map f [1..25]-> [0,0,0,1,1,1,1,1,1,2,0,1,1,2,1,2,0,2,1,2,1,3,0,3,1].

Direkte Implementierung der Definition: Zuerst ran alle Primzahlen binden n, dann ein 1für alle pund qvon rwo q<=pund p+q==nund addieren.