Primzahlen: Was läßt sich verbessern?

Diesen Teil:

Danke für die Hinweise. Ich habe dazu noch ein paar Fragen (wie Anfänger so sind). Doch erst mal das geänderte Programm:

#include <stdio.h>
#define MAX 500000
int main()
{
long int z[MAX], iz, i, i2, j, k, l;
// int sw; ** muss hier jetzt natürlich raus.
/* 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 zum halben Wert 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 */
iz=2;
z[1]=2;
z[2]=3;
printf ("2,3");
/* maximal MAX Primzahlen berechnen */
for (i=1; iz<MAX && i<2147483647 ; i++)
{
   k=z[1];
   i2=i/2;
//   sw=0;  ** muss hier jetzt natürlich auch raus.
/* Prüfe, ob i durch bisherige Primzahlen
                  bis max. i/2 teilbar ist */

  int j = 1;
   bool sw = true; //bool ist als "Schalter" besser
   do
   {
      k = z[j];
      l = i/k;
      if (l*k == i) sw = false;
      j++;
   }
   while((flag)&&(k<=i2));
   if (sw)
   {
      z[++iz]=i;
      printf (",%d",i);
   };  
};
printf ("\nAnzahl=%d \n", iz);
return 0;
}

1) Was ist (flag)? Sollte das (sw) heissen? Bei der Übersetzung bekomme ich folgende Fehlermeldung.

   F:\C\York\main.cpp   In function `int main()':
41  F:\C\York\main.cpp   `flag' undeclared (first use this function)

2) Ist das

  int j = 1;
   bool sw = true; //bool ist als "Schalter" besser

   ausführbar oder reine Definition? Das steht nämlich in der äusseren Schleife und muss dort jedes Mal gesetzt werden.

3) Kann ich dann die Zeilen

     l = i/k;
      if (l*k == i) sw = false;

   auch gleich durch

     if ((int)(i/k)*k == i) sw = false;

   ersetzen? Oder kann ich sogar

     if (i/k*k == i) sw = false;

   schreiben, weil das ja sowieso int ist?

Ich habe auch noch mal über den Algorithms nachgedacht. Ich glaube, ich muss nur bis zur Wurzel von "i" prüfen.

Standardanfängerprimzahlenoptimierung: Alle geraden Zahlen sind keine Primzahlen ;-)

Standardanfängerprimzahlenoptimierung: Alle geraden Zahlen sind keine Primzahlen ;-)

Du hast geschrieben, dass du nur bis zu einer bestimmten Zahl die Primzahlen ermitteln musst, weil die folgenden immer das doppelte oder so ist! Aber eine Primzahl lässt sich nur durch 1 und sich selbst restlos teilen! Deswegen musst du das nochmal überdenken!

Du hast geschrieben, dass du nur bis zu einer bestimmten Zahl die Primzahlen ermitteln musst, weil die folgenden immer das doppelte oder so ist! Aber eine Primzahl lässt sich nur durch 1 und sich selbst restlos teilen! Deswegen musst du das nochmal überdenken!

Du musst nur bis zur Wurzel prüfen, weil:

- Wenn X die zu überprüfende Zahl ist, und X keine Primzahl wäre weil X = y*z und y > sqrt(X) ist, dann ist z < sqrt(X) und wäre schon zuerst geprüft worden.

Du musst nur Primzahlen prüfen weil:

- Ist X die zu prüfende Zahl mit X = y*z und y ist keine Primzahl also y = a*b würde ja auch gelten X = a*(b*z) und a < y und wäre schon geprüft.

Du hast bestimmt Recht.

Ich prüfe bis zur Wurzel, weil es ja egal ist, ob ich 5x7 oder 7x5 prüfe und

ich prüfe nur Primzahlen, weil alle anderen Zahlen sich ja schon durch Primzahlen teilen lassen.

Ist das dasselbe?