Primzahlen erkennen



  • #include<cmath>
    #include<iostream>
    using namespace std; int main()
    {
    int n;
    cout << "Geben Sie bitte eine Zahl ein: ";
    cin >> n;
    int i={2};
    while (i <= sqrt(n)) { //wenn n=a*b, muss mindestens einer der Faktoren <= sqrt(n) sein
    if (n%i == 0) {
    cout << n << " ist keine Primzahl\n";
    return 0;
    }
    ++i; }
    if (n <= 1) cout << n << " ist keine Primzahl\n"; //Sonderfall 1 und Fehleingaben ausschließen
    else cout << n << " ist eine Primzahl\n";
    return 0;
    }

    // ???? Das ist ein Programm aus einer Uni-Übung. Verstehe nicht ganz wofür hier die Quadratwurzel verwendet wird. Dass Primzahlen keine Quadratwurzelzahlen sein können ist ja klar (weil sie nicht einmal gerade sind), aber warum muss einer der Faktoren für die eingegeben Zahl eine Quadratwurzelzahl sein?

    Danke für die Hilfe!



  • Hi,

    Es gilt n/sqrt(n) == sqrt(n).

    Bei jeder größeren, natürlichen Zahl x (also x > sqrt(n)), die ein Teiler von n ist gilt

    n/x < sqrt(n)

    das heißt man hätte schon das Teilungsergebnis n/x als Teiler von n gefunden und damit festgetellt, daß n KEINE Primzahl ist.

    Deshalb genügt es für den Primzahlentest all natürlichen Zahlen <= sqrt(n) zu untersuchen.

    VG Martin



  • Bagration1 schrieb:

    Dass Primzahlen keine Quadratwurzelzahlen sein können ist ja klar (weil sie nicht einmal gerade sind)

    Ich weiß nicht genau, was Du mit 'Quadratwurzelzahl' meinst, aber sowohl die ganzzahlige Wurzel aus einer Zahl als auch das Quadrat einer Zahl können durchaus ungerade sein: 9, 25, 49 ...



  • Belli schrieb:

    Bagration1 schrieb:

    Dass Primzahlen keine Quadratwurzelzahlen sein können ist ja klar (weil sie nicht einmal gerade sind)

    Ich weiß nicht genau, was Du mit 'Quadratwurzelzahl' meinst, aber sowohl die ganzzahlige Wurzel aus einer Zahl als auch das Quadrat einer Zahl können durchaus ungerade sein: 9, 25, 49 ...

    eine primzahl x ist nur durch 1 und sich selbst teilbar, nicht durch sqrt(x). ist das so schwer?



  • Was hat das mit Bellis Aussage zu tun?

    Gar nichts? Richtig!

    Ist das so schwer?



  • Bagration1 schrieb:

    Das ist ein Programm aus einer Uni-Übung. Verstehe nicht ganz wofür hier die Quadratwurzel verwendet wird.

    Ich versteh hier auch was nicht:
    1.: Wie kann man, wenn man an einer Uni ist, DAS nicht verstehen?!
    2.: Total falsche Baustelle, du bist hier in einem Programmierforum! Gut programmieren kannst du auch nicht, aber dein Problem hierbei ist, du kannst kein Mathe!
    3.: Das ist eine absolute evergreen-Einsteigeraufgabe zu der es 1 Millarde Lösungsvorschläge (mit solider Erklärung) gibt. Hast du überhaupt mal in Erwägung gezogen dir die Lösung selber zu Erarbeiten und zu verstehen?!



  • SeiKeinDummiGehZurUni schrieb:

    Bagration1 schrieb:

    Das ist ein Programm aus einer Uni-Übung. Verstehe nicht ganz wofür hier die Quadratwurzel verwendet wird.

    Ich versteh hier auch was nicht:
    1.: Wie kann man, wenn man an einer Uni ist, DAS nicht verstehen?!

    Möglicherweise ist die Schlussfolgerung, wer hier eine Uni-Aufgabe postet, ist auch Student an einer Uni, falsch.



  • SeiKeinDummiGehZurUni schrieb:

    3.: Das ist eine absolute evergreen-Einsteigeraufgabe zu der es 1 Millarde Lösungsvorschläge (mit solider Erklärung) gibt. Hast du überhaupt mal in Erwägung gezogen dir die Lösung selber zu Erarbeiten und zu verstehen?!

    Ja, kann mich noch gut daran erinnern. 1980 BASIC kurs auf dem Gymnasiium. Denke JEDER hat mal so ein Programm geschrieben.

    VG Martin



  • mgaeckler schrieb:

    Hi,

    Es gilt n/sqrt(n) == sqrt(n).

    Bei jeder größeren, natürlichen Zahl x (also x > sqrt(n)), die ein Teiler von n ist gilt

    n/x < sqrt(n)

    das heißt man hätte schon das Teilungsergebnis n/x als Teiler von n gefunden und damit festgetellt, daß n KEINE Primzahl ist.

    Deshalb genügt es für den Primzahlentest all natürlichen Zahlen <= sqrt(n) zu untersuchen.

    VG Martin

    Vielen Dank für deine Hilfe!


Anmelden zum Antworten