Primzahlen

karl05

Hallo!

Ich habe da ein Problem.
Ich will rausbekommen ob in einer while-Schleife, die eine Zahl hochzählt, diese Zahl eine Primzahl ist. Da bekomme ich trotzdem falsche Ergebnisse bei meiner selbstprogrammierten Schleife, die dies macht.

Wüsste einer wie das so lösen wäre? Vllt. ein neuer Ansatz?

FireFlow

Villeicht mal deine Schleife zeigen, dann kann man dir sagen was falsch ist und du hast den größten Lerneffekt. Ansonsten Google -> Primzahltest.

Gruß

SideWinder

Eine while-Schleife die eine Zahl hochzählt klingt nach einer for-Schleife:

for(int i = 0; Abbruchsbedingung; ++i)
{
    // Hier auf Primzahl testen
    if(isPrim(i)) cout << i << " ist eine Primzahl";
}

isPrim() ist eine Funktion von dir die eben irgendwie testet obs eine Primzahl ist (Einfachster Weg: Durch alle Zahlen vor der Zahl % ausführeun und auf == 0 prüfen).

Wenn die Schleife für den Algorithmus gebaut wurde zeigst du uns vielleicht besser deine selbstgemachte Version damit wir dir damit helfen können

MfG SideWinder

na denn zeischn doch ma her deinen Ansatz!

karl05

Ok, hier ist er:

while (ende > 0) 
{
  i++; 
  a = i; a++;
  isPrime = 0; isPrime2 = 0;
  for (div=2; isPrime && div < i; div++)
  {
    if (0==i % div)
    {
      isPrime = 0;
    }
  }
  for (div2=2; isPrime2 && div2 < a; div2++)
  {
    if (0==a % div2)
    {
      isPrime2 = 0;
    }
  }
  if (isPrime == 0 && isPrime2 == 0)
  { 
    cout << "P:  " << i <<  endl;  
    continue; 
  }
  //weitere andere Rechenoperationen, wenn keine Primzahl vorhanden ist.

}

niemand

Ein offensichtlicher Fehler ist die falsche Initialisierung von isPrime:

isPrime = 1; isPrime2 = 1;
for (div=2; isPrime && div < i; div++)

Ansonsten läuft Deine Schleife nicht, weil isPrime nicht erfüllt ist.

Pack diesen Teil Deiner Routine in eine Funktion (wie SideWinder es vorgeschlagen hat), dann musst Du sie nicht zweimal hinschreiben. Ausserdem ist bool isPrime netter als so ein int.

Für die while Schleife hast Du keine Abbruchbedingung, aber ich nehme mal an, dass das nicht Dein Problem ist.

karl05

So ich habe das jetzt so verändert:

int ende;
int i = 10, a;
while (ende > 0) {
  i++; 
  a = i; a++;

  if (isPrime(i) == 0 && isPrime(a) == 0)
  { 
    cout << "P:  " << i <<  endl; 
    continue; 
  }
  //hier gehts nur weiter, wenn es NICHT zwei aufeinanderfolgende Primzahlen    gibt
}

int isPrime(int zahl)
{
  int div;
  for (div=2; div < zahl; div++)
  {
    if (0 == zahl % div)
    {
      return 0;
    }
    else if (1 == zahl % div)
    {
      return 1;
    }
  }  
}

Das will immer noch nicht richtig funktionieren. Mit den Variablen i u. a will ich 2 Zahlenwerte habe, die nicht Primzahlen sind, aber wie schon gesagt, a muss i + 1 sein und beide dürfen keine Primzahlen sein. Dann kann erst in der while-Schleife fortgefahren werden(darum die if Abzweigung).

Ich hoffe ihr könnt mir helfen.

niemand

Immer noch keine Code-Tags...

Deine Routine isPrime ist fehlerhaft.

int isPrime(int zahl)
{
  int div;
  for (div=2; div < zahl; div++)
  {
    if (0 == zahl % div)
    {
      return 0;
    }
    else if (1 == zahl % div)
    {
      return 1;
    }
  }
}

Was genau soll das bewirken? In dem Augenblick wo Du eine Zahl gefunden hast,
die Rest 1 ergibt, sagst Du die Zahl ist prim?
Beispiel: zahl = 4; div = 3 -> 4%3 == 1 -> 4 ist Primzahl?

Es ist eine Primzahl, wenn sie sich durch keine (!) Zahl ohne Rest teilen lässt, d.h. Du kannst erst nach Beendigung Deiner Schleife sagen, dass es eine Primzahl ist.

warum soll man denn alle zahlen, die kleiner sind durchprobieren? ab der wurzel kann doch nix mehr kommen, oder? schau mal, ob du was hiermit anfangen kannst:

bool isPrime(unsigned long number)
{
	unsigned long j = 1, limit;

	if (number < 2)
		return false;

	limit = static_cast<unsigned long>(sqrt(number));
	while (j <= limit && number % ++j != 0) ;

	return j > limit;
}

karl05

Danke für eure Hilfe ich habe es jetzt raus. Die Funktion muss natürlich so lauten:

bool isPrime(int zahl)
{
  int div;
  bool e = true;
  for (div=2; e && div < zahl; div++)
  {
    if (0 == zahl % div)
    {
      e = false;
    }
  }
  return e;  
}

ChrisPlusPlus

Informiere Dich mal über das "Sieb des Eratosthenes"