Feedback

C# - Schnelle Berechnung von Primzahlen

Veröffentlicht von am 1/20/2013
(0 Bewertungen)
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);
	}
}
Abgelegt unter prim, primzahl, primzahlen, check, berechnung, schnell.

1 Kommentare zum Snippet

Gwinn schrieb am 1/30/2013:
Hi,

wenn du dein Snippet wirklich bis 10.000.000 getestet hast, ist dein Rechner entweder viel schneller als meiner oder du bist ein sehr geduldiger Mensch ;)

Mit folgender Funktion bekommst du deine Primzahlen um einiges schneller:

public List<UInt64> prime(UInt64 limit)
{
// Jede Zahl, die nicht Primzahl ist, hat (mindestens) einen Primteiler
// Der kleinste Primteiler einer Zahl ist höchstens die Wurzel der Zahl selbst


// primes ist die Liste mit den gefundenen Primzahlen
List<UInt64> primes = new List<UInt64>();
// die 2 spielt als einzige gerade Primzahl eine Sonderrolle
primes.Add(2);

// primteiler durchläuft die gefundenen Primzahlen
UInt64 primteiler;
// testlimit ist die Grenze, bis zu der die Teilbarkeit geprüft werden muss
double testlimit;
// laufindex ist die Stelle an der wir uns in der Primzahl-Liste befinden
int laufindex;
// isPrim bleibt solange wahr, bis ein Primteiler gefunden wird
bool isPrim;

try
{
// überprüft werden alle ungeraden Zahlen >= 3
// gerade Zahlen < 2 haben die 2 als Teiler uns sind deswegen keine Primzahlen

for (UInt64 zahl = 3; zahl <= limit; zahl += 2)
{
// zunächst wird für jede Zahl angenommen sie sei eine Primzahl
isPrim = true;
// Wir starten bei der drei als Primteiler, weil wir gegen 2 als Primteiler nicht prüfen müssen, da wir nur ungerade Zahlen testen
primteiler = 3;
// Weil der neue Primteiler erst am Ende der Schleife festgelegt wird, startet startet der Laufindex bei 2 (der dritten Primzahl).
laufindex = 2;
// wie oben schon erwähnt müssen wir nur bis Wurzel zahl prüfen
testlimit = Math.Sqrt(zahl);

while (primteiler <= testlimit)
{
// Der Modulo ist gleich 0, wenn primteiler ein Teiler von zahl ist. Dann ist zahl keine Primzahl und die Schleife wird abgebrochen.
if (zahl % primteiler == 0)
{
isPrim = false;
break;
}
primteiler = primes[laufindex++];
}
if (isPrim)
primes.Add(zahl);
}
return primes;
}
catch (Exception e)
{
Console.Clear();
Console.Write(e.Message);
return null;
}
}


Gruß Gwinn
 

Logge dich ein, um hier zu kommentieren!