Primzahl berechnung ; WO sind meine 250.000 $ ?

[dadie]

Hallo ,

Ich habe Heute etwas auf einer webseite gelesen ich Zitiere :

Meine bisherigen Versuche, eine generative Formel für eine Primzahl zu finden und die 250.000 Dollar beim EFF-Wettbewerb zu gewinnen, waren noch nicht erfolgreich.

...

Meines wissens ist doch eine Genetive Formel eine formel bei der man errechnen kann ob die Zahl X eine Primzahl ist.

Nunja ich habe es geschafft ^^ Wo sind meine 250.000 $ ?

Hier meine Lösung :

Code:

   #include <iostream.h> 

  int main(float i,int z,int y,int x,float t,float k,float h,int primzahl)           
  {           
   cout << "Zahlt eingeben" << endl;
   cin>>primzahl;

   for(i=1;i<=primzahl;i=i+1)
   {
      x = 0 ;
      for(z=1;z<=i;z=z+1)
      {
      y = i/z ;
            if (y == i)
            {
            x = x+1 ;     
            } 
               for(t=1;t<=i;t=t+1)
                {
                   k = i/t ;  
                                  for(h=1;h<=i;h=h+1)
                                   {          
                                      if(k == h)   
                                         {
                                          x = x+1 ;       
                                          }
                                   }         
                }
                                  
            //cout << i << " ist die zahl gerade und " << i << " Durch " << z << " Ist gleich " << y << " und X ist gleich " << x << endl;
      };
      if (x == 2*i+1)
      {
               if(i == primzahl)
               {
        cout << "Die Zahlt " << i << " Ist eine Primzahl" << endl; 
               }     

      } 
      
      
   };

                
  }

Wie hättet ihre es gelöst ?

Ist meine Lösung zu rechen intensiv ? Oder Gar total überladen ?

Mfg Dadie

[Rolus]

Hier hatten wir das Thema schon mal. Kannst dir ja mal meinen Code und den vom Ork dort anschauen. Dein Code ist wirklich etwas uneffizient. Wenn man testet, ob A durch B gerade teilbar ist und B² größer oder gleich A ist, dann ist A nicht gerade durch B teilbar. Hm, naja ist jetzt sicher etwas schwer zu verstehen. Ich poste mal meine Alternative zu deinem Programm hier ein:

Code:

#include <iostream.h> 
#include <conio.h>

int main()
{
 int zahl;
 cout << "Zahl eingeben" << endl;
 cin>>zahl;
 
 int tmp = 0;
 int x = 2;         //durch x wird geteilt - durch 1 zu teilen ist sinnfrei
 int y = 0;         // so oft wurde schon ohne rest geteilt 
 while (tmp <= zahl)  // wir muessen nur pruefen, ob tmp kleiner als zahl ist
 {
  if (zahl % x == 0)       // teilbar mit rest 0 ?
  { 
    ++y ;          // wenn ja, erhoehe y
  }
  ++x;             // erhoehe x
  tmp = x * x;   // tmp ist x² - wir muessen nur pruefen, ob tmp kleiner als zahl ist
 }
 if (y < 1)          // y kleiner als 1? also nie ohne rest geteilt ?
 {
  cout << zahl << " ist eine Primzahl" ;   // wenn ja, dann primzahl !
 }
 getch();
 return 0;
}

Ist sogar etwas kürzer. Wenn du etwas daran nicht verstehst einfach nachfragen.

freundliche Grüße, Rolus

[DFYX]

Gut, lass mal sehen...

Erst mal stammt das Zitat wohl von http://www.frank-buss.de/prime/, seh ich das richtig? Ist etwas sehr aus dem Kontext gerissen.

Dann ein bisschen (hoffentlich konstruktive) Kritik:
1. Ich weiß zwar zugegebenermaßen selber nicht, was eine "generative Formel" ist, aber das ist sicher keine. Das ist ein Algorithmus und so was findest du in jedem guten C++ Lehrbuch als Beispielcode. Übrigens ist auf der oben genannten Seite auch ein Link zu einem entsprechenden Algorithmus.

2. Schlechter Einrückstil. Rück nach MöglichkeitGrunsätzlich immer 2 bzw. 4 Leerzeichen weit ein, je nachdem, was dir besser gefällt. Aber bleib bei einem von beidem.

3. Es erscheint keine Ausgabe, wenn die Zahl keine Primzahl ist.

4. Zumindest bei mir ist bei einem Probelauf nach der Eingabe gar keine Ausgabe mehr sichtbar, weil das Fenster sofort geschlossen wird. Schreib ein getchar(); ans Ende. (Wobei das von meinem gcc auch nicht richtig kompiliert wird.)

5. Rechtschreib-/Tipfehler in sehr kurzen Ausgaben. Wenn sichs nur um Code zum Lernen handelt, mag das egal sein, aber wenn du das anderen weitergibst, solltest du wenigstens das Gröbste korrigieren.

6. Nach zwei "}" hast du ein unnötiges Semikolon.

7. Es ist eine SEHR merkwüdige Methode, seine Variablen zu deklarieren, indem man sie als Parameter der Main Funktion hinzufügt.

8. Die beiden Ifs am Schluss lassen sich mit && verbinden.

9. Die Kommentarzeile zwischendrin ist mir nicht ganz klar. Scheint eine Debuginfo zu sein, die ich aber auch nicht wirklich entziffern kann.

Ich hab mir mal die Mühe gemacht und eben diese Fehler ausgebessert:

Code:

#include <iostream.h>

int main()           
{
  float i;
  int z, y, x;
  float t, k, h;
  int primzahl;
             
  cout << "Zahl eingeben" << endl;
  cin>>primzahl;

  for(i=1;i<=primzahl;i=i+1)
  {
    x = 0 ;
    for(z=1;z<=i;z=z+1)
    {
      y = i/z ;
      if (y == i)
      {
        x = x+1 ;     
      }
       
      for(t=1;t<=i;t=t+1)
      {
        k = i/t ;  
        for(h=1;h<=i;h=h+1)
        {          
          if(k == h)   
          {
            x = x+1 ;       
          }
        }         
      }
    }
    
    if (x == 2*i+1 && i == primzahl)
    {
      cout << "Die Zahl " << i << " ist eine Primzahl" << endl;     
    }
  getchar(); 
  }           
}

Trotzdem halte ich den Algorithmus immer noch für alles andere als gut verständlich. Hier mal eine Variante in Form einer Funktion:

Code:

bool ist_primzahl(int zahl)
{
  for(int i = 2; i*i <= zahl; i++)
  {
    if(zahl%i == 0) // lässt sich die Zahl restlos durch i teilen?
      return false;
  }
  return true;
}

Das ganze ist natürlich immer noch nicht komplett optimiert, aber es funktioniert genau so und ist DEUTLICH kürzer und mit Sicherheit auch schneller.

[dadie]

2. Schlechter Einrückstil. Rück nach MöglichkeitGrunsätzlich immer 2 bzw. 4 Leerzeichen weit ein, je nachdem, was dir besser gefällt. Aber bleib bei einem von beidem.

...

oO? Also bisher hat sich nochniemand über meine Einrückung beschwert.

3. Es erscheint keine Ausgabe, wenn die Zahl keine Primzahl ist.

...

Joa habe ich woll vergessen -.-'
bzw.Fand ich nett für wichtig

4. Zumindest bei mir ist bei einem Probelauf nach der Eingabe gar keine Ausgabe mehr sichtbar, weil das Fenster sofort geschlossen wird. Schreib ein getchar(); ans Ende. (Wobei das von meinem gcc auch nicht richtig kompiliert wird.)

...

Ja ^^ ich teste meine Programme immer über CMD darum habe ich das woll vergessen


[Ediere später weiter]

[Lukas]

btw, wenn du dir den Link zu besagtem Contest mal durchgelesen hättest, wüsstest du, dass du die 250.000$ kriegst, wenn du als erster eine Primzahl mit mindestens einer Milliarde Stellen herausfindest. Viel Spaß beim rechnen lassen.