Primzahlen herausbekommen!

  • Themenstarter Themenstarter mich_blume
  • Beginndatum Beginndatum
M

mich_blume

Hi an alle,

ich bin neu bei der c++-Programmierung und habe auch gleich eine Aufgabe bekommen, die (zumindest für mich) nich ganz so einfach ist. So soll ich zum Beispiel die x. Primzahl ausgeben. Das x wird vom Benutzer eingeben und daraufhin die Berechnung ausgeführt.
Bisher habe ich an arrays gedacht zum speichern der Werte, aber da man ja die größe des arrays fest bestimmen muss, wiess ich nicht so recht wie das am besten zu gestalten wäre.

Besten Dank schon mal im vorraus

Michael
 
Mit diesem Programm müsste es gehen. Es könnte nur sein das du einige Kleinigkeiten ändern musst. (Funktioiert sicher unter Dev-Cpp 4.9.8.5)

Code: 
#include <iostream.h>
#include <conio.c>

void main()
{
int Zahl=1;
int Counter=0;
int Input, Last_Priem;
bool priem=true;

cout<<"Geben Sie an die wievielte Priemzahl sie wollen : ";
cin>>Input;

while(Counter<Input)
   {
   priem=true;
   for (int j=2;j<Zahl;j++)
      {
      if (Zahl%j==0)
            {
            priem=false;
            j=Zahl;
            }
      else if (Zahl%j!=0)
            {
            priem=true;
            Last_Priem=Zahl;
            }
      }
   if (priem==true)
      {
      Counter++;
      }
   Zahl++;
   }
   
   cout<<"Die "<<Input<<". Priemzahl ist "<<Last_Priem;
   getch();
}
 
Sollte ein bisschen schneller sein:

Code: 
#include <iostream>
using namespace std;

int main()
{
	int iGesucht, iAktuell = 0, iKandidat = 1, iKandidatHalbe, iTeiler;
	bool bIstPrim;

	cout << "Zu ermittelnde Primzahl Nr.: ";
	cin >> iGesucht;

	while (iAktuell < iGesucht) {
		bIstPrim = true;
		++iKandidat;
		iKandidatHalbe = iKandidat >> 1;
		for (iTeiler = 2; iTeiler < iKandidatHalbe; ++iTeiler) {
			if (iKandidat % iTeiler == 0) {
				bIstPrim = false;
				break;
			}
		}
		if (bIstPrim) {
			++iAktuell;
		}
	}

	cout << "Die " << iGesucht << ". Primzahl lautet: " << iKandidat;
	
	return 0;
}
 
PHP: 
	for (iTeiler = 2; iTeiler < iKandidatHalbe; ++iTeiler) {
			if (iKandidat % iTeiler == 0) {
				bIstPrim = false;
				break;
			}
		}
Zum Vergrößern anklicken....

PHP: 
        for (iTeiler = 2; iTeiler * iTeiler < iKandidat; ++iTeiler) {
			if (iKandidat % iTeiler == 0 ) {
				bIstPrim = false;
				break;
			}

Sollte bei großen Zahlen noch schneller gehen;), da man nur bis zur Wurzel der eingegebenen Zahl überprüfen brauch.

Gruß RedWing
 
Nein das denk ich nicht das es ein Streithema ist,
weil dann dein Shifting wegfällt und dafür das mal hinzukommt also nix eingebusst,
ausserdem denk ich ist es besser bei grossen Zahlen nur bis zur Wurzel zu gehen als jedesmal bis zur Hälfte.Und da das ganze quadratische Komplexität hat
ist meine Version schon eine leichte Verbesserung...
Ein Beispiel:
625:
Bei dir musst du alle Teiler bis 312 überprüfen
bei meinem Beispiel brauch ich dies nur bis 25 zu tun....

Solte nur eine konstruktive Kritik sein ;)


MfG

RedWing
 
Zuletzt bearbeitet:
Ich hab's grad mal ausprobiert, deine Methode ist tatsächlich um einiges schneller :)

Ich muss dir allerdings widersprechen, wenn du sagst dass die Berechnung des Produkts ohne Performanzverlust das Shifting ersetzt, denn:
1. wird ein Shifting prozessorintern schneller abgearbeitet (hab das was mit Faktor 3 im Kopf, weiß aber nicht wie aktuell das noch ist)
2. wird bei meiner Methode das Shifting einmal pro Primzahlkandidat durchgeführt, bei dir die Multiplikation jedoch einmal pro Teileruntersuchung jedes Primzahlkandidaten.

Es ist also nur die Tatsache, dass es quadratisch weniger Schleifendurchläufe sind, die dafür verantwortlich ist, dass der Geschwindigkeitsverlust ausgeglichen und sogar in's negative verlagert werden kann.

Ich wusste nur nicht, welche von beiden Einwirkungen überwiegt, deswegen meine Zweifel :)
 
Hallo zusammen!

Ich mische mich ja ungern ein, aber der Algo von Steiner_B ist fehlerhaft!
1. Versucht mal die erste bzw zweite Primzahl zu ermitteln! - Ergebnis: Müll!
Diese Schleife
for (int j=2;j<Zahl;j++)
Zum Vergrößern anklicken....
wird dann nämlich nie durchlaufen, das bedeutet Last_Prim enthält am Ende noch immer den willkürlichen Memorywert, der sich an der Adresse von Last_Prim befindet!
2. Wird nicht die gesuchte, sondern die eine Primzahl vorher zurückgeben: bsp: gibt man 4 an liefert das Programm 5 statt 7 (2,3,5,7,11,13...)! Bei 5 liefert es 7 statt 11!

(Wollte hier niemanden beleidigen, sondern nur etwas richtigstellen!)

Gruß
Johannes
 
Dann ist mein Quellcode allerdings auch fehlerbehaftet.

Bugfix:
Die entsprechende Zeile ersetzen:
Code: 
		for (iTeiler = 2; iTeiler <= iKandidatHalbe; ++iTeiler) {
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück