3. Primzahl berechnen?

Primzahl berechnen?

  • X

    Bevor du wild drauflosporgrammierst, versuch doch erstmal zu erklären wie genau dein Programm überprüfen soll, ob eine Zahl eine Primzahl ist.

    Erst wenn du es selbst GENAU verstanden hast, kannst du es auch dem Computer mitteilen, was er machen soll.

    Versuchs mal!

    0
  • ?

    Ich habe das selbe Prog zu schreiben und weiss bis jetzt garnicht wie ich da rangehen soll also hier mal die Aufgabe:
    Ich soll ein Programm schreiben welches mir sagt ob die eigegebene Zahl "z" eine Primzahl ist oder nicht.
    Aber wie soll ich da ran gehen ???
    Ich hatte nur eine Idee aber ich weiss nicht ob die läuft ??
    Also man lässt die Zahl einlesen und dann kommt ein Zähler der die Zahlen von 0-10 zählt und jeweils die Eingegebene Zahl dadurch teilt. und dann muss es gucken obs passt oder nicht....
    Aber irgendwas sagt mir das das viel zu kompliziert ist.

    Ps. Bräuchte bis Donnerstag abend hilfe.

    0
  • E

    Gasr schrieb:

    Aber wie soll ich da ran gehen ???
    Ich hatte nur eine Idee aber ich weiss nicht ob die läuft ??

    Dann fang halt mal an deine Idee in ein Programm umzusetzten, dann siehst du ja ob die Idee läuft, und dann kannst du immer noch fragen wie du weiter kommst.

    0
  • H

    @Gasr

    das ist eine möglichkeit, wobei die frage ist, wieso Dur nur von 0-10 überprüfst.
    keine zahl ist durch 0 teilbar, dafür jede zahl durch 1 teilbar, d.h. es gäbe bei Dir keine primzahlen.
    143 =11*13 und somit keine primzahl, würde also als primzahl erkannt, wenn man nur von 2-10 testen würde.

    wie wärs mit von 2-142 zu testen? und wenn das klappt, kannst Du mal drüber nachdenken, ob es evtl sogar reichen würde, bis wurzel(143) zu überprüfen.

    frohes schaffen

    0
  • U

    Hallo Gasr
    Der Einfache Trik dabei ist, dass eine Primzahl genau durch zwei Zahlen teilbar ist, durch 1 und sich selbst. Dies kann man dann in einer Funktion mit einer Modularteilung testen. Das Programm überprüft alle Zahlen von einer Startzahl bis Max.4,294,967,295, ob Sie Primzahlen sind und gibt die Primzahlen danach am Bildschirm aus.

    // Include-Anweisung
#include <iostream.h>

// Funktion: Überprüft, durch wie viele Zahlen eine Zahl teilbar ist

int Teiler(unsigned long int ZuTesten); 

int Teiler(unsigned long int ZuTesten)
{
	unsigned long int Difident=1;  // Programm difidiert die zu testende Zahl durch diese  
	int Moeglichkeiten = 0; // Durch so viele Zahlen ist die zu testende Zahl teilbar

	while(Difident<=ZuTesten)
	{
		if((ZuTesten % Difident) == 0)
		{
			Moeglichkeiten++;
			if (Moeglichkeiten == 3) // Primzahl hat nur 2 Moeglichkeiten.=> Zahl keine Primzahl
			{
				break;
			}
		}
		Difident++; // Ansonst nächste Zahl checken
	}
	return Moeglichkeiten;
}

int main()
{

	unsigned long int zurzeitTesten;
	int Rueckgabewert;
	cout << "Programm zum Ermitteln von Primzahlen\n";
	cout << "Mit welcher Zahl soll gestartet werden? ";
	cin >> zurzeitTesten;
	cout << "\n\n";
	// Die for-Schleife prüft von der Startzahl bis zur Maximalzahl alle Zahlen.
	for (; zurzeitTesten < /*Max: 4,294,967,295*/ 10000;zurzeitTesten++) // Hier maximale Begrenzung ändern
	{
		Rueckgabewert=Teiler(zurzeitTesten);
		switch(Rueckgabewert)
		{
			case 0: break;
			case 1: break;
			case 2: cout << zurzeitTesten << endl; break; // Diese Zahl ist eine Primzahl
			case 3: break;
			default: cout << "Fehler";
		}
	}

	return 0;
}
    0
  • U

    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;

}
    0
  • P

    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.

    0
  • M

    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. 🙂

    0
  • M

    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.

    0
  • M

    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. 🙂

    0
  • M

    Kein Problem. 🙂

    0
  • W

    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;
}
    0
  • L

    -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..

    0
  • C

    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;
    0
  • ?

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

    0
Anmelden zum Antworten