Ein optimierter Algorithmus der auf der Tatsache basiert das alle Zahlen durch Primzahlen teilbar sind außer Primzahlen.
Er ist auf den ersten Blick wahrscheinlich nicht sehr verständlich aber es ist alles bis 10.000.000 überprüft
Man übergibt der Methode das Limit (höchste zu prüfende Zahl)
Die Funktion hat eine Liste mit Primzahlen (2 und 3) und prüft nun alle ungeraden Zahlen (also wird Modulus 2 ausgeschlossen) auf ihren Modulus zu allen bisherigen Primzahlen. Dabei wird nur etwa das erste drittel der Primzahlen geprüft. Warum es funktioniert weis ich nicht genau aber es funktioniert zu 99,99999999%.
// Alle Kommentare auf Englisch
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Security.Cryptography;
using System.IO;
using System.Threading;
////////////////////////////////////////////////
/// Name: PrimZahlen Rechner V2 ///
/// Author: Tim Schuster, 2013 ///
////////////////////////////////////////////////
List<UInt64> prime(int limit) // PRIMES :D
{
List<UInt64> primes = new List<UInt64>(); // Our List of primes
primes.Add(2); // Add a few primes.
primes.Add(3); // 2 could to the job but because we do not calc EVEN numbers we can not get it and need a second for safety
try
{
UInt64 lim = UInt64.Parse(limit); // How far captain?
for (UInt64 i = 1; i <= lim; i += 2)
{
if (!primes.Contains(i))
{
bool notprime = false; // Change to true if the current number is NOT a prime
for (int j = 0; j < (primes.Count / 3 + 2) && !notprime; j++) // We use (primes.Count / 3 + 2) because when checking only uneven numbers we got modulus 2 already and this gets us 3
{
UInt64 e = primes[j];
if ((i % e == 0 && e != i))
{
notprime = true; // If the modulus of the current number and the current found prime is 0 and e is not i or it is already in the prime list it is not a prime.
}
}
if (!notprime && i != 1)
{
primes.Add(i); // Add our number to the list if its not notprime or not 1
}
}
}
return primes;
}
catch (Exception e)
{
Console.Clear();
Console.Write(e.Message);
}
}
1 Kommentare zum Snippet