# Abundante Zahlen



## cs1305 (19. Jul 2017)

Hallo Leute,

ich studiere Wirtschaftsingenieurwesen und schreibe in der kommenden Woche eine Wiinfo Klausur. Bei der letzten Altklausur sollten wir im Java Teil ein kleines Programm schreiben. Da keine Lösung raus gegeben wurde und ich selbst nicht auf ein funktionierendes Programm komme wollte ich euch um Hilfe bitten.

Und zwar geht es um eine mathematische Eigenschaft :

Eine natürliche *Zahl* heißt *abundant* (lat. abundans „überladen“), wenn ihre echte Teilersumme (die Summe aller Teiler ohne die *Zahl* selbst) größer ist als die *Zahl*selbst. 

Bei der Zahl 12 wären die Teiler 6,4,3,2,1 und damit in der Summe größer als die Zahl selbst. 

Die Aufgabenstellung war: Schreibe ein Programm, dass alle Zahlen von 1-100 darauf prüft, ob sie abundant sind oder nicht. Alle abundanten Zahlen, als auch alle nicht abundanten Zahlen sollten mit einem Text auf der Konsole ausgegeben werden.

Habt ihr Ideen ? 

Wäre euch total dankbar.


----------



## Joose (19. Jul 2017)

Wo genau liegt dein Problem? Bei der Überprüfung ob eine Zahl abundant ist? 
Wie würdest du es denn mit Zettel+Stift machen?

Schreibe eine Methode welche prüft ob eine Zahl "abundant" ist, in der main-Methode musst du nur noch eine Schleife schreiben welche die Methode aufruft und dir entsprechende Ergebnisse liefert (welche du dann ausgibst).


----------



## tommysenf (19. Jul 2017)

```
public class Abundanz
{
  public static void main(String[] args)
  {

    for (int i=1; i <= 100; i++) {
       System.out.println(i + " " +  istAbundant(i));
    }
  }
 
  static int berechneTeilerSumme(int a) {
 
       int summe = 0;
       for (int teiler=1; teiler < a; teiler++) {
         if (a % teiler == 0) {
           summe += teiler;
         }
       }
       return summe;
  }
 
  static boolean istAbundant(int i) {
      return berechneTeilerSumme(i) > i;
  }
 
}
```


----------



## Xyz1 (19. Jul 2017)

Wieso hier Lösungen ohne Eigenleistung?
Beitrag am Besten wieder entfernen.


----------



## Xyz1 (20. Jul 2017)

Mach mal einen Wettbewerb draus.
Ich habe mir das hier durchgelesen:
https://ktrobotics.wordpress.com/2015/09/06/java-example-finding-abundant-numbers/
https://stackoverflow.com/questions/8647059/finding-factors-of-a-given-integer
und
https://de.wikipedia.org/wiki/Abundante_Zahl

Ich bin der Meinung, das sei schnell:

```
static boolean abu(int i) {
        /*
        if (i < 12) {
            return false;
        }
        if (i < 945 && i % 2 != 0) {
            return false;
        }
        */
        int sum = 1;
        for (int j = i / 2; j > 1; j--) {
            if (i % j == 0) {
                sum += j;
                if (sum > i) {
                    return true;
                }
            }
        }
        return false;
    }
```

(Ja, das funktioniert auch mit 0.)

```
for (int j = 0; j < 1511; j++) {
            if (abu(j)) {
                System.out.print(j + ", ");
            }
        }
```

Ausgabe:

```
12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 100, 102, 104, 108, 112, 114, 120, 126, 132, 138, 140, 144, 150, 156, 160, 162, 168, 174, 176, 180, 186, 192, 196, 198, 200, 204, 208, 210, 216, 220, 222, 224, 228, 234, 240, 246, 252, 258, 260, 264, 270, 272, 276, 280, 282, 288, 294, 300, 304, 306, 308, 312, 318, 320, 324, 330, 336, 340, 342, 348, 350, 352, 354, 360, 364, 366, 368, 372, 378, 380, 384, 390, 392, 396, 400, 402, 408, 414, 416, 420, 426, 432, 438, 440, 444, 448, 450, 456, 460, 462, 464, 468, 474, 476, 480, 486, 490, 492, 498, 500, 504, 510, 516, 520, 522, 528, 532, 534, 540, 544, 546, 550, 552, 558, 560, 564, 570, 572, 576, 580, 582, 588, 594, 600, 606, 608, 612, 616, 618, 620, 624, 630, 636, 640, 642, 644, 648, 650, 654, 660, 666, 672, 678, 680, 684, 690, 696, 700, 702, 704, 708, 714, 720, 726, 728, 732, 736, 738, 740, 744, 748, 750, 756, 760, 762, 768, 770, 774, 780, 784, 786, 792, 798, 800, 804, 810, 812, 816, 820, 822, 828, 832, 834, 836, 840, 846, 852, 858, 860, 864, 868, 870, 876, 880, 882, 888, 894, 896, 900, 906, 910, 912, 918, 920, 924, 928, 930, 936, 940, 942, 945, 948, 952, 954, 960, 966, 968, 972, 978, 980, 984, 990, 992, 996, 1000, 1002, 1008, 1014, 1020, 1026, 1032, 1036, 1038, 1040, 1044, 1050, 1056, 1060, 1062, 1064, 1068, 1074, 1080, 1086, 1088, 1092, 1098, 1100, 1104, 1110, 1116, 1120, 1122, 1128, 1134, 1140, 1144, 1146, 1148, 1152, 1158, 1160, 1164, 1170, 1176, 1180, 1182, 1184, 1188, 1190, 1194, 1200, 1204, 1206, 1212, 1216, 1218, 1220, 1224, 1230, 1232, 1236, 1240, 1242, 1248, 1254, 1260, 1266, 1272, 1278, 1280, 1284, 1288, 1290, 1296, 1300, 1302, 1308, 1312, 1314, 1316, 1320, 1326, 1330, 1332, 1338, 1340, 1344, 1350, 1352, 1356, 1360, 1362, 1368, 1372, 1374, 1376, 1380, 1386, 1392, 1398, 1400, 1404, 1408, 1410, 1416, 1420, 1422, 1428, 1430, 1434, 1440, 1446, 1452, 1456, 1458, 1460, 1464, 1470, 1472, 1476, 1480, 1482, 1484, 1488, 1494, 1496, 1500, 1504, 1506
```

*Ich habe aber die Vermutung, es ginge noch schneller? Vorschläge?*

Zudem: Obiger Beitrag sollte nicht unfreundlich sein, aber jetzt en Idee, bei der ich noch etwas lerne.


----------



## cs1305 (21. Jul 2017)

Tausend Dank ! Kann es einigermaßen nachvollziehen .. wäre leider nie selbst drauf gekommen. 

Bei der unteren Lösung prüfst du alle von i/2 abwärts oder ? Und sobald der Rest 0 ist wird es zur Summe dazuaddiert. Ich hätte jetzt irgendwie gedacht man muss einen boolean dazu programmieren..Oder ist der Wert der if Schleife durch das == quasi ein boolean ? Sorry das ich so dumme fragen stelle


----------



## Xyz1 (21. Jul 2017)

cs1305 hat gesagt.:


> Oder ist der Wert der if Schleife durch das == quasi ein boolean


Ja, nicht nur quasi.

Dumme Fragen sind das nicht. Ich bin auch sicher, du lernst etwas dabei. Aber je nachdem wie viel Zeit dir für die Klausur bleibt ist eines der guten Bücher angebracht.

Ich spinne mal ein bisschen rum: Wenn es hundert solche möglichen Aufgaben gibt (habe ich das richtig geschrieben?) und 30 davon drankommen werden, dann hast du jetzt 1/30...

Und zu überheblich klingen will ich auch nicht. Ich denke, bei Wirtschaft bist du mir um einiges Vorraus.


----------



## tommysenf (21. Jul 2017)

DerWissende hat gesagt.:


> Ich habe aber die Vermutung, es ginge noch schneller? Vorschläge?


Natürlich:

```
private static final HashSet<Integer> ABS = new HashSet<>(Arrays.asList(new Integer[] {12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 100}));
 
  public static void main(String[] args)
  {
  
        for (int j = 0; j <=100; j++) {
            if (ABS.contains(j)) {
                System.out.print(j + ", ");
            }
        }
  }
 
  }
```


----------



## Xyz1 (21. Jul 2017)

tommysenf hat gesagt.:


> Natürlich:


Naja, wenn man einen Trecker bestellt und ein Mofa bekommt, wäre das vielleicht richtig. Oder anders: Danach wurde nicht gefragt.

Es kann doch nicht angehen, dass meine Lösung die beste Lösung ist?


----------



## tommysenf (21. Jul 2017)

cs1305 hat gesagt.:


> Schreibe ein Programm, dass alle Zahlen von 1-100 darauf prüft, ob sie abundant sind oder nicht.


Also eigentlich entspricht es meiner Meinung nach genau der Frage. Und eine besser optimierte Variante wird sich schwer finden lassen...


----------



## Xyz1 (21. Jul 2017)

Kann weg. Im Ton vergriffen...


----------



## JStein52 (21. Jul 2017)

tommysenf hat gesagt.:


> Also eigentlich entspricht es meiner Meinung nach genau der Frage


Näh, definitiv nicht. Es gibt nur die Zahlen aus die @DerWissende vorher berechnet hat.


----------



## cs1305 (26. Jul 2017)

Ich muss jetzt mal ganz dumm fragen... ich hab bisher nur mit public void und public int/double etc programmiert. Geht das dann genauso ? Irgendwie kriege ich das nicht hin... Muss ich nicht die Teiler in einer anderen Schleife irgendwie erstellen?


----------



## DrZoidberg (27. Jul 2017)

DerWissende hat gesagt.:


> Es kann doch nicht angehen, dass meine Lösung die beste Lösung ist?


Ein wenig kann man es noch verbessern, wenn man nur bis zur Wurzel der Zahl geht.

```
static boolean abu(int i) {
  int sum = 1;
  for(int j = 2; j*j <= i; j++) {
    if(i % j == 0) {
        sum += j;
        if(j*j < i) sum += i / j;
        if (sum > i) {
            return true;
        }
    }
  }
  return false;
}
```


----------



## Flown (27. Jul 2017)

DrZoidberg hat gesagt.:


> Ein wenig kann man es noch verbessern, wenn man nur bis zur Wurzel der Zahl geht.


Wurzel einmal berechnen anstatt n-mal (j*j) berechnen (das machst du auch 2 mal)


----------



## cs1305 (29. Jul 2017)

geht es auch so :

```
public static void main(String[] args) {
  int intervall =1000;
  int z = 0;
  int sum = 0;
  int sum2 =0;
  for(int c1=2; c1<=intervall; c1++) {      
    for(int c2=1; c2<c1; c2++) {
      z = c1 % c2;
      if (z==0){
        sum2=sum + c2;
        sum= sum2;
      }
    }
    if (c1==sum2){
      System.out.println(c1+" ist eine volkommende zahl");
    }
    if(c1<sum2){
      System.out.println(c1+" ist eine abundante zahl");      
    }
    sum=0;
    sum2=0;              
  }
  System.out.print("ENDE");
  }
}
```


----------



## Xyz1 (30. Jul 2017)

cs1305 hat gesagt.:


> geht es auch so


Das ist wieder eine Zumutung fürs Auge!


----------



## cs1305 (30. Jul 2017)

aber es geht ?


----------



## VfL_Freak (31. Jul 2017)

Moin,


cs1305 hat gesagt.:


> aber es geht ?


Warum probierst Du es nicht einfach mal aus ?? 

VG Klaus


----------



## Xyz1 (31. Jul 2017)

DrZoidberg hat gesagt.:


> Ein wenig kann man es noch verbessern, wenn man nur bis zur Wurzel der Zahl geht


Ich glaube, du hast es etwas verwässert...
Sicher, dass es funktioniert?
Ich kann die Korrektheit nicht unmittelbar nachvollziehen.
j*j < i wird vielleicht durch i % j == 0 gar nicht erreicht.

Ich meine, dass man bis zur Hälfte der Zahl gehen muss, erscheint klar.
Theoretisch kann eine Zahl auch schon, ohne alle Teiler gesummt zu haben, die Eigenschaft 'abudant' inne haben.

Hast du mal Zeiten gemessen, auch wenn es sich hierbei um Micro-Micro-Optimierungen handelt?

@cs1305 : AFAICCS funktioniert Deines korrekt.
( Fein, ich bin der einzige im Internet, der naben afaics auch afaiccs (...'can'...) schreibt. )


----------



## Meniskusschaden (31. Jul 2017)

DerWissende hat gesagt.:


> j*j < i wird vielleicht durch i % j == 0 gar nicht erreicht.


Hm, AFAICS  ist die Abfrage `j*j < i` auch nur bei `i % j == 0` relevant. Sie hat doch nur den Zweck, den Teiler nicht doppelt zu zählen, falls er die Wurzel der Zahl ist. Man könnte vermutlich ebenso gut `j*j != i` prüfen.


----------



## Meniskusschaden (31. Jul 2017)

Oder (falls du das meinst): Wenn `i % j == 0` nicht gilt, kann die bereits ermittelte Teilersumme nicht größer geworden sein, so dass man auch kein `return true;` verpasst.


----------



## DrZoidberg (2. Aug 2017)

DerWissende hat gesagt.:


> Ich glaube, du hast es etwas verwässert...
> Sicher, dass es funktioniert?
> Ich kann die Korrektheit nicht unmittelbar nachvollziehen.
> j*j < i wird vielleicht durch i % j == 0 gar nicht erreicht.


Natürlich funktioniert das. Kannst du mir eine positive Zahl nennen für die meine Methode fehlschlägt?



DerWissende hat gesagt.:


> Hast du mal Zeiten gemessen, auch wenn es sich hierbei um Micro-Micro-Optimierungen handelt?



Ja, hab ich.

```
public class Test {
  static boolean abu(int i) {
    int sum = 1;
    for (int j = i / 2; j > 1; j--) {
        if (i % j == 0) {
            sum += j;
            if (sum > i) {
                return true;
            }
        }
    }
    return false;
  }

  static boolean abu2(int i) {
    int sum = 1;
    for(int j = 2; j*j <= i; j++) {
      if(i % j == 0) {
          sum += j;
          if(j*j < i) sum += i / j;
          if (sum > i) {
              return true;
          }
      }
    }
    return false;
  }

  public static void main(String[] args) {
    long start = System.nanoTime();
    int count = 0;
    for (int j = 0; j < 100000; j++) {
      if (abu2(j)) count++;
    }
    long end = System.nanoTime();
    double time = (end - start)/1e6;
    System.out.println(count);
    System.out.println(time + "ms");

    start = System.nanoTime();
    count = 0;
    for (int j = 0; j < 100000; j++) {
      if (abu(j)) count++;
    }
    end = System.nanoTime();
    time = (end - start)/1e6;
    System.out.println(count);
    System.out.println(time + "ms");
  }
}
```

Ergebnis:

```
24794
60.611974ms
24794
8042.034928ms
```

Je grösser die Zahl, desto grösser der Unterschied in der Laufzeit. Wenn man alle Zahlen von 0 bis 100.000 durchgeht, hat man schon einen Faktor von mehr als 100.


----------

