Primzahl berechnen?

Ullrich M

Zu deinem Problem
Ich habe schnell ein kleines Programm geschrieben. Ich glaube, es sollte passen.

#include <iostream.h>

int main()
{
	int z; // Ist diese Zahl eine Primzahl?
	int a=0; // Durch so viele Zahlen ist z teilbar
	cout << "Z: ";
	cin >> z;
	for(int i=1;i<=z;i++) // i wird immer um 1 erhöt. Dabei wird überprüft, ob z%i==0. Wenn ja, dann wird a um eins erhöt.
	{
		if(z%i==0)
			a++;
	}

	if (a==2)
		cout << "Zahl ist eine Primzahl\n";
	else
		cout << "Zahl ist keine Primzahl\n";
	return 0;

}

Piioo

schneller waere es, wenn die Schleife abbrechen wuerde nachdem ein Teiler gefunden wurde und es wuerde schon reichen, wenn i bis maximal z/2 laufen wuerde. Bin sogar sicher, dass es noch weniger sein koennte...

Da 1 immer ein Teiler ist, muss er nicht abgefragt werden, genauso die Zahl selbst.

mantiz

Ich hab's jetzt auch mal auf die Schnelle gemacht, ist mit Sicherheit nicht die beste Lösung, aber sollte ausreichend sein (hoffe ich).
Man braucht nur bis max. Wurzel(z) prüfen, da Wurzel(z) * Wurzel(z) = z ist Wurzel(z) der größte Teiler, den die Zahl außer sich selbst haben kann, desweiteren muss man erst ab 2 prüfen, da 2 abgesehen von der 1 der kleinste Teiler ist, den es gibt. Hier meine Lösung:

#include <iostream>
#include <cmath>

using namespace std;

bool isPrime(int z) {
	if (z < 0) {
		z = -z;
	}
	if (z == 0 || z == 1) {
		return false;
	}
	for (int i = 2; i <= sqrt(z); i++) {
		if (z % i == 0) {
			return false;
		}
	}
	return true;
}

int main(int argc, char* argv[]) {

	int z;

	cout << "Bitte geben Sie eine moegliche Primzahl ein: ";
	cin >> z;

	cout << "\n";
	cout << "Die Zahl " << z << " ist " << (isPrime(z) ? "" : "k") << "eine Primzahl\n";

	return 0;
}

// Edit: Funktion umbenannt, so gefällt's mir besser.

michba

mantiz schrieb:

Man braucht nur bis max. Wurzel(z) prüfen, da Wurzel(z) * Wurzel(z) = z ist Wurzel(z) der größte Teiler, den die Zahl außer sich selbst haben kann, [...]

Naja, es stimmt zwar, dass man nur bis zur Wurzel von z zählen muss, aber die Begründung ist nicht ganz richtig.
Wurzel(z) muss nämlich nicht der größte Teiler der Zahl sein, z.b. bei 16 ist die Wurzel 4 aber es gibt ja auch noch den Teiler 8.
Das Entscheidende ist, dass bei Zahlen größer Wurzel(z) der andere Faktor kleiner Wurzel(z) sein muss, und dieser somit schonmal überprüft wurde.

Außerdem ist es schneller, wenn man in der for-Schleife statt

i <= sqrt(z)

i*i <= z

schreibt. Eine Multiplikation ist nämlich im Gegensatz zu der sqrt-Funktion ziemlich schnell.

mantiz

Oh Herr, gib' Hirn.

Hast natürlich recht, wie konnte ich nur.
Keine Ahnung, was mich da geritten hat.

Die Wurzel hab' ich bei mir rausgeschmissen, Danke für den Hinweis.

michba

Kein Problem.

walljumper

Cool endlich mal ein Thema zu dem ich was beitragen kann.

also Teiler muss man wie schon erwähnt nur bis wurzel(zu_prüfende_zahl) suchen

auserdem kann man nachdem geprüft hat ob die zahl gerade ist alle geraden teiler ebenfalls weglassen.

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

int main()
{
int teiler,zahl;

cin>>zahl;
if(zahl%2==0)
{
 cout<<zahl<<" ist keine Primzahl";
 getchar();
 getchar();
 return 0;
}
for(teiler=3;teiler<=sqrt(zahl)+1;teiler+=2)
 {
 if(zahl%teiler==0)
  {
   cout<<zahl<<" ist keine Primzahl";
   getchar();
   getchar();
   return 0;
  }
 }
cout<<zahl<<" ist eine Primzahl";
getchar();
getchar();
return 0;
}

life

-predator- schrieb:

Außerdem ist es schneller, wenn man in der for-Schleife statt
i <= sqrt(z)
i*i <= z
schreibt. Eine Multiplikation ist nämlich im Gegensatz zu der sqrt-Funktion ziemlich schnell.

dafür muss die Multiplikation bei jedem Schleifendurchlauf durchgeführt werden, während das Wurzelziehn nur einmal vor der Schleife gemacht werden muss..

CStoll

Wenn du es in der Schleifenbdingung schreibst, wird dein Programm trotzdem jede Runde neu die Wurzel berechnen (der Compiler KANN das rausoptimieren, muß aber nicht). Die schnellste Version wäre wohl:

if(z%2==0) return false;
int end=sqrt(z);
for(int i=3;i<=end;++i)
{
  if(z%i==0) return false;
}
return true;

Danke für die antworten konnte das Problem lösen.