C# :: Aufgabe #86

3 Lösungen Lösungen öffentlich

Giuga-Zahlen berechnen

Anfänger - C# von Gustl - 13.02.2015 um 12:42 Uhr
Eine natürliche Zahl n ist eine Giuga-Zahl, wenn alle ihre Primteiler p den Wert n/p - 1 teilen.

Schreibe ein Programm welches alle Giuga-Zahlen bis zu einer festen Obergrenze ausgibt.

Erläuterung zu einer Giuga-Zahl findest du hier: Wikipedia

Lösungen:

vote_ok
von eulerscheZhl (5130 Punkte) - 13.02.2015 um 17:14 Uhr
Zunächst ermittle ich für jede zusammengesetzte Zahl den kleinsten Teiler (Vorgehen wie beim Sieb des Erathostenes, nur mit Speichern des Teilers).
Anschließend gehe ich alle Zahlen bis zu einer bestimmten Grenze durch, iteriere über deren Teiler und prüfe die Bedingung.

Bis zu einer Grenze von 10^8 in 6.4s
Quellcode ausblenden C#-Code
using System;
using System.Diagnostics;

namespace trainYourProgrammer
{
	class MainClass
	{
		private static int[] GetSmallestFactors(int limit) {
			int[] result = new int[limit + 1];
			for (int i = 2; i * i <= limit; i++) {
				if (result [i] == 0) {
					for (int j = 2*i; j <= limit; j+=i) {
						if (result [j] == 0) {
							result [j] = i;
						}
					}
				}
			}
			return result;
		}

		private static bool IsGiuga(int n, int[] primes) {
			int current = n;
			while (primes[current] != 0) {
				if ((n / primes [current] - 1) % primes [current] != 0)
					return false;
				current /= primes [current];
			}
			return n != current && (n / current - 1) % current == 0;
		}

		public static void Main(string[] args) {
			Stopwatch sw = Stopwatch.StartNew ();
			const int limit = (int)1e8;
			int[] primes = GetSmallestFactors (limit);
			for (int i = 1; i <= limit; i++) {
				if (IsGiuga (i, primes)) {
					Console.WriteLine (i);
				}
			}
			sw.Stop ();
			Console.WriteLine ("Rechenzeit: " + sw.ElapsedMilliseconds + " ms");
		}
	}
}
vote_ok
von Robi (390 Punkte) - 06.01.2016 um 09:51 Uhr
Nicht schön, aber funktioniert. Das Programm sucht erst für jeden Schleifendurchgang alle Primfaktoren und schaut dann, ob es eine Giuga Zahl ist..

Quellcode ausblenden C#-Code
using System;
using System.Collections.Generic;

namespace Übungen_Zu_CSharp_86
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Obergrenze eingeben: ");
            long Obergrenze = long.Parse(Console.ReadLine());

            for (double i = 2; i <= Obergrenze; i++)
            {
                int primzahl = 2;
                List<int> primfaktoren = new List<int>();
                double iTemp = i;
                int tempPrimfaktoren = 1;

                do
                {
                    if (iTemp % primzahl == 0)
                    {
                        tempPrimfaktoren = 1;
                        iTemp = iTemp / primzahl;
                        primfaktoren.Add(primzahl);
                        foreach (int item in primfaktoren)
                            tempPrimfaktoren = tempPrimfaktoren * item;
                    }
                    else
                    {
                        while (iTemp % primzahl != 0)
                        {
                            primzahl++;
                        }
                    }
                }
                while (tempPrimfaktoren != i);

                bool GiugaZahl = false;

                foreach (double item in primfaktoren)
                {
                    if ((i / item - 1) == 0)
                    {
                        GiugaZahl = false;
                        break;
                    }
                    else
                    {
                        if ((i / item - 1) % item == 0)
                            GiugaZahl = true;
                        else
                        {
                            GiugaZahl = false;
                            break;
                        }
                    }
                }

                if (GiugaZahl)
                    Console.WriteLine("Giuga Zahl :" + i);
            }
            Console.ReadKey();
        }
    }
}
vote_ok
von stbehl (1550 Punkte) - 22.02.2018 um 14:39 Uhr
Quellcode ausblenden C#-Code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TrainYourProgrammer86
{
    class Program
    {
        static void Main(string[] args)
        {
            bool giuga = false;
            Console.WriteLine("GIUGA ZAHLEN");
            Console.Write("Geben Sie eine Zahl ein, welche überprüft werden soll: ");
            int zahl = Convert.ToInt32(Console.ReadLine());
            int[] primteiler = new int [zahl];
            int teiler = 0;

            int zaehler = 0;
            int zerlegen = zahl;
            for (int i = 2; i <= zahl; i++)
            {
                if (zerlegen % i == 0)
                {
                    zerlegen = zerlegen / i;
                    primteiler[zaehler] = i;
                    zaehler++;
                    i = 2;
                }
            }

            for (int i = 0; i <= primteiler.Length-1; i++)
            {
                if (primteiler[i] != 0)
                {
                    teiler = (zahl / primteiler[i]) - 1;
                    if (teiler % primteiler[i] == 0)
                    {
                        giuga = true;
                    }
                    else
                    {
                        giuga = false;
                        break;
                    }
                }
            }

            if (giuga)
            {
                Console.WriteLine("Die Zahl {0} ist eine Giuga Zahl.", zahl);
            }
            else
            {
                Console.WriteLine("Die Zahl {0} ist keine Giuga Zahl.", zahl);
            }


            Console.ReadKey();
        }
    }
}