C# :: Aufgabe #86
3 Lösungen
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
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:
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
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#-Codeusing 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");
}
}
}
Nicht schön, aber funktioniert. Das Programm sucht erst für jeden Schleifendurchgang alle Primfaktoren und schaut dann, ob es eine Giuga Zahl ist..
C#-Code
C#-Codeusing 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();
}
}
}
C#-Codeusing 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();
}
}
}