Abundante Zahlen

[cs1305]

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 Zahlselbst.

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]

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]

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]

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

 

[Xyz1]

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]

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]

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]

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]

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]

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]

Kann weg. Im Ton vergriffen...

 

[JStein52]

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]

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]

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]

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]

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]

geht es auch so

Das ist wieder eine Zumutung fürs Auge!

 

[cs1305]

aber es geht ?

 

[VfL_Freak]

Moin,

aber es geht ?

Warum probierst Du es nicht einfach mal aus ??

VG Klaus

 

[Xyz1]

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]

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]

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]

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?

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.