C# :: Aufgabe #70
14 Lösungen
Finde die erste Zahl die durch alle Zahlen bis 30teilbar ist
Fortgeschrittener - C#
von 96fabi
- 25.09.2014 um 09:01 Uhr
Gesucht wird die erste Zahl, die durch alle Zahlen bis 30 geteilt werden kann(1-30).
Zum Einstieg kann man erstmal die erste Zahl suchen , die durch alle Werte bis 20 geteilt werden kann.
Dieses ist 232792560
Zum Einstieg kann man erstmal die erste Zahl suchen , die durch alle Werte bis 20 geteilt werden kann.
Dieses ist 232792560
Lösungen:
C#-Code
using System;
namespace Teilbar_durch_30
{
class Program
{
static void Main(string[] args)
{
//Einlesen des Divisors
ulong GroeßterDivisor;
Console.WriteLine("Bitte geben Sie die Zahl ein, durch welche & alle darunter liegenden Zahlen \nbis 1 ohne Rest geteilt werden soll, um die erste mögliche Zahl zu finden!");
while (!ulong.TryParse(Console.ReadLine(), out GroeßterDivisor))
{
Console.WriteLine("Bitte eine positive Ganzzahl eingeben!");
}
//Berechnung der Zahl
ulong ErgebnisZahl = GroeßterDivisor;
bool OhneRestTeilbar = false;
bool DurchAlleDivisorenTeilbar = false;
NeueZahl:
while(DurchAlleDivisorenTeilbar == false)
{
for (ulong j = GroeßterDivisor; j >= 1; j--)
{
if (ErgebnisZahl % Convert.ToUInt64(j) == 0)
{
OhneRestTeilbar = true;
}
else
{
ErgebnisZahl+=GroeßterDivisor;
goto NeueZahl;
}
}
if(OhneRestTeilbar==true)
{
DurchAlleDivisorenTeilbar = true;
}
}
//Ausgabe der Zahl
Console.WriteLine("Die gesuchte Zahl ist: " + ErgebnisZahl);
Console.ReadLine();
}
}
}
Mit dynamischer Eingabe und Zeitermittlung für die Dauer der Berechnung
C#-Code
C#-Code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
namespace ErsteDurchAlleZahlenBisNTeilbareZahl
{
class Program
{
static Stopwatch stopuhr;
static void Main(string[] args)
{
Console.WriteLine("Geben Sie die zu berechnende Zahl ein");
Int32 input = Convert.ToInt32(Console.ReadLine());
stopuhr = new Stopwatch();
stopuhr.Start();
Thread thr = new Thread(new ParameterizedThreadStart(Berechnen));
thr.Start(input);
while (thr.IsAlive)
{
Console.WriteLine("Berechnung wird ausgeführ, vergangene Zeit: {0}", stopuhr.Elapsed.ToString("mm\\:ss\\.ff"));
Thread.Sleep(1000);
}
stopuhr.Stop();
Console.ReadKey();
}
static private void Berechnen(object inp)
{
int input = (int)inp;
int[] alleZahlenBisN = new int[input - 2];
for (int i = 0; i < input - 2; i++)
{
alleZahlenBisN[i] = i + 3;
}
long ergebnis = 0;
bool ok = false;
for (long i = input; !ok; i++)
{
bool ok2 = true;
if (i % 2 == 0)
{
for (int j = input; j > 0; j--)
{
if (i % j != 0)
{
ok2 = false;
break;
}
}
if (ok2)
{
ergebnis = i;
break;
}
}
}
Console.WriteLine("Die erste durch alle Zahlen bis {0} teilbare Zahl ist {1}", input, ergebnis);
Console.WriteLine("Die Dauer der Berechnung betrug {0}", stopuhr.Elapsed.ToString("mm\\:ss\\.ff"));
}
}
}
C#-Codeclass Program
{
static void Main(string[] args)
{
int range;
while (true)
{
long result = 1;
Console.Write("Enter the range of the factors(1-x):");
range = IntCheck(Console.ReadLine());
List<int> factors=GetFactors(GetPrimes(range), range);
foreach (int i in factors)
{
result *= i;
}
Console.WriteLine("The smallest number divisible by those factors is:" + result);
Console.ReadLine();
}
}
//überprüft ob eine gültige Integer eingegeben wurde
static int IntCheck(string eingabe)
{
int zahl;
if (Int32.TryParse(eingabe, out zahl))
{
return zahl;
}
else
{
Console.Write("Enter a valid number:");
return IntCheck(Console.ReadLine());
}
}
//gibt uns eine Liste an Primzahlen die wir für die Faktorenzerlegung benötigen
static List<int> GetPrimes(int range)
{
List<int> primes = new List<int>();
bool prime = true;
for (int i = 2; i <= range; i++)
{
for (int x = 2; x < i; x++)
{
if (i % x == 0)
{
prime = false;
break;
}
}
if (prime)
{
primes.Add(i);
}
prime = true;
}
return primes;
}
//gibt uns die Faktoren der auszurechnenden Zahl
static List<int> GetFactors(List<int> primes, int range)
{
List<int> factors = new List<int>();
long nmbr=1;
for (int i = 1; i <= range; i++)
{
foreach (int p in primes)
{
for(int x = 0;x<factors.Count;x++)
{
nmbr*=factors[x];
}
if(nmbr%i==0)
{
nmbr = 1;
break;
}
else if(i%p==0)
{
factors.Add(p);
}
nmbr = 1;
}
}
return factors;
}
}
C#-Codeusing System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace allezahlenbis30
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Geben Sie nun eine beliebige zu berechnende Zahl ein:");
double Zwert = Convert.ToDouble(Console.ReadLine());
Int64 i = 0;
Int64 j = 0;
Int64 k = Convert.ToInt32(Zwert);
Int64 l = Convert.ToInt32(Zwert) - 1;
Int64 m = Convert.ToInt32(Zwert) + 1;
Int64 n = 1;
Int64 Erfolg = 0;
//Array für Alle Zahlen anlegen
Int64[] Zahlen = new Int64[m];
while (i <= l)
{
Zahlen[i] = k;
k--;
i++;
}
i = 1;
k = 1;
l = l - 1;
while (Erfolg <= l)
{
while (n != 0)
{
n = (i * k) % Zahlen[j];
i++;
}
k = (i - 1) * k;
i = 1;
Erfolg = j;
j++;
n = 1;
}
Console.WriteLine(Convert.ToString("Ergebnis: " + k));
Console.ReadLine();
}
}
}
C#-Codeusing System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Number
{
class Program
{
static void Main(string[] args)
{
Console.Write("Geben Sie den größten Divisor ein: ");
ulong maxDiv = ulong.Parse(Console.ReadLine());
Console.Write("Geben Sie den Wert ein ab dem aufsteigend gesucht werden soll: ");
ulong number = ulong.Parse(Console.ReadLine());
bool found = false;
while (!found)
{
Console.WriteLine(number);
for (ulong i = 1; i <= maxDiv; i++)
{
if (number % i != 0)
{
break;
}
if (i == maxDiv && number % i == 0)
{
found = true;
}
}
if (found == true)
{
break;
}
number++;
}
Console.WriteLine("Gesuchte Zahl >>>> " + number);
Console.ReadKey();
}
}
} C#-Code
using System;
namespace _30_divide
{
class Program
{
static void Main(string[] args)
{
Int64 kgv =
((Int64)Math.Pow(2, 4)) * ((Int64)Math.Pow(3, 3)) * ((Int64)Math.Pow(5, 2)) * 7 * 11 * 13 * 17 * 19 * 23 * 29;
Console.WriteLine(kgv);
Console.ReadLine();
}
}
}
Brute-force mit vier paralenen Threads.
Der Nutzer kann die Reichweite der Suche selbst bestimmen, bis 30 dauert allerdings schon recht lange, wenn man die Startwerte zu Testzwecken nicht etwas höher ansetzt. Man sollte evtl. ein Höchstlimit festlegen.
C#-Code
Der Nutzer kann die Reichweite der Suche selbst bestimmen, bis 30 dauert allerdings schon recht lange, wenn man die Startwerte zu Testzwecken nicht etwas höher ansetzt. Man sollte evtl. ein Höchstlimit festlegen.
C#-Code
using System;
using System.Collections.Generic;
namespace durch_1_30_teilbar {
class Program {
static decimal checkpoint = 100000000;
static bool fertig = false;
static int? limit = null;
static void Main(string[] args) {
while (!(limit > 1))
try {
if (limit != null) throw new FormatException();
Console.Write("Teilbar durch 1 - ");
limit = Convert.ToInt32(Console.ReadLine());
}
catch (FormatException) {
Console.WriteLine("Bitte Gannzahl größer als 1 eingeben");
limit = null;
Console.ReadKey(false);
Console.Clear();
}
List<Worker> liste = new List<Worker>();
for (int i = 0; i < 4; i++) {
liste.Add(new Worker((decimal)(limit * i + limit), i + 1, limit));
}//2.329.089.562.800 (1-30)
System.Threading.Tasks.Parallel.ForEach(liste, x => x.DoMath());
Console.ReadKey(false);
}
class Worker {
decimal diezahl;
int id;
int? limit;
public Worker(decimal start, int id, int? limit) {
diezahl = start;
this.id = id;
this.limit = limit;
}
public void DoMath() {
bool found = false;
try {
while (!found) {
found = true;
for (int j = 2; j < limit; j++) {
if (diezahl % j != 0) {
found = false;
break;
}
}
if (diezahl > checkpoint) {
Console.WriteLine(">{0:#,0.0} {1}", checkpoint / 1000000000, "Millarden");
checkpoint = diezahl + 100000000;
}
if (found) break;
diezahl += (decimal)(limit * 4);
found = fertig;
}
}
catch (Exception e) {
found = false;
Console.WriteLine(e.Message.ToString());
}
if (!fertig) {
if (found) {
Console.WriteLine("{0} ist durch 1-{1} teilbar", diezahl, limit);
fertig = true;
}
else
Console.WriteLine("Keine Zahl gefunden");
}
}
}
}
}
Rechnet alles bis zur Zahl 70 in unter einer Sekunde aus. Danach produziert die Decimal-Variable einen System.Overflow.
C#-Code
C#-Code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace TeilbarDurchAlleZahlenBis
{
class Program
{
static decimal Obergrenze = 1;
static decimal ZuTeilendeZahl = 1;
static decimal VorherigeZuTeilendeZahl;
static void Main(string[] args)
{
Console.WriteLine("\nObergrenze" + "Von 1-Obergrenze teilbar".PadLeft(Console.WindowWidth - 20));
Schleife(Obergrenze);
}
static void Schleife(decimal Grenze)
{
DaCapo:
for (decimal i = Obergrenze; i > 1; i--)
{
if (ZuTeilendeZahl % i != 0)
{
goto NaechsteZahl;
}
}
Console.WriteLine("________________________________________________________________________________");
Console.WriteLine(Grenze + "\t" + string.Format("{0:0,0}", ZuTeilendeZahl).PadLeft(Console.WindowWidth - 10));
Obergrenze++;
VorherigeZuTeilendeZahl = ZuTeilendeZahl;
Schleife(Obergrenze);
NaechsteZahl:
try
{
ZuTeilendeZahl = ZuTeilendeZahl + VorherigeZuTeilendeZahl;
goto DaCapo;
}
catch (OverflowException E)
{
Console.WriteLine("\n\n" + E);
Console.ReadLine();
}
}
}
}
Dauert ewig lange, aber gibt das richtige Ergebnis aus.
C#-Code
C#-Codeusing System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace AlleZahlenteilbar
{
class Program
{
static void Main(string[] args)
{
long zahl = 30;
bool valid = false;
while (!valid)
{
long z = zahl;
for (int i = 1; i <= 30; i++)
{
if (z % i != 0)
{
zahl += 30;
break;
}
if (i == 30)
{
valid = true;
}
}
}
Console.WriteLine("Die erste Zahl, die durch alle Zahlen von 1-20 teilbar ist, ist: {0}", zahl);
if (zahl == 232792560)
{
Console.WriteLine("Dein Programm läuft richtig");
}
Console.ReadLine();
}
}
}
C#-Codeusing System;
namespace FindNumberDivisibleUntil
{
internal class Program
{
private static void Main(string[] args)
{
int actualNumber = 1; // kann höher gesetzt werden, falls man mit größerer Zahl beginnen möchte
while (!CheckNumberDivisible(actualNumber))
{
actualNumber++;
Console.WriteLine("actual number: {0}", actualNumber);
}
Console.WriteLine("Die Zahl wurde gefunden! Sie lautet {0}", actualNumber);
Console.ReadLine();
}
private static bool CheckNumberDivisible(int actualNumber)
{
int divisionCounter = 0;
for (int i = 2; i <= 30; i++)
{
if (actualNumber % i == 0)
divisionCounter++;
else
return false;
}
return true;
}
}
}
Mit dynamischer Eingabe, Zeitberechnung und Ausgabe der Anzahl der Ziffern der gefundenen Zahl.
berechnet n = 40000 in < 1s
und n = 100000 in < 5 s
C#-Code
berechnet n = 40000 in < 1s
und n = 100000 in < 5 s
C#-Code
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Diagnostics;
namespace Teilbar30
{
class Program
{
static Stopwatch stop = new Stopwatch();
static void Main(string[] args)
{
Console.WriteLine("Berechnung der kleinsten zahl die durch 1 bis 'n' teilbar ist.");
int input = 0;
while (true)
{
Console.Write("\nBitte 'n' eingeben: ");
try
{
input = Convert.ToInt32(Console.ReadLine());
}
catch
{
Console.WriteLine("Bitte eine Z A H L eingeben!\n");
continue;
}
Berechnen(input);
}
}
static void Berechnen(int input)
{
stop.Start();
BigInteger ergebnis = 1;
List<int> RelevantePrimzahlen = PrimzahlenGenerieren(input);
int[,] PrimzahlenMitExponenten = new int[RelevantePrimzahlen.Count, 2];
for (int i = 0; i < RelevantePrimzahlen.Count; i++)
{
PrimzahlenMitExponenten[i, 0] = (int)RelevantePrimzahlen[i];
}
// Primfaktorzerlegung
for (int i = 2; i <= input; i++)
{
int rest = i;
int teiler = 2;
List<int> PrimzahlenTemp = new List<int>();
while (rest > 1)
{
if (rest % teiler == 0)
{
PrimzahlenTemp.Add(teiler);
rest /= teiler;
continue;
}
teiler++;
}
//Prüfung of die gespeichete Exponentenzahlen kleiner sind als die aktuellen
for (int a1 = 0; a1 < PrimzahlenMitExponenten.GetLength(0); a1++)
{
int Exponent = 0;
int a2 = 0;
while (a2 < PrimzahlenTemp.Count)
{
if (PrimzahlenMitExponenten[a1, 0] == PrimzahlenTemp[a2])
{
Exponent++;
PrimzahlenTemp.RemoveAt(a2);
continue;
}
a2++;
}
if (Exponent > PrimzahlenMitExponenten[a1, 1])
{
PrimzahlenMitExponenten[a1, 1] = Exponent;
}
if (PrimzahlenTemp.Count <= 0)
{
break;
}
}
}
//alle Primfaktoren zusammerrechnen
for (int f = 0; f < PrimzahlenMitExponenten.GetLength(0); f++)
{
for (int e = 0; e < PrimzahlenMitExponenten[f, 1]; e++)
{
ergebnis *= Convert.ToUInt64(PrimzahlenMitExponenten[f, 0]);
}
}
stop.Stop();
Console.WriteLine("{0}\nist von 1 bis {1} teilbar und hat {2} Stellen.\nBerechnet in {3}\n\n"
, ergebnis, grenze, CountDigits(ergebnis), stop.Elapsed);
stop.Reset();
}
static int StellenZaehlen(BigInteger input)
{
int ziffern = 0;
String s = input.ToString();
ziffern = s.Length;
return ziffern;
}
static List<int> PrimzahlenGenerieren(int input)
{
bool teilbar;
List<int> Primzahlen = new List<int>();
Primzahlen.Add(2);
for (int i = 2; i <= input; i++)
{
teilbar = false;
foreach (int x in Primzahlen)
{
if (i % x == 0)
{
teilbar = true;
break;
}
}
if (!teilbar)
{
Primzahlen.Add(i);
}
}
return Primzahlen;
}
}
}
C#-Code
namespace Exercise_70
{
using System;
using System.Numerics;
internal static class Program
{
private static void Main(string[] args)
{
BigInteger n = 30;
while (true)
{
if (n.Test())
{
Console.WriteLine(n);
break;
}
n += 1;
}
Console.Read();
}
private static bool Test(this BigInteger n)
{
for (var i = 1; i < 31; i++)
{
if (n % i != 0)
{
return false;
}
}
return true;
}
}
}
C#-Code
using System;
using System.Collections.Generic;
using System.Numerics;
using System.Diagnostics;
namespace aufgabe_70 {
static class Program {
static void Main() {
Stopwatch sw = new Stopwatch();
sw.Start();
Console.WriteLine(((BigInteger)1E+5).main());
Console.WriteLine(sw.Elapsed.ToString());
sw.Restart();
Console.WriteLine(((BigInteger)4E+4).main());
Console.WriteLine(sw.Elapsed.ToString());
sw.Restart();
Console.WriteLine(((BigInteger)20).main());
Console.WriteLine(sw.Elapsed.ToString());
sw.Restart();
Console.WriteLine(((BigInteger)30).main());
Console.WriteLine(sw.Elapsed.ToString());
Console.ReadKey(true);
}
static string main(this BigInteger bis) {
BigInteger[] primes = bis.primes_until();
BigInteger erg = 1;
for (var i = 0; i < primes.Length; i++) {
BigInteger p = primes[i];
while (p * primes[i] <= bis)
p *= primes[i];
erg *= p;
};
return (erg.ToString("n0"));
}
static BigInteger[] primes_until(this BigInteger m) {
List<BigInteger> p = new List<BigInteger>(); p.Add(2);
for (BigInteger i = 3; i <= m; i += 2) {
bool bo_isprime = true;
for (var j = 0; j < p.Count; j++)
if (i % p[j] == 0)
{ bo_isprime = false; break; }
if (bo_isprime)
p.Add(i);
}
return p.ToArray();
}
}
}
C#-Codeusing System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Threading.Tasks;
namespace TrainYourProgrammer70
{
class Program
{
static void Main(string[] args)
{
BigInteger ausgabe = 1;
for (int i = 1; i <= 30; i++)
{
if (ausgabe % i != 0)
{
ausgabe += 1;
i = 1;
}
}
Console.Write(ausgabe);
Console.ReadKey();
}
}
}