Gerade Zahl als Summe zweier Primzahlen darstellen

[Grey (Gast)]

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?

[Dussel (Gast)]

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.

[radiostar (Gast)]

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.

[Christian B. (casandro)]

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.

[Josef (Gast)]

Siehe auch Goldbachsche Vermutung.

Du kannst also noch beruehmt werden.

[g457 (Gast)]

> 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

[Grey (Gast)]

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?

[Dussel (Gast)]

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.

[Dussel (Gast)]

Ich muss mich verbessern: Die Bedingung muss 'kleiner oder gleich x/2' 
sein.

[Grey (Gast)]

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?

[Grey (Gast)]

Ach ja, das ist das bisherige Programm, welches sehr gut funktioniert:

void makePrime(long number){
    long i = 0, zahl;

    while(TRUE){
        while(TRUE){
            zahl = number/2-i;
            if(isprime(zahl)){
                printf("zahl = %ld ist eine Primzahl\n", zahl);
                break;
            }
            i++;
        }

        if( isprime(number - zahl) ){
            printf("\nDie Zahl %ld ist eine Primzahl \n", (number-zahl) );
            printf("\nDie Zahl %ld kann als: %ld + %ld dargestellt werden", number, (number-zahl), zahl);
            return;
        }
        i++;
    }
}

[Christian B. (casandro)]

Grey schrieb:
> Ich frag mich nur was passiert, wenn unter x/2 keine Primzahlen mehr
> vorhanden sind?

Naja, dann gibts keine weiteres Primzahlenpaar. Natürlich muss es 
kleiner Gleich x/2 heißen, da war ich unpräzise.

[g457 (Gast)]

> 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.