Primzahlausgabe in C++

Hi |

Das Problem liegt im Algorithmus.

In deinem innersten IF-Zweig prüfst du, ob die aktuelle Zahl bei der Division durch sich selbst oder einen iterierten Divisor Rest Null ergibt.

Nun wissen wir von Primzahlen, dass sie nur durch 1 und sich selbst ohne Rest teilbar sind.

Demzufolge ist die Bedingung der IF-Klausel nicht zureichend, um eine Primzahl eindeutig zu bestimmen.

Beispiel:

zahl = 8
divident (schreibt sich übrigens dividend *g*) = 4

Ergibt bei
zahl / zahl = 1 REST 0
und bei
zahl / dividend = 2 REST 0

Bedingung erfüllt, aber 8 ist keine Primzahl.

Schau dir mal das hier an

greez
JoSsiF

Naja ok,aber wenn es allein am Allgorithmus liegt (desse Fehler ist nun auch erkenne  ) dann müssten er also mir die NICHT Primzahlen ausgeben,was er meiner Ansicht auch tut,aber warum öfters hinterenander.
Die Ausgabe schaut so aus:

Die Primzahl:4
Die Primzahl:6
Die Primzahl:6
Die Primzahl:8
Die Primzahl:8
Die Primzahl:9
Die Primzahl:10
Die Primzahl:10
Die Primzahl:12
Die Primzahl:12
Die Primzahl:12
Die Primzahl:12
.............

Beispiel:

zahl = 6

dividend = 2 --> Bedingung erfüllt
dividend = 3 --> Bedingung erfüllt

--> 2x Ausgabe "6"

Ach ja. Logisch. Stelle mich bisschen blöd an. Sorry. Aber wie könnte ich denn nun das Gegenteil erreichen,dass nur die Primzahlen angezeigt werden, die Primzahlen sind bzw. in diesem Beispiel, die eben bei der Modula Berechnung ungleich 0 sind.

Theoretisch müsstest du die Modulo-Division für alle Zahlen <=zahl ausführen, und nur bei zahl%1 sowie zahl%zahl darf 0 rauskommen, alle anderen Ergebnisse müssen >0 sein. Dann ist es eine Primzahl.

Das ist aber unheimlich rechenaufwändig. Darum gibt's ja unterschiedliche Algorithmen dafür. Mal den Link angeschaut?

greez
JoSsiF

Ja schon,aber der liefert ja nicht wirklich eine Lösung,aber das macht nichts. Ich sollte nämlich so einen Quellcode bereits irgendwo auf einer meiner vielen Cds haben,da ich das ganze schon mal gemacht ,nur heute es eben in der Arbeit ausprobieren wollte ,da ich wenig zu tun habe 

Wenig zu tun? Och, ich hätte da was für dich

Ja??     

Hier ist sonst auch noch ein Quellcode:

#include <stdio.h>
#include <math.h>
#define MAXMAX 2147483647
#define MAX 46341 //sqrt(MAXMAX)

int main()
{
long int z[MAX], iz, i, i2, j, k, max2;
bool sw;
/* in z[] werden die gefundenen Primzahlen
    gespeichert. Jede weitere Zahl kann
    nur dann eine Primzahl sein, wenn sie
    sich durch eine der gefundenen Primzah-
    len teilen läßt. Diese Prüfung braucht
    aber nur bis zur Wurzel der aktuell
    zu prüfenden Zahl i durchgeführt werden.
   i=aktuell auf Primzahl zu prüfende Zahl
   j=Index(z) für Primzahlprüfung
   k=aktuelle Primzahl für Prüfung mit i
*/
/* neu (23.5.2005): Es werden die Primzahlen
   bis zu MAXMAX errechnet, aber nur bis MAX
   zwischengespeichert.
*/
iz=2;
z[1]=2;
z[2]=3;
printf ("2,3");

for (i=3; i<MAXMAX ; i=i+2)
{
   k=z[1];
   i2=(long) sqrt((float)(i));
   sw=false;
/* Prüfe, ob i durch bisherige Primzahlen
             bis max. sqrt(i) teilbar ist */

   for (j=1; k<=i2 ; j++, k=z[j])
   {
      sw=true;
      if (i/k*k==i)
      {
          sw=false;
          break;
      };
   };
   if (sw)
   {
      iz++;
      if (iz<=MAX) z[iz]=i;
      if (i>2140000000) printf (",%d",i);
   };   
};
printf ("\nAnzahl=%d \n", iz);
return 0;
}