4. vollkommene zahlen berechnen

vollkommene zahlen berechnen

  • M

    Bsp.: 28 = 1 + 2 + 4 + 7 + 14 ==> vollkommen wenn eine zahl gleich der summe ihrer teiler ist

    mein c-code dazu:

    #include <stdio.h>
#include <conio.h>

int main()
{
 long z,i,summe=0;

 for(z=1;z<=1000000;z++)
 {
  for(i=1;i<z;i++)
  {
   if(z%i == 0) summe += i;
  }
  if(summe == z) printf("%ld\n",z);
  summe=0;
 }

 return 0;
}

    jetzt hab ich das problem das das sehr lange dauert (bei meinem athlon 1800+ hab ich nach 5 min abgebrochen, da war er gerade bei ca. 80 000)

    kann man das effizienter machen?

    mfg

    0
  • V

    for(i=1;i<z;i++)
    if(z%i == 0) summe += i;
    sieht für maich aus wie
    for(i=1;i*i<z;i++)
    if(z%i == 0) {summe += i;summe += z/i;}
    if(z%i == 0) summe += i;

    0
  • M

    Original erstellt von volkard:
    for(i=1;i<z;i++)
    if(z%i == 0) summe += i;
    sieht für maich aus wie
    for(i=1;i*i<z;i++)
    if(z%i == 0) {summe += i;summe += z/i;}
    if(z%i == 0) summe += i;

    steht die letzte zeile bewusst da?

    0
  • M

    also irgendwie geht das gar nicht....mir ist auch der ansatz nicht klar....

    0
  • W

    Original erstellt von mi+chl:
    **```
    for(z=1;z<=1000000;z++)
    {
    for(i=1;i<z;i++)
    {
    if(z%i == 0) summe += i;
    }
    if(summe == z) printf("%ld\n",z);
    summe=0;
    }

    Du könntest in der "i-schleife" prüfen ob die Summe zu gross wird und, falls ja, abbrechen. (Spart man sich unvolkommene Zahlen zu "überbeweisen")

    for(i=1;i<z;i++)
  {
   if(z%i == 0)
     { summe += i;
       if ( summe >z ) i=z;  // oder break; (ich mag break nicht :-) )
     }
  }

    auch glaube ich dass die i-schleife nur bis z/2 suchen muß:
    for(i=1;(i*2)<=z;i++)

    und ich würde von gross nach klein suchen
    for(i=(z+1)/2;i>0; --i) // das z+1 um sicherzugehen,
    // dass auch die hälfte geprüft wird

    allerdings muß dann meine Abbruch mit i=0 geändert werden

    Gruss

    [ Dieser Beitrag wurde am 13.11.2002 um 09:29 Uhr von westhoven editiert. ]

    [ Dieser Beitrag wurde am 13.11.2002 um 09:38 Uhr von westhoven editiert. ]

    0
  • W
     

    #include <stdio.h>
#include <math.h>
int main()
{
  long z,i,summe=1;   // Teiler 1 gibt es immer

  for(z=1;z<=1000000;z++)
    { 
      for(i=sqrt(z);i>1; --i)   // ohne Teiler 1 bis zur Wurzel
        { if( z%i == 0 ) 
             { summe += i;
               summe += z/i;    // jeder Teiler hat seinen "co-Teiler"
               if ( summe >z ) i=0;  // abbruch da Summe zu groß
             }
        }
       if(summe == z) printf("%ld\n",z);
       summe=1;  // Teiler 1 gibt es immer
    }

  return 0;
}

    auf nen 450er Pentium in ca 2 minuten die ganze Mille durchgerechnet
    allerdings nur folgende Zahlen gefunden

    1
6
28
496
8128

    ob des alle sind weiß ich nicht

    0
  • K

    Das sind alle. Aber da musst dir noch viele zeitsparende Dinge einfallen lassen, damit du da viele findest. Die fünfte ist 33 550 336 und die sechste bereits 8 589 869 056 ...

    Edit: Die eins ist übrigens keine vollkommene Zahl, da nur jene vollkommen sind, die gleich der Summe ihrer Teiler ohne die Zahl selbst sind.

    [ Dieser Beitrag wurde am 13.11.2002 um 10:53 Uhr von kwoTx editiert. ]

    0
  • K

    Vielleicht interessiert den ein oder anderen auch das:

    Vollkommene Zahlen sind immer eine Summe aufeinanderfolgender Zahlen ,zB:
    6 = 1+2+3,
    28 = 1+2+3+4+5+6+7,
    496 = 1+2+3+4+5+...+30+31
    8128= 1+2+3+4+5+...+126+127

    Euklid bewies mit Hilfe der geometrischen Reihe:

    Für manche Zahlen n ist p = 1+2+4+8+...+ 2^n = 2^(n+1) -1 eine Primzahl.
    In jedem solchen Fall ist 2^n · p vollkommen.
    6 = 2 * (2²-1)
    28 = 2² * (2³-1)

    Später wurde von Euler bewiesen, dass diese Regel alle geraden, vollkommenen Zahlen liefert - vorausgesetzt man findet die passende Primzahl. Deshalb geht praktisch jeder neue große Primzahlfund mit einer weiteren großen vollkommenen Zahl einher.

    Die Frage, ob es auch ungerade, vollkommene Zahlen gibt, ist bis heute ungeklärt. Im Falle einer Existenz müsste dieser aber größer als 10^100 sein und mindestens 11 verschiedene Primteiler besitzen.

    [ Dieser Beitrag wurde am 13.11.2002 um 11:13 Uhr von kwoTx editiert. ]

    0
  • V

    Original erstellt von mi+chl:
    steht die letzte zeile bewusst da?

    Ja.
    Oben addiere ich die paarigen Teiler.
    also für 36 mach ich da
    2 18
    3 12
    4 9
    und unten mach ich nochmal die 6
    und die 1 hab ich ganz vergessen.

    ja, wenn jede vollkommene zahl ne dreieckszahl sein muß, dann hat man da ja noch nen feinen beschleuniger.

    0
  • M

    wenn ich bis z/2 untersuchen will wieso hab ich dann auch als abbruch bedingung nicht > oder < z/2 sondern wurzel z bzw. i quadrat?

    0
  • V

    Original erstellt von mi+chl:
    wenn ich bis z/2 untersuchen will wieso hab ich dann auch als abbruch bedingung nicht > oder < z/2 sondern wurzel z bzw. i quadrat?

    weil sqrt(z) bereits reicht.
    z/2 wäre zeitverschwendung.

    für jeden teiler i mit z%i==0 wird der Gegenteiler g=z%i auch z%g==0 erfüllen. deswegen braucht man nur bis zur wurzel zu gehen, da wäre i==g. Ansonsten ist immer einer kleiner und einer größer als die Wurzel.

    0
Anmelden zum Antworten