C Vollkommene Zahlen - Optimierung

_mclaren_ · 2. November 2008

Hallo Leute!

Folgende Aufgabenstellung

Eine natürliche Zahl n nennt man eine vollkommene Zahl, wenn die Summe ihrer Teiler ̈
ohne die Zahl selbst gleich n ist.

Beispiel: 6 = 1 + 2 + 3

Schreiben Sie ein C-Programm, das alle vollkommenen Zahlen berechnet und ausgibt,
die kleiner oder gleich 1000000 sind.

Das hab ich

Code:

#include <stdio.h>

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

  for(z=2;z<=1000000;z=z+2){ // keine ungerade Vollkomme Zahl, daher +2
    summe = 1; // Teiler 1 gibt es immer
    for(i=2;i<z;i++) {

        if(z%i == 0) {
            summe += i;
        }
        if(summe == z && i==z-1) { // ||i==z-1, notwendig, sonst werden nicht alle echten Teiler beachtet (z.b bei 24)
            printf("%ld\n",z);
            if (summe > z){ // Abbruch wenn Summe zu groß
                i=0;        // Ausweg aus Schleife
            }
        }

    }

  }

  return 0;
}

funktioniert, aber eben zml langsam. Da es bis 1000000 rechnen soll, rechnet er bei mir im oberen Zahlenbereich alles nach und nach vor sich hin.

Ich hab zwar andere Lösungsansätze mit bis zur Wurzlx gesehen, aber nicht verstanden. Vl. weiß ja hier noch jemand etwas, dass ich auch nachvoll ziehn kann, ansonst lass ichs halt so *g*

Danke

Woey · 2. November 2008

hi,

auf die Schnelle würd ich mal behaupten dass es sich um eine "Serie" handelt:

3 = 2+1
6 = 3 +2 +1
12 = 6+3+2+1
24 = 12 +6+3+2+1
usw...

-> immer das Doppelte der vorherigen Zahl!(?) -> Startwert 3 und dann einfach mit bitshift left (x << 1) die nächste Zahl berechnen

_mclaren_ · 2. November 2008

Hallo!

Nein stimmt nicht ganz, denn 24 ist keine Vollkommene Zahl

Eine natürliche Zahl wird vollkommene Zahl (auch perfekte Zahl) genannt, wenn sie genauso groß ist wie die Summe ihrer positiven echten Teiler (d. h. aller Teiler außer sich selbst).

Die ersten 10 vollkommenen Zahlen sind:

1. 6
2. 28
3. 496
4. 8.128
5. 33.550.336
6. 8.589.869.056
7. 137.438.691.328
8. 2.305.843.008.139.952.128
9. 2.658.455.991.569.831.744.654.692.615.953.842.176
10. 191.561.942.608.236.107.294.793.378.084.303.638.130.997.321.548.169.216

bei 24 ist nämlich folgendes

24 hat folgende echte Teiler 1,2,3,4,6,8,12

diese summiert 1+2+3+4+6+8+12 ergibt 36

das fiese hier ist, wenn man nur 1+2+3+4+6+8 (ohne 12) rechnet, bekommt man 24, aber 12 gehört als echter Teiler dazu (daher auch in meinem Quellcode der Kommentar bei der Bedingung)

Schnidi · 2. November 2008

@woey

bei 12 und 24 gibt es weitere Teiler. (4 und 8)

Edit: Da war jemand schneller.

claW. · 2. November 2008

ohne groß zu überlegen (da es schon ziemlich spät ist

) eine wohl nahezu perfekte lösung: http://www.tutorials.de/forum/c-c/177254-perfekte-zahlen-berechnen.html

ignorier es einfach, wenn du es nicht sehen und selbst auf die lösung kommen willst.

vllt mal die ausgabe:

8128 is a perect number!
496 is a perect number!
28 is a perect number!
6 is a perect number!

Process returned 0 (0x0) execution time : 12.016 s
Press any key to continue.

Woey · 2. November 2008

ok - hab mich mal wikipedia umgeschaut:

da du ja nur die ersten vier vollkommenen Zahlen berechnen sollst, kannst du ja die Formel
((2^(n -1))*((2^n) - 1) verwenden und die jeweiligen Ergebnisse auf ihre richtigkeit analysieren

_mclaren_ · 2. November 2008

Woey schrieb:
ok - hab mich mal wikipedia umgeschaut:

da du ja nur die ersten vier vollkommenen Zahlen berechnen sollst, kannst du ja die Formel
((2^(n -1))*((2^n) - 1) verwenden und die jeweiligen Ergebnisse auf ihre richtigkeit analysieren

Ich muss nicht die ersten vier berechnen. Ich muss die vollkommenen Zahlen bis 1000000 berechnen. Das ist ein Unterschied. Du hast schon recht, schlussendlich hab ich die ersten vier, aber das weiß ich ja vorher nicht. Ich weiß wie man es berechnet, aber nicht mehr.

Deine Formel ist ja auch erst im Nachhinein entstanden als man die ersten vier Zahlen wusste, Euklid zeigte das es eine Gemeinsamkeit gibt, aber das ist nicht die wahre Berechnung einer vollkommenen Zahl.
Meine eigene Lösung hab ich, nämlich so, wie man es normal händisch rechnen würde, ich wills ja nur noch etwas optimieren.

@claW. schaus mir gleich an, danke

Edit: öhm ja

summe += (((j%i) == 0) ? i : 0);

Was solln das heißn?!
j%i dazurechnen, mmmmh warum? - hach - ich glaub ich muss meinen lassen wie er is... ich kanns halt nur auf die dumme normale, langsame Art *gg*

Woey · 2. November 2008

"ich kanns halt nur auf die dumme normale, langsame Art "

-> Schlau und Schnell währe Multithreading auf einem Multicore-Prozessor

asdfman · 2. November 2008

_mclaren_ schrieb:
Was solln das heißn?!
j%i dazurechnen, mmmmh warum? - hach - ich glaub ich muss meinen lassen wie er is... ich kanns halt nur auf die dumme normale, langsame Art *gg*

Nix mit j%i dazurechnen. Da ist doch ein ternärer Operator drin ;(

_mclaren_ · 2. November 2008

okay - ich glaub ich lass so *g*

ag3nt · 2. November 2008

Also wenn es darum geht das ganze schneller zu berechnen, gibt zumindest für deinen Fall eine eventuell intressante Lösung basierend auf einer der möglichen Formeln

Code:

#include <stdio.h>
#include <math.h>

unsigned long int p (const unsigned long int s) {
	unsigned long int r = 1;

	long int i = 1;
	long int max = sqrt( (double) s);

	while( ++i <= max && r <= s ) {
		if( s % i == 0 ) r += i + s/i;
	}
	
	return r;
}

int main (void) {
	unsigned long int s;
	int i = 2;

	do {
		s = ((1UL<<(i-1)) * ((1UL<<i)-1UL));

		if( p(s) == s ) {			
			printf("%lu\n", s);
		}
		
		i++;
	}
	while(s <= 1000000000000UL);

	return 0;
}

_mclaren_ · 2. November 2008

Danke

Den code hab ich schon mal gesehen, aber ich kanns einfach nicht nachvollziehen, warum man es so machen kann, wie schon erwähnt, warum reicht es wenn man nur bis zur Wurzl rechnet... warum wird zur Summe der nicht nur der Teiler sondern die Zahl x durch den Teiler hinzu addiert
Also es scheitert wohl eher am mathematischen ...

ag3nt · 2. November 2008

Ob du nun die Methode mit der Wurzel verstehst ist für die Geschwindigkeit eigentlich eher unerheblich. Wenn du es mit "deiner Methode" versuchst, wird es zwar langsamer sein aber im Vergleich zu vorher immer noch erheblich schneller. Das liegt einfach daran, dass du einfach jede Menge Zahlen schon im Vorfeld aussschließen kannst, was letztlich die Geschwindigkeit enorm steigert.
Du musst nämlich gerade mal 20 Zahlen (und das ist noch nicht(!) optimiert) bis 1.000.000.000.000 prüfen!

_mclaren_ · 2. November 2008

Es ist nicht unwesentlich. Ich sollt ja begründen können warum ich mein Programm so gemacht habe, wenn ich sag ja weil im inet steht is das etwas dämlich. Wenn ichs versteh und begründen kann, verwend ichs.

ag3nt · 2. November 2008

Wenn es dir darum geht, dann argumentiere, dass Euklid bzw Leonhard Euler beweisen konnte das jede vollkommene Zahl sich in der Form (2^(i-1) ) * ( (2^i) - 1 ) schreiben lässt, wenn ((2^i) - 1) eine Primzahl ist. Das ist dann eine bewiesene mathematische Tatsache die als Begründung ausreicht. Dann brauchst du nicht mal eine Faktorisierung der Zahl durchführen und würdest mit wenigen Befehlen auskommen:

Code:

#include <stdio.h>

#define POWER_2(n) (1ULL<<(n))
#define MERSENNE(k) (POWER_2((k))-1ULL)

int main (void) {

	 //(2^11)-1 is not a prime-number
	int exp[] = { 2, 3, 5, 7, 13, 17, 19, 31 };
	int n;

	for(n=0; n < 8; n++) {
		unsigned long long int s = 
			POWER_2(exp[n]-1) * MERSENNE(exp[n]);
		
		printf("%llu\n", s);
	}

	return 0;
}

mensch183 · 2. November 2008

In deinem Code im 1. Artikel versuchst du als Teiler alle i von 2 bis z-1. Es würde reichen, als mögliche Teiler 2 bis z/2 zu testen.

/edit: mal deins umgeschrieben, wie ich es "aus dem Bauch heraus" machen würde, also ohne schlaue Sätze und vorgegebene Primzahlen.

Code:

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

  for (z=2;z<=100000;z=z+2){ // keine ungerade Vollkomme Zahl, daher +2
    summe = 1; // Teiler 1 gibt es immer
    for (i = 2; i <= z/2; i++) {
      if (z%i) {
        continue;   
      }
      summe += i;
      if (summe > z) {
        break;
      }
    }  
    if (summe == z) {
      printf("%ld\n",z);
    }
  }  
  return 0;
}

_mclaren_ · 4. November 2008

Hallo Leute!
danke @mensch183
_
ich hab nun mitn Lehrer gredet, er wills so guts geht optimiert haben -.-

Das mit der Wurzl als Grenze hat er gmeint solln wir so nehmen.

Nun dacht ich ok, schreib ich das einfach so rein in die for, aber denkste

Code:

#include <stdio.h>
#include <math.h>

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

  for(z=2;z<=1000000;z=z+2){ // Beginn = 2 weil 1 sowieso enthalten || keine ungerade Vollkomme Zahl, daher +2
    summe = 1; // Teiler 1 gibt es immer
    for(i=2;i<=[COLOR="Red"][B]sqrt(z)[/B][/COLOR];i++) {

        if(z%i == 0) {
            summe += i;
        }
        if(summe == z ) { 
            printf("%ld\n",z);
            if (summe > z){ // Abbruch wenn Summe zu groß
                i=0;        // Ausweg aus Schleife
            }
        }
    }
  }
  return 0;
}

Da tut sich nichts mehr -.- Ich weiß allerdings nicht warum

nun hab ich nach Programmen gesucht die es schon haben z.B.:

Code:

#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;
              [B][COLOR="Red"] summe += z/i[/COLOR][/B];    // 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;
}

Die Zählen hier in der inneren Schleife hinab, hat das nen tieferen Grund?
Die fettmakierte Zeile kann ich auch nicht nachvollziehen.
Weiß da jemand etwas?

Danke

hat sich erledigt

mensch183 · 6. November 2008

_mclaren_ schrieb:
Die Zählen hier in der inneren Schleife hinab, hat das nen tieferen Grund?

Die gehen davon aus, daß man so zuerst größere Teiler findet und damit bei den z, die durch summe>z aus dem Suchmuster rausfallen, schneller eine zu große summe erreicht und somit schneller abbrechen kann. Allerdings sucht man bei Abwärtssuche zuerst im dünner mit Teilern besiedelten Bereich der größeren Zahlen.

Beispiel mit z=12:
Die 1 ist immer vorgeben.
Per Aufwärtssuche findest du die Teiler 2,3,4,6 bis du wegen summe>z abbrechen kannst. Dazu waren 5 Tests nötig (i=2 bis 6).
Per Abwärtsssuche findest du 6,4,3 und dann ist summe>z. Dazu waren nur 4 Tests nötig (i=6 runter bis 3). 4 Tests gehen schneller als 5 Tests.

_mclaren_ schrieb:
Die fettmakierte Zeile kann ich auch nicht nachvollziehen.
Weiß da jemand etwas?

Dann hast du auch nicht verstanden, warum es reicht bis zu sqrt(z) statt bis z/2 zu testen.

Wieder Beispiel z=12:
Die 1 ist vorgegeben. Dann testest du i=2. Treffer! summe+=2. Nach dem alten System würdest du nun mit dem Test von i=3 weitermachen. Wenn aber 2 ein Teiler von 12 ist, kannst du durch Berechnung eben dieses Quotienten 12:2=6 mit der 6 gleich noch einen 2. Teiler ermitteln und der Summe per summe+=6 zuschlagen. Genau das passiert in der rot markierten Zeile. Danach würde man i=3 testen und dabei wieder ein Paar Teiler finden (die 3 und die 4 weil 12:3=4). Man findet die Teiler also immer paarweise: erst den kleinesten und den größten, dann den zweitkleinsten und den zweitgrößten usw. Nur deshalb kann man die Suche bei i=sqrt(z) bereits abbrechen, weil man alle größeren Teiler bereits gefunden hat.

Tip: laß dir vom Programm alle z und i anzeigen, die jeweils getestet werden. So findest du leichter Fehler, weil du siehst, was das Programm genau tut. Dafür natürlich nicht bis 100000 sondern nur bis z.B. 10 testen.

_mclaren_ · 6. November 2008

hy . danke!
es sich aber wie oben angemerkt dann eh erübrigt - habs dann durchschaut *g*

C Vollkommene Zahlen - Optimierung

Lieutenant

Ensign

Lieutenant

Ensign

claW.

Gast

Ensign

Lieutenant

Ensign

Commander

Lieutenant

Lieutenant

Lieutenant

Lieutenant

Lieutenant

Lieutenant

Captain

Lieutenant

Captain

Lieutenant

Ähnliche Themen