Eleganteste Weg Primzahlen zu erzeugen [geschlossen]
https://stackoverflow.com/questions/1042902
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Was ist der eleganteste Weg, um diese Funktion zu implementieren:
ArrayList generatePrimes(int n)
Diese Funktion erzeugt das erste n Primzahlen (edit: wo n>1), so generatePrimes(5) wird eine ArrayList mit {2, 3, 5, 7, 11} zurück. (Ich tue dies in C #, aber ich bin glücklich mit einer Java-Implementierung - oder ähnliche Sprache für diese Angelegenheit (also nicht Haskell)).
Ich weiß, wie man diese Funktion zu schreiben, aber wenn ich es letzte Nacht habe es nicht so schön, wie ich am Ende hatte gehofft. Hier ist, was ich kam mit:
ArrayList generatePrimes(int toGenerate)
{
ArrayList primes = new ArrayList();
primes.Add(2);
primes.Add(3);
while (primes.Count < toGenerate)
{
int nextPrime = (int)(primes[primes.Count - 1]) + 2;
while (true)
{
bool isPrime = true;
foreach (int n in primes)
{
if (nextPrime % n == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
break;
}
else
{
nextPrime += 2;
}
}
primes.Add(nextPrime);
}
return primes;
}
Ich bin nicht allzu besorgt über die Geschwindigkeit, obwohl ich es nicht will offensichtlich ineffizient. Ich bin nicht dagegen, welche Methode verwendet wird (naive oder Sieb oder etwas anderes), aber ich will es ziemlich kurz und klar sein, wie es funktioniert.
Bearbeiten : Vielen Dank an alle, die geantwortet haben, obwohl viele nicht meine eigentliche Frage beantworten. Um es zu wiederholen, wollte ich ein schönes, sauberes Stück Code, der eine Liste von Primzahlen erzeugt. Ich weiß schon, wie es eine Reihe von verschiedenen Möglichkeiten zu tun, aber ich bin anfällig für das Schreiben von Code, das nicht so klar ist, wie es sein könnte. In diesem Thread haben ein paar gute Optionen vorgeschlagen:
- Eine schönere Version von dem, was ich ursprünglich hatte (Peter Smit, jmservera und Rekreativc)
- Eine sehr saubere Umsetzung des Sieb des Eratosthenes (starblue)
- Verwenden von Java
BigIntegers undnextProbablePrimefür sehr einfachen Code, obwohl ich mir nicht vorstellen kann besonders effizient sein (DFA) - Verwenden Sie LINQ to lazily die Liste der Primzahlen (Maghis) erzeugen
- Setzen Sie viele Primzahlen in einer Textdatei und liest sie in bei Bedarf (Darin)
Edit 2 : Ich habe anständige Methode die Grenze zu finden, zu den Sieben zu liefern).
Lösung 2
Vielen Dank an alle, die hilfreichen Antworten gab. Hier sind meine Implementierungen von ein paar verschiedene Methoden zu finden, die ersten n Primzahlen in C #. Die ersten beiden Methoden sind so ziemlich, was hier geschrieben. (Die Plakate Namen sind neben dem Titel.) Ich plane, irgendwann mit dem Sieb des Atkin auf tun, obwohl ich es vermute nicht, wie die Methoden, die hier zur Zeit ganz so einfach sein. Wenn jemand eine Art und Weise sehen kann jede dieser Methoden zur Verbesserung Ich würde gerne wissen: -)
Standard-Methode ( Peter Smit, jmservera , Rekreativc )
Die erste Primzahl ist 2. diese von Primzahlen zu einer Liste hinzufügen. Die nächste Primzahl ist die nächste Zahl, die nicht teilbar durch eine beliebige Anzahl in dieser Liste.
public static List<int> GeneratePrimesNaive(int n)
{
List<int> primes = new List<int>();
primes.Add(2);
int nextPrime = 3;
while (primes.Count < n)
{
int sqrt = (int)Math.Sqrt(nextPrime);
bool isPrime = true;
for (int i = 0; (int)primes[i] <= sqrt; i++)
{
if (nextPrime % primes[i] == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
primes.Add(nextPrime);
}
nextPrime += 2;
}
return primes;
}
Dies ist nur durch die Prüfung für Teilbarkeit bis zur Quadratwurzel der Anzahl getestet optimiert; und durch das Testen nur ungerade Zahlen. Dies kann weiter durch Testen nur Zahlen der Form 6k+[1, 5] optimiert werden, oder 30k+[1, 7, 11, 13, 17, 19, 23, 29] oder usw. .
Sieb des Eratosthenes ( starblue )
Dies findet alle Primzahlen k . Um eine Liste der ersten machen n Primzahlen, müssen wir zunächst den ungefähren Wert der n th prime. Die folgende Methode, dieses Sieb vor kurzem, aber es kann sehr einfach implementiert werden. Meine Implementierung ist nicht so schnell wie das Sieb des Eratosthenes, aber es ist wesentlich schneller als die naive Methode.
public static BitArray SieveOfSundaram(int limit)
{
limit /= 2;
BitArray bits = new BitArray(limit + 1, true);
for (int i = 1; 3 * i + 1 < limit; i++)
{
for (int j = 1; i + j + 2 * i * j <= limit; j++)
{
bits[i + j + 2 * i * j] = false;
}
}
return bits;
}
public static List<int> GeneratePrimesSieveOfSundaram(int n)
{
int limit = ApproximateNthPrime(n);
BitArray bits = SieveOfSundaram(limit);
List<int> primes = new List<int>();
primes.Add(2);
for (int i = 1, found = 1; 2 * i + 1 <= limit && found < n; i++)
{
if (bits[i])
{
primes.Add(2 * i + 1);
found++;
}
}
return primes;
}
Andere Tipps
Mit der Schätzung
pi(n) = n / log(n)
für die Anzahl der Primzahlen bis n eine Grenze zu finden, und dann durch ein Sieb zu verwenden. Die Schätzung unterschätzt die Anzahl der Primzahlen bis n etwas, so dass das Sieb etwas größer sein als notwendig, was in Ordnung ist.
Das ist mein Standard-Java-Sieb, berechnet die erste Million Primzahlen in etwa eine Sekunde auf einem normalen Laptop:
public static BitSet computePrimes(int limit)
{
final BitSet primes = new BitSet();
primes.set(0, false);
primes.set(1, false);
primes.set(2, limit, true);
for (int i = 0; i * i < limit; i++)
{
if (primes.get(i))
{
for (int j = i * i; j < limit; j += i)
{
primes.clear(j);
}
}
}
return primes;
}
Resurrecting eine alte Frage, aber ich stolperte über sie, während sie mit LINQ zu spielen.
Dieser Code erfordert .NET4.0 oder NET3.5 Mit Parallel Extensions
public List<int> GeneratePrimes(int n) {
var r = from i in Enumerable.Range(2, n - 1).AsParallel()
where Enumerable.Range(2, (int)Math.Sqrt(i)).All(j => i % j != 0)
select i;
return r.ToList();
}
Sie sind auf dem guten Weg.
Einige Kommentare
-
primes.Add (3); macht, dass diese Funktion nicht für Nummer funktioniert = 1
-
Sie dont't die Division mit primenumbers testen größer, dass die Wurzel aus der Zahl getestet werden.
Empfohlene Code:
ArrayList generatePrimes(int toGenerate)
{
ArrayList primes = new ArrayList();
if(toGenerate > 0) primes.Add(2);
int curTest = 3;
while (primes.Count < toGenerate)
{
int sqrt = (int) Math.sqrt(curTest);
bool isPrime = true;
for (int i = 0; i < primes.Count && primes.get(i) <= sqrt; ++i)
{
if (curTest % primes.get(i) == 0)
{
isPrime = false;
break;
}
}
if(isPrime) primes.Add(curTest);
curTest +=2
}
return primes;
}
Sie sollten einen Blick auf wahrscheinlich Primzahlen . Insbesondere werfen Sie einen Blick href="http://en.wikipedia.org/wiki/Randomized_algorithm" rel="noreferrer"> Randomisierte Algorithmen und Miller-Rabin-Test .
Der Vollständigkeit halber könnte man einfach java .math.BigInteger :
public class PrimeGenerator implements Iterator<BigInteger>, Iterable<BigInteger> {
private BigInteger p = BigInteger.ONE;
@Override
public boolean hasNext() {
return true;
}
@Override
public BigInteger next() {
p = p.nextProbablePrime();
return p;
}
@Override
public void remove() {
throw new UnsupportedOperationException("Not supported.");
}
@Override
public Iterator<BigInteger> iterator() {
return this;
}
}
@Test
public void printPrimes() {
for (BigInteger p : new PrimeGenerator()) {
System.out.println(p);
}
}
Keineswegs effecient, aber vielleicht die am besten lesen:
public static IEnumerable<int> GeneratePrimes()
{
return Range(2).Where(candidate => Range(2, (int)Math.Sqrt(candidate)))
.All(divisor => candidate % divisor != 0));
}
mit:
public static IEnumerable<int> Range(int from, int to = int.MaxValue)
{
for (int i = from; i <= to; i++) yield return i;
}
In der Tat nur eine Variation einiger Beiträge hier mit schöner Formatierung.
Ich weiß, dass Sie nicht-Haskell Lösung gefragt, aber ich bin auch diese hier, da es auf die Frage bezieht und auch ist Haskell schön für diese Art der Sache.
module Prime where
primes :: [Integer]
primes = 2:3:primes'
where
-- Every prime number other than 2 and 3 must be of the form 6k + 1 or
-- 6k + 5. Note we exclude 1 from the candidates and mark the next one as
-- prime (6*0+5 == 5) to start the recursion.
1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]
primes' = p : filter isPrime candidates
isPrime n = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
divides n p = n `mod` p == 0
Verwenden Sie eine erstklassige Zahlen Generator erstellen primes.txt und dann:
class Program
{
static void Main(string[] args)
{
using (StreamReader reader = new StreamReader("primes.txt"))
{
foreach (var prime in GetPrimes(10, reader))
{
Console.WriteLine(prime);
}
}
}
public static IEnumerable<short> GetPrimes(short upTo, StreamReader reader)
{
int count = 0;
string line = string.Empty;
while ((line = reader.ReadLine()) != null && count++ < upTo)
{
yield return short.Parse(line);
}
}
}
In diesem Fall verwende ich Int16 in der Methodensignatur, so meine primes.txt Datei enthält Zahlen von 0 bis 32767. Wenn Sie dies Int32 oder Int64 Ihre primes.txt sein könnte erweitern wollen deutlich größer.
Ich kann die folgende C # Lösung anbieten. Es ist keineswegs schnell, aber es ist sehr klar, was es tut.
public static List<Int32> GetPrimes(Int32 limit)
{
List<Int32> primes = new List<Int32>() { 2 };
for (int n = 3; n <= limit; n += 2)
{
Int32 sqrt = (Int32)Math.Sqrt(n);
if (primes.TakeWhile(p => p <= sqrt).All(p => n % p != 0))
{
primes.Add(n);
}
}
return primes;
}
ich alle Kontrollen gelassen - wenn Grenze negativ oder kleiner als zwei ist (im Moment wird das Verfahren durchweg mindestens zwei Rück als Haupt). Aber das ist alles einfach zu beheben.
UPDATE
Withe die folgenden zwei Erweiterungsmethoden
public static void Do<T>(this IEnumerable<T> collection, Action<T> action)
{
foreach (T item in collection)
{
action(item);
}
}
public static IEnumerable<Int32> Range(Int32 start, Int32 end, Int32 step)
{
for (int i = start; i < end; i += step)
}
yield return i;
}
}
Sie können es wie folgt umschreiben.
public static List<Int32> GetPrimes(Int32 limit)
{
List<Int32> primes = new List<Int32>() { 2 };
Range(3, limit, 2)
.Where(n => primes
.TakeWhile(p => p <= Math.Sqrt(n))
.All(p => n % p != 0))
.Do(n => primes.Add(n));
return primes;
}
Es ist weniger effizient (weil die Quadratwurzel als ziemlich oft neu bewertet), aber es ist noch sauberer Code. Es ist möglich, den Code neu zu schreiben, zu faul die Primzahlen aufzählen, aber das wird der Code ziemlich viel Unordnung.
Hier ist eine Implementierung von Sieb des Eratosthenes in C #:
IEnumerable<int> GeneratePrimes(int n)
{
var values = new Numbers[n];
values[0] = Numbers.Prime;
values[1] = Numbers.Prime;
for (int outer = 2; outer != -1; outer = FirstUnset(values, outer))
{
values[outer] = Numbers.Prime;
for (int inner = outer * 2; inner < values.Length; inner += outer)
values[inner] = Numbers.Composite;
}
for (int i = 2; i < values.Length; i++)
{
if (values[i] == Numbers.Prime)
yield return i;
}
}
int FirstUnset(Numbers[] values, int last)
{
for (int i = last; i < values.Length; i++)
if (values[i] == Numbers.Unset)
return i;
return -1;
}
enum Numbers
{
Unset,
Prime,
Composite
}
Copyrights 2009 von St.Wittum 13189 Berlin DEUTSCHLAND unter CC-BY-SA-Lizenz https://creativecommons.org/licenses/by-sa/3.0/
Die einfache, aber höchst elegante Weise Primzahlen zu berechnen sein würde, aber auf diese Weise langsam und Speicherkosten sind viel höher für höhere Zahlen weil mit der Fakultät (!) Funktion ... aber es zeigt eine Variation von Wilson Theoreme in einer Anwendung, alle Primzahlen von Algorithmus zu erzeugen implementiert in Python
#!/usr/bin/python
f=1 # 0!
p=2 # 1st prime
while True:
if f%p%2:
print p
p+=1
f*=(p-2)
Arbeiten mit dem gleichen Algorithmus können Sie es tun etwas kürzer:
List<int> primes=new List<int>(new int[]{2,3});
for (int n = 5; primes.Count< numberToGenerate; n+=2)
{
bool isPrime = true;
foreach (int prime in primes)
{
if (n % prime == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
primes.Add(n);
}
ich eine einfache Eratosthenes Implementierung in C # geschrieben einige LINQ verwenden.
Leider ist LINQ nicht eine unendliche Folge von ints, so dass Sie int.MaxValue verwenden: (
Ich hatte in einem anonimous zwischenzuspeichern den Kandidaten sqrt geben Sie es für jede zwischengespeichert prim zu vermeiden berechnen (sieht ein bisschen hässlich).
Ich verwende eine Liste der bisherigen Primzahlen bis sqrt des Kandidaten
cache.TakeWhile(c => c <= candidate.Sqrt)
und jede Int überprüfen 2 gegen sie beginnen
.Any(cachedPrime => candidate.Current % cachedPrime == 0)
Hier ist der Code:
static IEnumerable<int> Primes(int count)
{
return Primes().Take(count);
}
static IEnumerable<int> Primes()
{
List<int> cache = new List<int>();
var primes = Enumerable.Range(2, int.MaxValue - 2).Select(candidate => new
{
Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
Current = candidate
}).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
.Any(cachedPrime => candidate.Current % cachedPrime == 0))
.Select(p => p.Current);
foreach (var prime in primes)
{
cache.Add(prime);
yield return prime;
}
}
Eine weitere Optimierung ist die Überprüfung auch Zahlen zu vermeiden und dem nur 2 vor der Erstellung der Liste. Auf diese Weise, wenn die aufrufende Methode fragt nur für 1 prime es wird alles, das Chaos vermeiden:
static IEnumerable<int> Primes()
{
yield return 2;
List<int> cache = new List<int>() { 2 };
var primes = Enumerable.Range(3, int.MaxValue - 3)
.Where(candidate => candidate % 2 != 0)
.Select(candidate => new
{
Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
Current = candidate
}).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
.Any(cachedPrime => candidate.Current % cachedPrime == 0))
.Select(p => p.Current);
foreach (var prime in primes)
{
cache.Add(prime);
yield return prime;
}
}
Um es elegant, sollten Sie Ihren IsPrime Test in ein separates Verfahren Refactoring aus, und die Looping und Schritte außerhalb damit umgehen.
Ich habe es in Java eine funktionelle Bibliothek schrieb ich, aber da meine Bibliothek die gleichen Konzepte wie Aufzählungen verwendet, ich bin sicher, dass der Code ist anpassungsfähig:
Iterable<Integer> numbers = new Range(1, 100);
Iterable<Integer> primes = numbers.inject(numbers, new Functions.Injecter<Iterable<Integer>, Integer>()
{
public Iterable<Integer> call(Iterable<Integer> numbers, final Integer number) throws Exception
{
// We don't test for 1 which is implicit
if ( number <= 1 )
{
return numbers;
}
// Only keep in numbers those that do not divide by number
return numbers.reject(new Functions.Predicate1<Integer>()
{
public Boolean call(Integer n) throws Exception
{
return n > number && n % number == 0;
}
});
}
});
Hier ist ein Python-Codebeispiel, das die Summe aller Primzahlen druckt unter zwei Millionen:
from math import *
limit = 2000000
sievebound = (limit - 1) / 2
# sieve only odd numbers to save memory
# the ith element corresponds to the odd number 2*i+1
sieve = [False for n in xrange(1, sievebound + 1)]
crosslimit = (int(ceil(sqrt(limit))) - 1) / 2
for i in xrange(1, crosslimit):
if not sieve[i]:
# if p == 2*i + 1, then
# p**2 == 4*(i**2) + 4*i + 1
# == 2*i * (i + 1)
for j in xrange(2*i * (i + 1), sievebound, 2*i + 1):
sieve[j] = True
sum = 2
for i in xrange(1, sievebound):
if not sieve[i]:
sum = sum + (2*i+1)
print sum
Dies ist die eleganteste ich kurzfristig denken kann.
ArrayList generatePrimes(int numberToGenerate)
{
ArrayList rez = new ArrayList();
rez.Add(2);
rez.Add(3);
for(int i = 5; rez.Count <= numberToGenerate; i+=2)
{
bool prime = true;
for (int j = 2; j < Math.Sqrt(i); j++)
{
if (i % j == 0)
{
prime = false;
break;
}
}
if (prime) rez.Add(i);
}
return rez;
}
Hope dies hilft Ihnen eine Idee zu geben. Ich bin sicher, dass diese optimiert werden können, aber es sollte Ihnen eine Idee geben, wie Sie Ihre Version eleganter gemacht werden.
EDIT: Wie in den Kommentaren darauf hingewiesen, in der Tat dieser Algorithmus liefert falsche Werte für numberToGenerate <2. Ich möchte nur darauf hinweisen, dass ich versuchte, ihn nicht eine große Methode zu schreiben prime zu erzeugen Zahlen (für den bei Henri Antwort aussehen), ich mearly wurde unter Hinweis darauf, wie seine Methode eleganter gemacht werden könnte.
Mit Stream-basierte Programmierung in Functional Java , kam ich mit dem Follow-up. Der Typ Natural ist im Wesentlichen ein BigInteger> = 0 ist.
public static Stream<Natural> sieve(final Stream<Natural> xs)
{ return cons(xs.head(), new P1<Stream<Natural>>()
{ public Stream<Natural> _1()
{ return sieve(xs.tail()._1()
.filter($(naturalOrd.equal().eq(ZERO))
.o(mod.f(xs.head())))); }}); }
public static final Stream<Natural> primes
= sieve(forever(naturalEnumerator, natural(2).some()));
Jetzt haben Sie einen Wert, dass Sie sich herumtragen können, was ein unendlicher Strom von Primzahlen ist. Sie können Dinge tun, wie folgt:
// Take the first n primes
Stream<Natural> nprimes = primes.take(n);
// Get the millionth prime
Natural mprime = primes.index(1000000);
// Get all primes less than n
Stream<Natural> pltn = primes.takeWhile(naturalOrd.lessThan(n));
Eine Erklärung des Siebes:
- Nehmen wir die erste Zahl in dem Argument Strom prim ist und es an der Vorderseite des Rückstrom setzen. Der Rest des Rückstroms ist eine Berechnung nur dann erzeugt werden, wenn gefragt.
- Wenn jemand für den Rest des Stromes fragt Sieb auf den Rest des Arguments Strom nennen, Zahlen teilbar durch die erste Anzahl Ausfiltern (der Rest der Division ist Null).
Sie müssen die folgenden Importe haben:
import fj.P1;
import static fj.FW.$;
import static fj.data.Enumerator.naturalEnumerator;
import fj.data.Natural;
import static fj.data.Natural.*;
import fj.data.Stream;
import static fj.data.Stream.*;
import static fj.pre.Ord.naturalOrd;
Ich persönlich denke, dies ist eine ziemlich kurz und sauber (Java) Implementierung:
static ArrayList<Integer> getPrimes(int numPrimes) {
ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
int n = 2;
while (primes.size() < numPrimes) {
while (!isPrime(n)) { n++; }
primes.add(n);
n++;
}
return primes;
}
static boolean isPrime(int n) {
if (n < 2) { return false; }
if (n == 2) { return true; }
if (n % 2 == 0) { return false; }
int d = 3;
while (d * d <= n) {
if (n % d == 0) { return false; }
d += 2;
}
return true;
}
Versuchen Sie, diese LINQ-Abfrage, generiert es Primzahlen wie erwartet
var NoOfPrimes= 5;
var GeneratedPrime = Enumerable.Range(1, int.MaxValue)
.Where(x =>
{
return (x==1)? false:
!Enumerable.Range(1, (int)Math.Sqrt(x))
.Any(z => (x % z == 0 && x != z && z != 1));
}).Select(no => no).TakeWhile((val, idx) => idx <= NoOfPrimes-1).ToList();
// Create a test range
IEnumerable<int> range = Enumerable.Range(3, 50 - 3);
// Sequential prime number generator
var primes_ = from n in range
let w = (int)Math.Sqrt(n)
where Enumerable.Range(2, w).All((i) => n % i > 0)
select n;
// Note sequence of output:
// 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
foreach (var p in primes_)
Trace.Write(p + ", ");
Trace.WriteLine("");
Die einfachste Methode ist der Versuch und Irrtum: Sie versuchen, wenn ein beliebige Zahl zwischen 2 und n-1 teilt Ihren Kandidaten prime n
.
Erste Kombinationen sind natürlich a) Sie nur ungerade Zahlen zu überprüfen, und b) hav Sie nur für Teiler überprüfen bis sqrt (n.)
In Ihrem Fall, in dem Sie alle vorherigen Primzahlen in dem Prozess erzeugen als auch, Sie nur, wenn eine der Primzahlen in Ihrer Liste zu überprüfen, bis (n) sqrt, teilt n.
Sollte die schnellsten Sie für Ihr Geld bekommen können: -)
Bearbeiten
Ok, Code, fragte sie ihn. Aber ich warne dich :-), das ist 5-Minuten-quick-and-dirty Delphi-Code:
procedure TForm1.Button1Click(Sender: TObject);
const
N = 100;
var
PrimeList: TList;
I, J, SqrtP: Integer;
Divides: Boolean;
begin
PrimeList := TList.Create;
for I := 2 to N do begin
SqrtP := Ceil(Sqrt(I));
J := 0;
Divides := False;
while (not Divides) and (J < PrimeList.Count)
and (Integer(PrimeList[J]) <= SqrtP) do begin
Divides := ( I mod Integer(PrimeList[J]) = 0 );
inc(J);
end;
if not Divides then
PrimeList.Add(Pointer(I));
end;
// display results
for I := 0 to PrimeList.Count - 1 do
ListBox1.Items.Add(IntToStr(Integer(PrimeList[I])));
PrimeList.Free;
end;
Zum ersten 100 Primzahlen folgender Java-Code herauszufinden, in Betracht gezogen werden kann.
int num = 2;
int i, count;
int nPrimeCount = 0;
int primeCount = 0;
do
{
for (i = 2; i <num; i++)
{
int n = num % i;
if (n == 0) {
nPrimeCount++;
// System.out.println(nPrimeCount + " " + "Non-Prime Number is: " + num);
num++;
break;
}
}
if (i == num) {
primeCount++;
System.out.println(primeCount + " " + "Prime number is: " + num);
num++;
}
}while (primeCount<100);
Ich habe dies durch erste Lesung des „Sieb des Atkin“ auf Wikki plus einige vor Gedanke, den ich dazu gegeben haben - ich viel Zeit damit verbringen, von Grund auf neu Codierung und ganz auf Leute auf Null gestellt bekommen kritisch meiner Compiler-like, sehr dichter Codierstil + ich habe nicht einmal einen ersten Versuch gemacht, den Code auszuführen ... viele des Paradigmas, das ich gelernt habe, sind hier zu bedienen, einfach lesen und weinen, bekommen, was Sie können.
Seien Sie absolut und total sicher, das wirklich alles zu testen, bevor die weitere Verwendung, sicher nicht zeigen, es jedem - es für das Lesen und die Ideen unter Berücksichtigung. Ich muß arbeiten primality Werkzeug bekommen, so das ist, wo ich jedes Mal beginne ich habe etwas zum Laufen zu bringen.
Lernen Sie eine saubere Übersetzung, dann beginnen wegzunehmen, was defekt ist - ich habe fast 108 Millionen Tastenanschläge nutzbaren Code es auf diese Art und Weise zu tun, ... verwenden, was Sie können.
Ich werde auf meiner Version von morgen arbeiten.
package demo;
// This code is a discussion of an opinion in a technical forum.
// It's use as a basis for further work is not prohibited.
import java.util.Arrays;
import java.util.HashSet;
import java.util.ArrayList;
import java.security.GeneralSecurityException;
/**
* May we start by ignores any numbers divisible by two, three, or five
* and eliminate from algorithm 3, 5, 7, 11, 13, 17, 19 completely - as
* these may be done by hand. Then, with some thought we can completely
* prove to certainty that no number larger than square-root the number
* can possibly be a candidate prime.
*/
public class PrimeGenerator<T>
{
//
Integer HOW_MANY;
HashSet<Integer>hashSet=new HashSet<Integer>();
static final java.lang.String LINE_SEPARATOR
=
new java.lang.String(java.lang.System.getProperty("line.separator"));//
//
PrimeGenerator(Integer howMany) throws GeneralSecurityException
{
if(howMany.intValue() < 20)
{
throw new GeneralSecurityException("I'm insecure.");
}
else
{
this.HOW_MANY=howMany;
}
}
// Let us then take from the rich literature readily
// available on primes and discount
// time-wasters to the extent possible, utilizing the modulo operator to obtain some
// faster operations.
//
// Numbers with modulo sixty remainder in these lists are known to be composite.
//
final HashSet<Integer> fillArray() throws GeneralSecurityException
{
// All numbers with modulo-sixty remainder in this list are not prime.
int[]list1=new int[]{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,
32,34,36,38,40,42,44,46,48,50,52,54,56,58}; //
for(int nextInt:list1)
{
if(hashSet.add(new Integer(nextInt)))
{
continue;
}
else
{
throw new GeneralSecurityException("list1");//
}
}
// All numbers with modulo-sixty remainder in this list are are
// divisible by three and not prime.
int[]list2=new int[]{3,9,15,21,27,33,39,45,51,57};
//
for(int nextInt:list2)
{
if(hashSet.add(new Integer(nextInt)))
{
continue;
}
else
{
throw new GeneralSecurityException("list2");//
}
}
// All numbers with modulo-sixty remainder in this list are
// divisible by five and not prime. not prime.
int[]list3=new int[]{5,25,35,55};
//
for(int nextInt:list3)
{
if(hashSet.add(new Integer(nextInt)))
{
continue;
}
else
{
throw new GeneralSecurityException("list3");//
}
}
// All numbers with modulo-sixty remainder in
// this list have a modulo-four remainder of 1.
// What that means, I have neither clue nor guess - I got all this from
int[]list4=new int[]{1,13,17,29,37,41,49,53};
//
for(int nextInt:list4)
{
if(hashSet.add(new Integer(nextInt)))
{
continue;
}
else
{
throw new GeneralSecurityException("list4");//
}
}
Integer lowerBound=new Integer(19);// duh
Double upperStartingPoint=new Double(Math.ceil(Math.sqrt(Integer.MAX_VALUE)));//
int upperBound=upperStartingPoint.intValue();//
HashSet<Integer> resultSet=new HashSet<Integer>();
// use a loop.
do
{
// One of those one liners, whole program here:
int aModulo=upperBound % 60;
if(this.hashSet.contains(new Integer(aModulo)))
{
continue;
}
else
{
resultSet.add(new Integer(aModulo));//
}
}
while(--upperBound > 20);
// this as an operator here is useful later in your work.
return resultSet;
}
// Test harness ....
public static void main(java.lang.String[] args)
{
return;
}
}
//eof
Mit diesem Code Versuche.
protected bool isPrimeNubmer(int n)
{
if (n % 2 == 0)
return false;
else
{
int j = 3;
int k = (n + 1) / 2 ;
while (j <= k)
{
if (n % j == 0)
return false;
j = j + 2;
}
return true;
}
}
protected void btn_primeNumbers_Click(object sender, EventArgs e)
{
string time = "";
lbl_message.Text = string.Empty;
int num;
StringBuilder builder = new StringBuilder();
builder.Append("<table><tr>");
if (int.TryParse(tb_number.Text, out num))
{
if (num < 0)
lbl_message.Text = "Please enter a number greater than or equal to 0.";
else
{
int count = 1;
int number = 0;
int cols = 11;
var watch = Stopwatch.StartNew();
while (count <= num)
{
if (isPrimeNubmer(number))
{
if (cols > 0)
{
builder.Append("<td>" + count + " - " + number + "</td>");
}
else
{
builder.Append("</tr><tr><td>" + count + " - " + number + "</td>");
cols = 11;
}
count++;
number++;
cols--;
}
else
number++;
}
builder.Append("</table>");
watch.Stop();
var elapsedms = watch.ElapsedMilliseconds;
double seconds = elapsedms / 1000;
time = seconds.ToString();
lbl_message.Text = builder.ToString();
lbl_time.Text = time;
}
}
else
lbl_message.Text = "Please enter a numberic number.";
lbl_time.Text = time;
tb_number.Text = "";
tb_number.Focus();
}
Hier ist der aspx-Code.
<form id="form1" runat="server">
<div>
<p>Please enter a number: <asp:TextBox ID="tb_number" runat="server"></asp:TextBox></p>
<p><asp:Button ID="btn_primeNumbers" runat="server" Text="Show Prime Numbers" OnClick="btn_primeNumbers_Click" />
</p>
<p><asp:Label ID="lbl_time" runat="server"></asp:Label></p>
<p><asp:Label ID="lbl_message" runat="server"></asp:Label></p>
</div>
</form>
Ergebnisse: 10000 Primzahlen in weniger als einer Sekunde
100000 Primzahlen in 63 Sekunden
Bildschirmfoto von ersten 100 Primzahlen
