Gerade Zahl als Summe zweier Primzahlen darstellen

Gast #3144845
Hallo leute, wir haben neulich in unserer Laborübung die Aufgabe 
bekommen in C ein Programm zu schreiben, welches eine gerade Zahl als 
summe zweier Primzahlen darstellen soll.

Nun habe ich folgende Überlegungen gehabt:
Wenn ich die Zahl durch 2 teile, dann kann es immer noch sein, dass die 
entstandenen Zahlen wieder gerade sind, was aber nicht gut ist, denn ich 
will ja 2 Primzahlen errechnen. Wenn ich eine Primfaktorzerlegung mache, 
dann bringt mich das auch nicht weiter, weil ich habe daruch zwar nur 
Primzahlen drinnen, aber eine Multiplikation zwischen diesen 
entstandenen Primzahlen so zu gestalten dass zwei weitere rauskommen, 
ist meines erachtens nach nicht möglich...

Wie würdet ihr das ganze angehen?
Gast #3144856
Kommt drauf an, wie viel mir eine gute Lösung der Aufgabe wert ist. Wenn 
die Aufgabe nur schnell erfüllt sein soll, würde ich es einfach 
ausprobieren. Von der gegebenen geraden Zahl nacheinander Primzahlen 
abziehen, bis das Ergebnis eine Primzahl ist.
Gast #3144864
Grey schrieb:
> Wenn ich eine Primfaktorzerlegung mache,
> dann bringt mich das auch nicht weiter, weil ich habe daruch zwar nur
> Primzahlen drinnen, aber eine Multiplikation zwischen diesen
> entstandenen Primzahlen so zu gestalten dass zwei weitere rauskommen,
> ist meines erachtens nach nicht möglich...

Nein, aber Du könntest alle Primzahlen kleiner als die gegebene Zahl 
bestimmen. Und dann probierst Du einfach aus, welche Kombination passt.
#3144871
OK, C deutet darauf hin, dass es sich um kleine Zahlen handelt, da C für 
große Zahlen spezielle Bibliotheken braucht.

Du findest sicherlich relativ schnell einen Algorithmus zur Bestimmung 
ob eine Zahl eine Primzahl ist oder nicht, bzw einen Algorithmus mit dem 
Du Primzahlen bestimmen kannst. (Gibts sicher auf Wikipedia oder so)

Wenn Deine gerade Zahl x ist, bestimme Primzahlen die kleiner als x/2 
sind. Schaue bei jeder dieser Primzahlen nach ob die Differenz prim ist, 
ist sie das so hast Du ein Beispiel gefunden.
Gast #3144884
> OK, C deutet darauf hin, dass es sich um kleine Zahlen handelt, da C für
> große Zahlen spezielle Bibliotheken braucht.

'klein' und 'groß' sind relativ. Ich betrachte 2^64-1 als ziemlich groß 
:-) Unabhängig davon wird man die Goldbachvermutung wohl am 
einfachsten(tm) so angehen. Einen schnellen Prim-Checker wirds 
allerdings brauchen.

[0] Linux/amd64, long long unsigned int
Gast #3144888
Christian Berger schrieb:
> Wenn Deine gerade Zahl x ist, bestimme Primzahlen die kleiner als x/2
> sind. Schaue bei jeder dieser Primzahlen nach ob die Differenz prim ist,
> ist sie das so hast Du ein Beispiel gefunden.

Ist diese FUnktionsweise aber garantiert? Oder kann es sein, dass bei 
der ein oder anderen es doch nicht funktioniert?
Gast #3144891
Grey schrieb:
> Christian Berger schrieb:
>> Wenn Deine gerade Zahl x ist, bestimme Primzahlen die kleiner als x/2
>> sind. Schaue bei jeder dieser Primzahlen nach ob die Differenz prim ist,
>> ist sie das so hast Du ein Beispiel gefunden.
>
> Ist diese FUnktionsweise aber garantiert? Oder kann es sein, dass bei
> der ein oder anderen es doch nicht funktioniert?
Unter der Annahme, dass die besagte Goldbachsche Vermutung stimmt, die 
bis 10^17 oder sowas nachgewiesen ist, funktioniert das für alle Zahlen 
größer als 2.
Gast #3144925
Na das funktioniert ja fix!!
Ich frag mich nur was passiert, wenn unter x/2 keine Primzahlen mehr 
vorhanden sind? Dann würde doch der Algorithmus nicht funktionieren. 
Also sprich, alle Kombinationen haben nicht funktioniert, und jetzt bin 
ich bei 2 angelangt. Was jetzt?
Gast #3144928
Ach ja, das ist das bisherige Programm, welches sehr gut funktioniert:
1
void makePrime(long number){
2
    long i = 0, zahl;
3

4
    while(TRUE){
5
        while(TRUE){
6
            zahl = number/2-i;
7
            if(isprime(zahl)){
8
                printf("zahl = %ld ist eine Primzahl\n", zahl);
9
                break;
10
            }
11
            i++;
12
        }
13

14
        if( isprime(number - zahl) ){
15
            printf("\nDie Zahl %ld ist eine Primzahl \n", (number-zahl) );
16
            printf("\nDie Zahl %ld kann als: %ld + %ld dargestellt werden", number, (number-zahl), zahl);
17
            return;
18
        }
19
        i++;
20
    }
21
}
Gast #3144936
> Also sprich, alle Kombinationen haben nicht funktioniert, und jetzt bin
> ich bei 2 angelangt. Was jetzt?

Sofern Du geprüft hast, dass..
   - die Eingabe gerade
und
   - echt größer als 2 ist
und Du sodann bei obigem Problem angelangt bist, gibt es genau zwei 
Möglichkeiten:
   - Dein Programm ist falsch (oder ein Myon hat den Speicher
     korrumpiert)
oder
   - Du hast ein Gegenbeispiel zur Goldbachvermutung gefunden. Auf jeden
     Fall aufschreiben und veröffentlichen!

Ersterer Fall ist aber wahrscheinlicher.

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 13 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.