Giuga-Zahlen berechnen

3 Lösungen

#86

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

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von eulerscheZhl (5230 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

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");
		}
	}
}