Primzahlen

pumuckl

Das hast du dir leider ein ganzes Stückchen ZU einfach gemacht... Das Primzahl-Problem ist eines der schwierigsten und hat schon Programme mit einigen tausend Zeilen Code hervorgebracht - frag also nächstesmal nicht "ist das okay?" sondern besser: "was ist daran nicht okay?"

Jester

pumuckl schrieb:

Das Primzahl-Problem ist eines der schwierigsten und hat schon Programme mit einigen tausend Zeilen Code hervorgebracht

Es mag ja sein, daß es Programme gibt, die so lang sind um Primzahlen zu berechnen, aber das macht das Problem doch nicht gleich soooo schwierig. Und eines der Schwierigsten Probleme ist es schon gleich garnicht.

@XaTrIxX:

Es reicht nicht einfach nur Teiler 2,3,5,7 abzuprüfen. Ein Zahl kann ja auch nur größere Teiler haben (volkard hat schon 121 = 11*11 gepostet. Letztlich mußt Du mit Deiner Methode alle Primzahlen bis sqrt(n) testen, ob sie Teiler von n sind, nur dann kannst Du sicher sein.

MfG Jester

XaTrIxX

huch!
ist eigentlich schon richtig...
son mist!
lol

moe szyslak

Die Primfaktorzerlegung ist auch einer der schwierigen Huerden, die es noch zu loesen gibt!

FireFlow

moe szyslak schrieb:

Die Primfaktorzerlegung ist auch einer der schwierigen Huerden, die es noch zu loesen gibt!

Tjo und das bleibt besser erst einmal so, ansonsten sollten sich ein paar Leute mit neuen Verschluüsselungsalgorithmen beschäftigen.

Gruß

moe szyslak

FireFlow schrieb:

moe szyslak schrieb:

Die Primfaktorzerlegung ist auch einer der schwierigen Huerden, die es noch zu loesen gibt!

Tjo und das bleibt besser erst einmal so, ansonsten sollten sich ein paar Leute mit neuen Verschluüsselungsalgorithmen beschäftigen.

Gruß

Was machen wir dann erst wenn es Quantencomputer gibt? Dann ist kein Algorithmus mehr sicher?
Zum Glueck kann ich da ein wenig beruhigen. Ich Studiere an der Uni, wo an Quantencomputern geforscht wird (meinen Informationen gibt es weltweit nur 2 solcher Institute), und bis noch muessen sie ueber nacht das Grid auf der Uni anwerfen um auszurechnen, ob Ihr Quantencomputer richtig gerechnet hat!

Aber es kann ja noch was werden *g*

otze

verschlüsselungsalgorithmen sind nie sicher. Sie sind nur in relation zur durchschnittlichen rechenkapazität von pcs nicht in absehbarer zeit knackbar.

aber wahrscheinlich wird bei quantencomputern wieder einfach nur die schlüssellänger um ein vielfaches erhöht...

flammenvogel

otze schrieb:

aber wahrscheinlich wird bei quantencomputern wieder einfach nur die schlüssellänger um ein vielfaches erhöht...

Meines wissens sind quantencomputer nicht schneller, sondern können nur bestimmte mathematische Berechnungen schneller ausführen, als normale Prozessoren. (Potenzen...(nicht sicher))

Werner Salomon

XaTrIxX schrieb:

hey leute. ich hab n proggy geschrieben, ...
jetzt wollte ich fragen: ist das okay?

Ja, weil das Programm für Primzahlen bis 120 funktioniert.
Du kannst fragen: was kann man besser machen? Nun zunächst einmal, Dinge die sich leicht trennen lassen, voneinander trennen.
Hier z.B. die Primzahl-Bestimmung vom Eingabe-Dialog.

#include <iostream>
using namespace std;

bool istPrimzahl( int Eingabe )
{
    if(Eingabe==2 || Eingabe==3 || Eingabe==5 || Eingabe==7)
    {
        return true;
    }
    else if(Eingabe%2==0 || Eingabe%3==0 || Eingabe%5==0 || Eingabe%7==0)
    {
        return false;
    }                
    else    
    {
        return true;
    }
}

int main()
{
    int nochmal=1;
    while(nochmal==1)
    {
        int Eingabe=0;
        cout<<"Herzlich Willkommen zur Primzahlenueberpreufung! \nGeben Sie eine Zahl ein!\n";
        cin>>Eingabe;
        if( istPrimzahl( Eingabe ) )
        {
            cout<<"Diese Zahl ist eine Primzahl \n";
        }
        else
        {
            cout<<"Die Zahl ist keine Primzahl! \n";
        }
        cout<<"Druecke 1 wenn du es nochmal ausprobieren moechtest! \t";  
        cin>>nochmal;
        cout<<" \n\n\n\n\n\n\n\n\n\n";  
    }    
    system("PAUSE");
    return EXIT_SUCCESS;
}

.. besser machen kann man auch die Einrückung; dann läßt sich's besser lesen.

Dann kann man sich der Primzahl-Bestimmung zuwenden; und auf "beliebig hohe" erweitern.

#include <iostream>
#include <cmath>
using namespace std;

bool istPrimzahl( int Eingabe )
{
    if( Eingabe < 4 )
        return false; // 1,2,3 sind prim
    const int maxTeiler = int( sqrt( double( Eingabe ) ) );
    for( int teiler = 2; teiler <= maxTeiler; ++teiler )
    {
        if( Eingabe % teiler == 0 )
            return false;
    }
    return true;
}
// main() wie oben

das ist nicht die schnellste Methode, aber sie funktioniert erst mal.

Der nächste Punkt wäre die Fehlerbehandlung im verbleibenden main-Programm. Gib doch mal 1001. ein (also mit Punkt am Ende) und überlege dann, warum das passiert, was dann passiert.

Gruß
Werner

life

otze schrieb:

verschlüsselungsalgorithmen sind nie sicher. Sie sind nur in relation zur durchschnittlichen rechenkapazität von pcs nicht in absehbarer zeit knackbar.

es gibt schon verschlüsselungsalgorithmen, die bewiesenermaßen nicht knackbar sind. Z. B. bei Manchen, wenn der schlüssel völlig zufällig ist, genauso lang wie die botschaft selber und nur einmal benutzt wird (One-Time-Pads) oder eben die Quantenkryptographie..

XaTrIxX

also quantencomputer, für alle, gaaanz grob:
bei den heutigen, "normalen" computern gibt es grundsätzlich:
1 und 0
bei den Quantencomputern, wie auch immer, gibt es "Zustände zwischen 1 und 0"
Dadurch ist ein extrem hohes Spektrum möglich.
So hab ichs in der 1. Klasse HTL vor mehr als 1 Jahr gelernt...
^^
passt doch prima zum Thread "Primzahlen" oder?

flammenvogel

kann sein, dann meine ich eine andere Art von Pc ...