3. Primzahlen ermitteln

Primzahlen ermitteln

  • S

    jkhsjdhjs schrieb:

    knivil schrieb:

    Du hast ja immer noch floats drin.

    Wie meinst du das? Ich muss y, x & k durch float definieren, da es sonst nich klappt.

    Nein.

    Und wieso sollte ich das nicht drin haben?

    Weil floats bei 'nem zahlentheoretischen Problem nichts zu suchen haben. Rundungsfehler (wie sie bei float automatisch irgendwann entstehen) sind da katastrophal.

    0
  • J

    Soll ich da dann double oder long double verwenden oder was empfehlt ihr?

    0
  • S

    jkhsjdhjs schrieb:

    Soll ich da dann double oder long double verwenden oder was empfehlt ihr?

    Überhaupt keine Fließkommazahlen. Denn du brauchst keine.

    Daher auch die Devise: Immer sagen was du erreichen willst, nicht womit. Und wo sinnvoll auch das höher gestellte Problem.

    0
  • B

    Der richtige Tipp wurde doch schon längst gegeben (von µ), nur der OP hat ihn ignoriert.

    0
  • J

    Ich muss doch x durch k teilen und in y speichern. Ich muss dann bei y überprüfen, ob es int ist oder nicht. Und wenn x oder k schon int sind, kommt für y immer int raus, auch wenn nur y float ist. Deshalb muss ich die drei Variablen per float definieren. Da x und k sowieso immer nur ganzzahlig sind, macht das denke ich nichts. Und y wird immer neu berechnet.

    Achso, das mit Modulo. Ok, da müsste ich mich noch reinlesen, weiß nicht was das ist.

    0
  • O

    Modulo ist division mit Rest.

    1 % 3 = 1
    2 % 3 = 2
    3 % 3 = 0
    4 % 3 = 1

    Eine Zahl ist genau dann durch eine andere teilbar, wenn die division rest 0 hat und die Zahl selbst nicht 0 ist.

    0
  • K

    Du willst also, dass dein Programm eine nutzerdefinierte Anzahl an Primzahlen findet. Zuerst brauchen wir also eine Funktion, die feststellt, ob eine Zahl eine Primzahl ist. Die Idee ist dabei folgende: Wir pruefen, ob unsere Zahl durch 2, 3, 4, ..., wurzel(Zahl) teilbar ist. Ist die Zahl durch keine dieser Zahlen teilbar, dann haben wir eine Primzahl gefunden. *

    Wie prueft man nun, ob eine Zahl durch eine andere teilbar ist? Das geht mit dem Modulo-Operator, den µ und Otze bereits angesprochen haben. Der gibt naemlich den Rest einer Division zurueck. Und wenn der Rest der Division 0 ist, ist eine Zahl durch die andere teilbar.

    Wir bekommen also:

    bool isPrime(unsigned n)
{
	if(n < 2) // zahlen < 2 sind keine primzahlen
		return false;

	for(unsigned i = 2; i * i <= n; ++i) // fuer alle zahlen 2, 3, ..., wurzel(n) - 1, wurzel(n) ...
		if(n % i == 0) // ... wenn n durch i teilbar ist, ...
			return false; // ... dann haben wir keine primzahl

	return true; // wenn n durch keine der zahlen teilbar ist, dann haben wir eine primzahl gefunden
}

    Jetzt brauchen wir noch den Teil, der den User fragt, wie viele Primzahlen er haben moechte und diese dann ausrechnet.

    int main()
{
	std::cout << "Wie viele Primzahlen?\n";

	unsigned numberOfPrimes;
	std::cin >> numberOfPrimes;

	// count zaehlt die anzahl der primzahlen, die wir schon gefunden haben
	// n zaehlt einfach der reihe nach solange zahlen hoch, bis wir fertig sind
	for(unsigned count = 0, n = 0; count != numberOfPrimes; ++n) // solange wir noch nicht genug primzahlen haben ...
		if(isPrime(n)) // ... wenn die aktuelle zahl eine primzahl ist ...
		{
			std::cout << n << ' '; // ... dann gib die zahl aus ...
			++count; // ... und erhoehe die anzahl gefundener primzahlen um 1
		}
}

    Jetzt setzen wir das ganze noch zusammen und bekommen:

    #include <iostream>

bool isPrime(unsigned n)
{
	if(n < 2) // zahlen < 2 sind keine primzahlen
		return false;

	for(unsigned i = 2; i * i <= n; ++i) // fuer alle zahlen 2, 3, ..., wurzel(n) - 1, wurzel(n) ...
		if(n % i == 0) // ... wenn n durch i teilbar ist, ...
			return false; // ... dann haben wir keine primzahl

	return true; // wenn n durch keine der zahlen teilbar ist, dann haben wir eine primzahl gefunden
}

int main()
{
	std::cout << "Wie viele Primzahlen?\n";

	unsigned numberOfPrimes;
	std::cin >> numberOfPrimes;

	// count zaehlt die anzahl der primzahlen, die wir schon gefunden haben
	// n zaehlt einfach der reihe nach solange zahlen hoch, bis wir fertig sind
	for(unsigned count = 0, n = 0; count != numberOfPrimes; ++n) // solange wir noch nicht genug primzahlen haben ...
		if(isPrime(n)) // ... wenn die aktuelle zahl eine primzahl ist ...
		{
			std::cout << n << ' '; // ... dann gib die zahl aus ...
			++count; // ... und erhoehe die anzahl gefundener primzahlen um 1
		}
}

    http://ideone.com/I5qoPv

    Wenn es Unklarheiten gibt, einfach nachfragen. 🙂

    * Ist natuerlich doof, alle Zahlen durchzugehen. Wem es besser gefaellt, der kann Vielfache von 2 und 3 gleich ueberspringen:

    bool isPrime(unsigned n)
{
	if(n == 2 || n == 3)
		return true;

	if(n < 2 || n % 2 == 0 || n % 3 == 0)
		return false;

	for(unsigned i = 5, delta = 2; i * i <= n; i += delta, delta = 6 - delta)
		if(n % i == 0)
			return false;

	return true;
}

    😉

    0
  • K

    Was fuer eine schule ist das? Und in welchem jahr bist du?

    Greets

    0
  • J

    @Kellerautomat: Danke, ich werds mir heute mal durchlesen und dich nochmal anschreiben wenn ich was nicht verstehe.

    @kamelkacke: ein berufliches Gymnasium, bin in der 12ten

    EDIT: @Kellerautomat: Ja, hab alles verstanden wasdu erklärt hast, werde das Programm noch etwas abändern, da es die Aufgabe war, zuerst alle Primzahlen in einem Array zu speichern und danach auszugeben.
    Danke nochmals 😉

    EDIT2: @Kellerautomat: Habs grad geändert und muss sagen, die Methode geht ja sau schnell. Mein PC (Core 2 Duo @ 3,6GHz) braucht nun nur noch ne halbe Sekunde um alle zu berechnen 😃
    Nur die Ausgabe dauert halt ewig ^^

    EDIT3: Hier das fertige Programm:

    // Aufgabe 3.cpp : Definiert den Einstiegspunkt für die Konsolenanwendung.
//

#include "stdafx.h"
#include <conio.h>
#include <iostream>

using namespace std;

bool isPrime(unsigned n) {
	if(n < 2) { // zahlen < 2 sind keine primzahlen
        return false;
	}

	for(unsigned i = 2; i * i <= n; i++) { // fuer alle zahlen 2, 3, ..., wurzel(n) - 1, wurzel(n) ...
        if(n % i == 0) // ... wenn n durch i teilbar ist, ...
            return false; // ... dann haben wir keine primzahl
	}

    return true; // wenn n durch keine der zahlen teilbar ist, dann haben wir eine primzahl gefunden
}

int _tmain(int argc, _TCHAR* argv[]) {

	int Prim [100000], numberOfPrimes, count;

	cout<<"Dieses Programm ermittelt und gibt Primzahlen aus!";
	cout<<"\n\nBitte geben Sie nun ein, bis zur wie vielten Primzahl ermittelt werden soll (maximal 100.000)!"<<endl;
	cout<<"maximale Primzahl: ";
	cin>>numberOfPrimes;
	cout<<"\nErmittlung laeuft...";

    // count zaehlt die anzahl der primzahlen, die wir schon gefunden haben
    // n zaehlt einfach der reihe nach solange zahlen hoch, bis wir fertig sind
    for(unsigned count = 0, n = 0; count != numberOfPrimes; n++) // solange wir noch nicht genug primzahlen haben ...
		if(isPrime(n)) { // ... wenn die aktuelle zahl eine primzahl ist ...
			Prim [count] = n; //... wird sie im array gespeichert ...
            count++; // ... und die anzahl gefunder primzahlen um 1 erhöht
        }

	for (count = 0; count <= numberOfPrimes - 1; count++) {
		cout<<endl<<count + 1<<". Primzahl: "<<Prim [count];
	}

	cout<<"\n\nDruecken Sie eine beliebige Taste zum Beenden...";
	_getch();

	return 0;
}

    Nur wieso kannst du bei Primzahlermittlung einfach i * i rechnen? Kann man sich dann dennoch 100% sicher sein, dass die Primzahlen stimmen?

    0

  • Hallo,

    es reicht bis zur Wurzel von n, d.h. sqrt(n), zu rechnen~~, da alles, was darüber ist, keine Primzahl von n mehr sein kann (da der Rest-Faktor dann ja kleiner als 2 wäre)~~. Da aber die Wurzelberechnung langsam ist (und man zu Fließkommazahlen bei der Standardfunktion konvertieren müßte), ist es einfacher den Term "i <= sqrt(n)" zu "i * i <= n" umzuformen (denn für positive x und y gilt: wenn "x <= y" dann "x * x <= y * y").

    Man muß aber aufpassen, den Wertebereich bei "i * i" nicht zu überschreiten, d.h. bei 4 Byte Integer dürfte i nur bis max. 65535 (= 2^16 - 1) laufen, damit die Ungleichung stimmt!!!

    Edit: da habe ich gestern abend 2 Sachen durcheinander gebracht (nach der Arbeit sollte man nicht mehr posten 😉
    Ich hatte zuerst die Optimierung auf "i <= n/2" im Kopf und dann erst gemerkt, daß ja schon die Optimierung auf "sqrt(n)" im Code ist.

    0
  • J

    Th69 schrieb:

    Hallo,

    es reicht bis zur Wurzel von n, d.h. sqrt(n), zu rechnen, da alles, was darüber ist, keine Primzahl von n mehr sein kann (da der Rest-Faktor dann ja kleiner als 2 wäre). Da aber die Wurzelberechnung langsam ist (und man zu Fließkommazahlen bei der Standardfunktion konvertieren müßte), ist es einfacher den Term "i <= sqrt(n)" zu "i * i <= n" umzuformen (denn für positive x und y gilt: wenn "x <= y" dann "x * x <= y * y").

    Man muß aber aufpassen, den Wertebereich bei "i * i" nicht zu überschreiten, d.h. bei 4 Byte Integer dürfte i nur bis max. 65535 (= 2^16 - 1) laufen, damit die Ungleichung stimmt!!!

    Ansonsten werden die Primzahlen falsch berechnet und stimmen nicht mehr, oder wie?
    Also ich habe die Primzahlen bis zur 100.000ten Primzahl berechnet (1.299.709) und habe diese und noch ein paar darüberliegende auf einer Internetseite überprüft und die haben alle gestimmt. Und bei 1.000.000 hat i 65535 ja schon längt überschritten. Oder sehe ich das falsch?

    0
  • N

    jkhsjdhjs schrieb:

    Th69 schrieb:

    Hallo,

    es reicht bis zur Wurzel von n, d.h. sqrt(n), zu rechnen, da alles, was darüber ist, keine Primzahl von n mehr sein kann (da der Rest-Faktor dann ja kleiner als 2 wäre). Da aber die Wurzelberechnung langsam ist (und man zu Fließkommazahlen bei der Standardfunktion konvertieren müßte), ist es einfacher den Term "i <= sqrt(n)" zu "i * i <= n" umzuformen (denn für positive x und y gilt: wenn "x <= y" dann "x * x <= y * y").

    Man muß aber aufpassen, den Wertebereich bei "i * i" nicht zu überschreiten, d.h. bei 4 Byte Integer dürfte i nur bis max. 65535 (= 2^16 - 1) laufen, damit die Ungleichung stimmt!!!

    Ansonsten werden die Primzahlen falsch berechnet und stimmen nicht mehr, oder wie?
    Also ich habe die Primzahlen bis zur 100.000ten Primzahl berechnet (1.299.709) und habe diese und noch ein paar darüberliegende auf einer Internetseite überprüft und die haben alle gestimmt. Und bei 1.000.000 hat i 65535 ja schon längt überschritten. Oder sehe ich das falsch?

    Nein, i ist dann ja bei sqrt(1000000) maximal.
    Und wenn ein Überlauf stattfindest merkst du das schon, dein Programm beendet sich nämlich nicht mehr.
    Und warum speicherst du die Primzahlen? Gib sie doch direkt aus?

    0
  • J

    Nathan schrieb:

    jkhsjdhjs schrieb:

    Th69 schrieb:

    Hallo,

    es reicht bis zur Wurzel von n, d.h. sqrt(n), zu rechnen, da alles, was darüber ist, keine Primzahl von n mehr sein kann (da der Rest-Faktor dann ja kleiner als 2 wäre). Da aber die Wurzelberechnung langsam ist (und man zu Fließkommazahlen bei der Standardfunktion konvertieren müßte), ist es einfacher den Term "i <= sqrt(n)" zu "i * i <= n" umzuformen (denn für positive x und y gilt: wenn "x <= y" dann "x * x <= y * y").

    Man muß aber aufpassen, den Wertebereich bei "i * i" nicht zu überschreiten, d.h. bei 4 Byte Integer dürfte i nur bis max. 65535 (= 2^16 - 1) laufen, damit die Ungleichung stimmt!!!

    Ansonsten werden die Primzahlen falsch berechnet und stimmen nicht mehr, oder wie?
    Also ich habe die Primzahlen bis zur 100.000ten Primzahl berechnet (1.299.709) und habe diese und noch ein paar darüberliegende auf einer Internetseite überprüft und die haben alle gestimmt. Und bei 1.000.000 hat i 65535 ja schon längt überschritten. Oder sehe ich das falsch?

    Nein, i ist dann ja bei sqrt(1000000) maximal.
    Und wenn ein Überlauf stattfindest merkst du das schon, dein Programm beendet sich nämlich nicht mehr.
    Und warum speicherst du die Primzahlen? Gib sie doch direkt aus?

    Achso, ok. Na dann ist das ja nicht der Fall.

    Und die Zahlen speicher, weil ich eigentlich für die Schule die Aufgabe mache und wir da grad das Thema Arrays haben und diese Aufgabe dazu machen sollten.
    Eigentlich sollte das Programm auch nur die Primzahlen bis 20 ermitteln, aber ich fand das halt ein bischen öde, da das Programm bei jedem Start immer wieder das selbe macht und keine Benutzereingaben erfordert.

    0
  • ?

    Th69 schrieb:

    es reicht bis zur Wurzel von n, d.h. sqrt(n), zu rechnen, da alles, was darüber ist, keine Primzahl von n mehr sein kann (da der Rest-Faktor dann ja kleiner als 2 wäre).

    Stimmt nicht ganz, das ist nicht die Begründung, um nur bis zur Wurzel zu rechnen. Es gibt auch Primfaktoren größer als die Wurzel und der Restfaktor wird auch nicht kleiner als 2. Gegenbeispiel: 35 = 7*5 , 7 ist größer als sqrt(35)≈5,9 und 5>2.

    jkhsjdhjs schrieb:

    Ansonsten werden die Primzahlen falsch berechnet und stimmen nicht mehr, oder wie?

    Nein, nicht falsch nur unnötig. Bis zur Wurzel von n zu rechnen ist eine Optimierung und beschleunigt die Ausführung ganz erheblich.

    Wir prüfen ja
    if(n % i == 0)
    und hätten in dem Fall einen Teiler i gefunden, können also false zurückgeben weil n damit keine Primzahl ist.

    Wenn es also einen Teiler i gibt, gilt n = i*j für eine andere Zahl j. Ein Teiler i kann selbstverständlich größer als die Wurzel von n sein, aber in dem Fall wäre der andere Faktor j kleiner als die Wurzel. Da wir aufsteigend alle Zahlen in der Schleife prüfen, finden wir stets die kleineren Faktoren zuerst. Der Punkt in dem beide hypothetischen Teiler gleich groß sind ist genau bei der Wurzel(n) erreicht und wir müssen größere Zahlen nicht mehr prüfen: Wären sie Teiler, hätten wir einen anderen, kleineren, Teiler schon vorher entdeckt.

    0

  • Mich wundert es ein wenig, dass noch niemand das Sieb des Eratosthenes erwähnt hat.

    Edit:
    Ah, weil die ersten n Primzahlen gefragt sind, und nicht alle Primzahlen bis n. Ergibt Sinn.

    0
  • M

    DocShoe schrieb:

    Mich wundert es ein wenig, dass noch niemand das Sieb des Eratosthenes erwähnt hat.

    Edit:
    Ah, weil die ersten n Primzahlen gefragt sind, und nicht alle Primzahlen bis n. Ergibt Sinn.

    Man kann das Sieb des Erastothenes auch für die ersten n Primzahlen anwenden, man muss dann halt nur suchen, bis das Array n Elemente enthält, während man sonst bis n alle Promzahlen überprüfen würde.
    Ich hätte das Sieb ja schon erwähnt, aber für die Schule, es scheint ja wirklich um grundlagen und simple Dinge zu gehen, reicht auch die andere Variante, hauptsache er versteht die Lösung auch.

    EDIT: Das overflow-Problem lässt sich doch einfach mit 64-bit-integern umgehen, bzw. so weit verschieben, dass man eh nicht mehr so lange sucht:
    Statt unsigned int benutze unsigned long long oder std::uint64_t

    0
  • S

    Marthog schrieb:

    DocShoe schrieb:

    Mich wundert es ein wenig, dass noch niemand das Sieb des Eratosthenes erwähnt hat.

    Edit:
    Ah, weil die ersten n Primzahlen gefragt sind, und nicht alle Primzahlen bis n. Ergibt Sinn.

    Man kann das Sieb des Erastothenes auch für die ersten n Primzahlen anwenden, man muss dann halt nur suchen, bis das Array n Elemente enthält, während man sonst bis n alle Promzahlen überprüfen würde.

    Und wie weit geht man dann jeweils mit dem Durchstreichen?

    0
  • J

    Ich hab mir das Sieb des Eratosthenes mal angeschaut und verstehe den Algorithmus soweit, ich werde es mal versuchen einzubauen. Danke 😉

    und @µ: Danke für deine ausführliche Antwort, habs kapiert 😉

    0
  • Mod

    SG1 schrieb:

    Und wie weit geht man dann jeweils mit dem Durchstreichen?

    Wir könnten natürlich Zahlentheorie benutzen und wissen, dass die Primzahldichte logarithmisch ist und dann eine sichere obere Grenze abschätzen. Oder wir machen es mit cleveren Algorithmen:

    #include <queue>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int main()
{
  unsigned max_num_primes;
  cout << "Wie viele Primzahlen? ";
  cin >> max_num_primes;

  // Die 2 sparen wir uns mal bei der Rechnung:
  if (max_num_primes > 0)
    {
      cout << "2\t";
      unsigned num_primes_printed = 1;
      unsigned current_number = 3;

      std::priority_queue<pair<unsigned int, unsigned int>,
        vector< pair<unsigned int, unsigned int> >,
        greater< pair<unsigned int, unsigned int> >
        > 
        queue;

      while (num_primes_printed < max_num_primes)
        {
          if (queue.empty() || queue.top().first != current_number)
            {
              cout << current_number << '\t';
              ++num_primes_printed;
              queue.push(make_pair(current_number*current_number, current_number*2));
            }
          else
            {
              for(pair<unsigned int, unsigned int> top = queue.top();
                  top.first == current_number;
                  top=queue.top())
                {
                  queue.pop();
                  queue.push(make_pair(top.first + top.second, top.second));
                }              
            }
          current_number += 2;
        }
      cout << '\n';
    }
}

    (Ich wollte schon immer mal eine priority_queue prakitsch einsetzen 😋 )

    Erklärung:
    http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

    0
  • J

    Also bei mir hat sich herausgestellt, dass ich es nicht hinbekomme mit dem Sieb und wenn dann würde es wieder ellen lang werden. Deshalb hab ich jetzt mal das Programm, welches SeppJ gepostet hat ausprobiert. Doch leider meldet mit Visual C++ 2008 Fehler. Zuerst musste ich noch stdafx.h als Header einfügen, weil Visual C++ einen vorkompilierten Header braucht, aber dann waren da immer noch Fehler in queue.

    1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\queue(160) : error C2529: '_Pred': Verweis auf Verweis ungültig
1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\queue(174) : error C2529: '_Pred': Verweis auf Verweis ungültig
1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\queue(181) : error C2529: '_Pred': Verweis auf Verweis ungültig

    Deshalb bleibe ich besser bei der Methode mit dem Modulo Operator. Aber ich hätte dazu noch eine Frage:
    Kann ich die größe eines Arrays noch irgendwie auf 1.000.000 oder mehr erweitern? Weil wenn ich zum Beispiel die größe auf 500.000 setze, bekomme ich Stack overflow und was mit Für deiesen Bereich ist kein Quellcode verfügbar, noch bevor das Programm startet. Hat da jemand ne Idee bzw. ist das überhaupt möglich?

    0
Anmelden zum Antworten