C# :: Aufgabe #88
2 Lösungen
Gesellige Zahlen finden
Fortgeschrittener - C#
von eulerscheZhl
- 13.02.2015 um 19:56 Uhr
Eine Zahl ist dann vollkommen, wenn sie gleich der Summe ihrer Teiler ist. (Bsp.: die Teiler von 6 sind 1,2,3 und 1+2+3=6)
Es gibt aber auch Zahlenpaare, die jeweils die andere Zahl als Teilersumme besitzen (Bsp.: 220 und 284), befreundete Zahlen.
Dies lässt sich mit den geselligen Zahlen sogar noch steigern: hier ergibt nicht die Teilersumme von zwei Zahlen die jeweils andere, sondern es lässt sich eine Kette aus mehreren Zahlen bilden (Bsp.: 12496, 14288, 15472, 14536, 14264)
Finde alle Gruppen von geselligen Zahlen, bei denen keine eine Obergrenze (z.B. 10^7) übersteigt.
Es gibt aber auch Zahlenpaare, die jeweils die andere Zahl als Teilersumme besitzen (Bsp.: 220 und 284), befreundete Zahlen.
Dies lässt sich mit den geselligen Zahlen sogar noch steigern: hier ergibt nicht die Teilersumme von zwei Zahlen die jeweils andere, sondern es lässt sich eine Kette aus mehreren Zahlen bilden (Bsp.: 12496, 14288, 15472, 14536, 14264)
Finde alle Gruppen von geselligen Zahlen, bei denen keine eine Obergrenze (z.B. 10^7) übersteigt.
Lösungen:
C#-Code
class Program
{
static void Main(string[] args)
{
DateTime start,stop;
Zahlen zahlen = new Zahlen();
for (int i = 1; i <= 7; i++)
{
int max = (int)Math.Round(Math.Pow(10, i));
start = DateTime.Now;
zahlen.search(max);
stop = DateTime.Now;
foreach (int v in zahlen.vollkommeneZahlen)
{
Console.Write(v + " , ");
}
Console.WriteLine();
Console.WriteLine("Vollkommene in(" + max + "): " + (stop - start));
foreach (int[] v in zahlen.befreundeteZahlen)
{
foreach (int vv in v)
{
Console.Write(vv + " , ");
}
Console.WriteLine();
}
Console.WriteLine();
Console.WriteLine("Befreundet in(" + max + "): " + (stop - start));
foreach (int[] v in zahlen.geselligeZahlen)
{
foreach (int vv in v)
{
Console.Write(vv + " , ");
}
Console.WriteLine();
}
Console.WriteLine();
Console.WriteLine("Gesellig in(" + max + "): " + (stop - start));
Console.ReadKey();
}
}
}
class Zahlen
{
private List<int> vollkommenListe;
public int[] vollkommeneZahlen
{
get
{
return vollkommenListe.ToArray();
}
}
private List<int[]> befreundetListe;
public int[][] befreundeteZahlen
{
get
{
return befreundetListe.ToArray();
}
}
private List<int[]> geselligeListe;
public int[][] geselligeZahlen
{
get
{
return geselligeListe.ToArray();
}
}
private static int[] teiler(int zahl)
{
List<int> teilr = new List<int>();
for (int i = 1; i < Math.Sqrt(zahl); i++)
{
if (zahl % i == 0)
{
teilr.Add(i);
if (i != 1) teilr.Add(zahl / i);
}
}
return teilr.ToArray();
}
public void search(int max)
{
vollkommenListe = new List<int>();
befreundetListe = new List<int[]>();
geselligeListe = new List<int[]>();
for (int i = 1; i <= max; i++)
{
if (!vollkommenListe.Contains(i) && !befreundetListe.Exists(x => x.Contains(i)) && !geselligeListe.Exists(x => x.Contains(i)))
{
int[] zahlen = { i };
searching(max, zahlen);
}
if (i % (max / 10000 == 0 ? 1 : max / 10000) == 0)
{
Console.Clear();
Console.Write(((double)i * 100.0 / (double)max).ToString("00.00") + " %");
}
}
Console.WriteLine();
}
private void searching(int max, int[] zahlen)
{
int[] teilr = teiler(zahlen[zahlen.Length - 1]);
int zahl = teilr.Sum();
if (1 > zahl || zahl > max) return;
if (zahlen.Contains(zahl))
{
if (zahlen[0] == zahl)
{
switch (zahlen.Length)
{
case 1:
vollkommenListe.Add(zahlen[0]);
break;
case 2:
befreundetListe.Add(zahlen);
break;
default:
geselligeListe.Add(zahlen);
break;
}
}
return;
}
else
{
int[] neueZahl = { zahl };
int[] neueZahlen = new int[zahlen.Length + 1];
zahlen.CopyTo(neueZahlen, 0);
neueZahl.CopyTo(neueZahlen, zahlen.Length);
searching(max, neueZahlen);
}
}
}
C#-Codeusing System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
namespace trainYourProgrammer
{
class MainClass
{
private static int[] CalcSigma(int limit) { //Summe der Teiler für jede Zahl <= limit
int[] result = new int[limit + 1];
for (int i = 2; i <= limit; i++) {
result [i] = 1;
}
for (int i = 2; i * 2 <= limit; i++) {
for (int j = 2 * i; j <= limit; j += i) {
result [j] += i;
}
}
return result;
}
private static List<List<int>> SocialNumbers(int limit) {
List<List<int>> result = new List<List<int>> ();
int[] sigma = CalcSigma (limit);
for (int i = 2; i <= limit; i++) {
List<int> chain = new List<int> (5);
int tmp = i;
while (tmp > 0 && tmp <= limit && !chain.Contains(tmp)) {
chain.Add (tmp);
tmp = sigma [tmp];
}
if (chain.Count > 2 && tmp == chain [0]) { //mache >2 zu == 2 für befreundete Zahlen bzw. == 1 für vollkommene Zahlen
result.Add (chain);
}
if (tmp == chain [0] || tmp == 0 || tmp > limit) {
foreach (int j in chain) { //eine Zahl kann nicht in 2 verschiedenen Ketten vorkommen
sigma [j] = 0;
}
}
}
return result;
}
public static void Main(string[] args) {
const int limit = (int)1e7;
Stopwatch sw = Stopwatch.StartNew ();
List<List<int>> numbers = SocialNumbers (limit);
foreach (List<int> chain in numbers) {
Console.WriteLine (String.Join (", ", chain));
}
sw.Stop ();
Console.WriteLine ("\nbenötigte Zeit: " + sw.ElapsedMilliseconds/1000.0 + " s");
}
}
}