Najbardziej elegancki sposób generowania liczb pierwszych [zamknięte]

Jaki jest najbardziej elegancki sposób realizacji tej funkcji:

ArrayList generatePrimes(int n)

Ta funkcja generuje pierwsze nliczby pierwsze (edit: where n>1), więc generatePrimes(5)zwróci ArrayListwith {2, 3, 5, 7, 11}. (Robię to w C #, ale jestem zadowolony z implementacji Java - lub innego podobnego języka (a więc nie Haskell)).

Wiem, jak napisać tę funkcję, ale kiedy zrobiłem to zeszłej nocy, nie skończyło się tak dobrze, jak się spodziewałem. Oto co wymyśliłem:

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;
}

Nie przejmuję się zbytnio szybkością, chociaż nie chcę, aby była ona oczywiście nieefektywna. Nie przeszkadza mi, która metoda jest używana (naiwna, sito lub cokolwiek innego), ale chcę, aby była dość krótka i oczywista, jak to działa.

Edycja : Dziękuję wszystkim, którzy odpowiedzieli, chociaż wielu nie odpowiedziało na moje rzeczywiste pytanie. Powtarzając, chciałem mieć ładny, czysty fragment kodu, który generowałby listę liczb pierwszych. Wiem już, jak to zrobić na wiele różnych sposobów, ale mam skłonność do pisania kodu, który nie jest tak jasny, jak mógłby być. W tym wątku zaproponowano kilka dobrych opcji:

• Ładniejsza wersja tego, co pierwotnie miałem (Peter Smit, jmservera i Rekreativc)
• Bardzo czyste wykonanie sita Eratostenes (starblue)
• Użyj Java's BigIntegeri nextProbablePrimedla bardzo prostego kodu, chociaż nie wyobrażam sobie, żeby był szczególnie wydajny (dfa)
• Użyj LINQ, aby leniwie generować listę liczb pierwszych (Maghis)
• Umieść wiele liczb pierwszych w pliku tekstowym i przeczytaj je w razie potrzeby (darin)

Edycja 2 : Zaimplementowałem w C # kilka metod podanych tutaj i inną metodę, o której tutaj nie wspomniano. Wszystkie skutecznie znajdują pierwsze n liczb pierwszych (a ja mam przyzwoitą metodę znajdowania granicy, którą należy dostarczyć do sit).

Skorzystaj z oszacowania

pi(n) = n / log(n)

dla liczby liczb pierwszych do n, aby znaleźć granicę, a następnie użyj sita. Oszacowanie nieco zaniża liczbę liczb pierwszych do n, więc sito będzie nieco większe niż to konieczne, co jest w porządku.

To jest moje standardowe sito Java, oblicza pierwszy milion liczb pierwszych w ciągu około sekundy na normalnym laptopie:

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;
}

Wielkie dzięki dla wszystkich, którzy udzielili pomocnych odpowiedzi. Oto moje implementacje kilku różnych metod znajdowania pierwszych n liczb pierwszych w C #. Pierwsze dwie metody są mniej więcej tym, co zostało tutaj opublikowane. (Nazwy plakatów są obok tytułu.) Planuję kiedyś zrobić sito Atkina, chociaż podejrzewam, że nie będzie to tak proste, jak obecne metody. Jeśli ktoś może znaleźć sposób na ulepszenie którejkolwiek z tych metod, chciałbym wiedzieć :-)

Metoda standardowa ( Peter Smit , jmservera , Rekreativc )

Pierwsza liczba pierwsza to 2. Dodaj ją do listy liczb pierwszych. Następna liczba pierwsza jest następną liczbą, która nie jest podzielna równo przez żadną liczbę na tej liście.

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;
}

Zostało to zoptymalizowane przez testowanie tylko podzielności do pierwiastka kwadratowego z testowanej liczby; i testując tylko liczby nieparzyste. Może to być dodatkowo zoptymalizowany poprzez badanie tylko liczbę postaci 6k+[1, 5]lub 30k+[1, 7, 11, 13, 17, 19, 23, 29]i tak dalej .

Sieve of Eratostenes ( starblue )

To znajduje wszystkie liczby pierwsze do k . Aby sporządzić listę pierwszych n liczb pierwszych, musimy najpierw oszacować wartość n- tej liczby pierwszej. Robi to następująca metoda, jak tutaj opisano .

public static int ApproximateNthPrime(int nn)
{
    double n = (double)nn;
    double p;
    if (nn >= 7022)
    {
        p = n * Math.Log(n) + n * (Math.Log(Math.Log(n)) - 0.9385);
    }
    else if (nn >= 6)
    {
        p = n * Math.Log(n) + n * Math.Log(Math.Log(n));
    }
    else if (nn > 0)
    {
        p = new int[] { 2, 3, 5, 7, 11 }[nn - 1];
    }
    else
    {
        p = 0;
    }
    return (int)p;
}

// Find all primes up to and including the limit
public static BitArray SieveOfEratosthenes(int limit)
{
    BitArray bits = new BitArray(limit + 1, true);
    bits[0] = false;
    bits[1] = false;
    for (int i = 0; i * i <= limit; i++)
    {
        if (bits[i])
        {
            for (int j = i * i; j <= limit; j += i)
            {
                bits[j] = false;
            }
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfEratosthenes(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfEratosthenes(limit);
    List<int> primes = new List<int>();
    for (int i = 0, found = 0; i < limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(i);
            found++;
        }
    }
    return primes;
}

Sito Sundaram

Dopiero niedawno odkryłem to sito , ale można je wdrożyć po prostu. Moja realizacja nie jest tak szybka jak sito Eratostenesa, ale jest znacznie szybsza niż metoda naiwna.

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;
}

Wracam do starego pytania, ale natknąłem się na nie podczas gry z LINQ.

Ten kod wymaga .NET4.0 lub .NET3.5 z równoległymi rozszerzeniami

public List<int> GeneratePrimes(int n) {
    var r = from i in Enumerable.Range(2, n - 1).AsParallel()
            where Enumerable.Range(1, (int)Math.Sqrt(i)).All(j => j == 1 || i % j != 0)
            select i;
    return r.ToList();
}

Jesteś na dobrej drodze.

Kilka komentarzy

• liczby pierwsze.Dodaj (3); sprawia, że ​​ta funkcja nie działa dla liczby = 1

• Nie musisz testować dzielenia z liczbami pierwotnymi większymi niż pierwiastek kwadratowy testowanej liczby.

Sugerowany kod:

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;
}

powinieneś przyjrzeć się prawdopodobnym liczbom pierwszym . W szczególności spójrz na algorytmy losowe i test pierwszości Millera – Rabina .

Ze względu na kompletność możesz po prostu użyć 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);
    }
}

W żadnym wypadku nieefektywny, ale może najbardziej czytelny:

public static IEnumerable<int> GeneratePrimes()
{
   return Range(2).Where(candidate => Range(2, (int)Math.Sqrt(candidate)))
                                     .All(divisor => candidate % divisor != 0));
}

z:

public static IEnumerable<int> Range(int from, int to = int.MaxValue)
{
   for (int i = from; i <= to; i++) yield return i;
}

W rzeczywistości tylko odmiana niektórych postów tutaj z ładniejszym formatowaniem.

Copyrights 2009 by St.Wittum 13189 Berlin, NIEMCY na licencji CC-BY-SA https://creativecommons.org/licenses/by-sa/3.0/

Najprostszym, ale najbardziej eleganckim sposobem obliczenia WSZYSTKICH PIERWOTNYCH byłoby to, ale ten sposób jest powolny, a koszty pamięci są znacznie wyższe dla wyższych liczb, ponieważ użycie funkcji wydziału (!) ... ale demonstruje odmianę Twierdzenia Wilsona w aplikacji do generuje wszystkie liczby pierwsze za pomocą algorytmu zaimplementowanego w Pythonie

#!/usr/bin/python
f=1 # 0!
p=2 # 1st prime
while True:
    if f%p%2:
        print p
    p+=1
    f*=(p-2)

Użyj generatora liczb pierwszych , aby utworzyć primes.txt, a następnie:

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);
        }
    }
}

W tym przypadku używam Int16 w sygnaturze metody, więc mój plik primes.txt zawiera liczby od 0 do 32767. Jeśli chcesz rozszerzyć to na Int32 lub Int64, twój primes.txt może być znacznie większy.

Mogę zaoferować następujące rozwiązanie C #. Nie jest to szybkie, ale jest bardzo jasne, co robi.

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;
}

Pominąłem wszelkie sprawdzenia - jeśli limit jest ujemny lub mniejszy niż dwa (na razie metoda zawsze zwróci co najmniej dwa jako liczbę pierwszą). Ale to wszystko jest łatwe do naprawienia.

AKTUALIZACJA

Z następujących dwóch metod rozszerzania

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;
    }
}

możesz go przepisać w następujący sposób.

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;
}

Jest mniej wydajny (ponieważ pierwiastek kwadratowy jest często przewartościowywany), ale jest jeszcze czystszym kodem. Możliwe jest przepisanie kodu, aby leniwie wyliczyć liczby pierwsze, ale to trochę zaśmieci kod.

Oto implementacja Sieve of Eratostenes w 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
    }

Używając tego samego algorytmu, możesz to zrobić trochę krócej:

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);
}

Wiem, że prosiłeś o rozwiązanie inne niż Haskell, ale włączam to tutaj, ponieważ odnosi się do pytania, a także Haskell jest piękny w tego typu sprawach.

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

Napisałem prostą implementację Eratostenesa w języku C # przy użyciu LINQ.

Niestety LINQ nie zapewnia nieskończonej sekwencji int, więc musisz użyć int.MaxValue :(

Musiałem zapisać w pamięci podręcznej anonimowy typ sqrt kandydata, aby uniknąć obliczania go dla każdej buforowanej liczby pierwszej (wygląda trochę brzydko).

Używam listy poprzednich liczb pierwszych do kwadratu kandydata

cache.TakeWhile(c => c <= candidate.Sqrt)

i sprawdź z nim każdy Int zaczynający się od 2

.Any(cachedPrime => candidate.Current % cachedPrime == 0)

Oto kod:

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;
    }
}

Inną optymalizacją jest uniknięcie sprawdzania liczb parzystych i zwrócenie zaledwie 2 przed utworzeniem listy. W ten sposób, jeśli metoda wywołująca prosi tylko o 1 liczbę pierwszą, uniknie całego bałaganu:

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;
    }
}

Aby uczynić go bardziej eleganckim, należy refaktoryzować test IsPrime do oddzielnej metody i obsługiwać pętle i inkrementacje poza tym.

Zrobiłem to w Javie przy użyciu biblioteki funkcjonalnej, którą napisałem, ale ponieważ moja biblioteka używa tych samych pojęć co Enumerations, jestem pewien, że kod można dostosować:

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;
            }
        });
    }
});

To najbardziej elegancki, jaki przychodzi mi do głowy w krótkim czasie.

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;
}

Mam nadzieję, że to pomoże ci podpowiedzieć. Jestem pewien, że można to zoptymalizować, ale powinno to dać ci wyobrażenie, jak twoja wersja mogłaby być bardziej elegancka.

EDYCJA: Jak zauważono w komentarzach, ten algorytm rzeczywiście zwraca błędne wartości dla numberToGenerate <2. Chcę tylko podkreślić, że nie próbowałem wysłać mu świetnej metody generowania liczb pierwszych (spójrz na odpowiedź Henri), Mówiłem szczerze, jak można uczynić jego metodę bardziej elegancką.

Używając programowania strumieniowego w funkcjonalnej Javie , wymyśliłem następujące. Typ Naturalto zasadniczo a BigInteger> = 0.

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()));

Teraz masz wartość, którą możesz nosić ze sobą, która jest nieskończonym strumieniem liczb pierwszych. Możesz robić takie rzeczy:

// 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));

Wyjaśnienie dotyczące sita:

1. Załóżmy, że pierwsza liczba w strumieniu argumentów jest liczbą pierwszą i umieść ją na początku strumienia zwrotnego. Reszta strumienia zwrotnego to obliczenia, które mają być wykonane tylko na żądanie.
2. Jeśli ktoś zapyta o resztę strumienia, wywołaj sito na pozostałej części strumienia argumentów, odfiltrowując liczby podzielne przez pierwszą liczbę (reszta z dzielenia wynosi zero).

Musisz mieć następujące importy:

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;

Osobiście uważam, że jest to dość krótka i przejrzysta implementacja (Java):

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;
}

Wypróbuj to zapytanie LINQ, generuje liczby pierwsze zgodnie z oczekiwaniami

        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("");

Oto przykład kodu w Pythonie, który wypisuje sumę wszystkich liczb pierwszych poniżej dwóch milionów:

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

Najprostszą metodą jest metoda prób i błędów: spróbuj, jeśli jakakolwiek liczba od 2 do n-1 dzieli twoją kandydującą liczbę pierwszą n.
Pierwsze skróty to oczywiście a) musisz tylko sprawdzić liczby nieparzyste i b) musisz tylko sprawdzić, czy nie ma dzielników do sqrt (n).

W twoim przypadku, w którym generujesz również wszystkie poprzednie liczby pierwsze w procesie, musisz tylko sprawdzić, czy którakolwiek z liczb pierwszych na twojej liście, do sqrt (n), dzieli n.
Powinien być najszybszy, jaki możesz dostać za swoje pieniądze :-)

edytuj
Ok, kod, prosiłeś o to. Ale ostrzegam cię :-), to jest 5-minutowy szybki i brudny kod Delphi:

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;

Aby znaleźć pierwsze 100 liczb pierwszych, można wziąć pod uwagę następujący kod java.

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);

Dostałem to po pierwszym przeczytaniu "Sieve of Atkin" na Wikki plus kilka wcześniejszych przemyśleń, które nad tym zastanawiałem - spędziłem dużo czasu na kodowaniu od zera i całkowicie wyzerowałem, że ludzie są krytyczni wobec mojego bardzo gęstego kodowania w stylu kompilatora style + Nie zrobiłem nawet pierwszej próby uruchomienia kodu ... wiele paradygmatów, których nauczyłem się używać, jest tutaj, po prostu przeczytaj i płacz, zdobądź, co możesz.

Absolutnie i całkowicie upewnij się, że naprawdę przetestujesz to wszystko przed jakimkolwiek użyciem, na pewno nikomu tego nie pokazuj - służy do czytania i rozważania pomysłów. Muszę sprawić, by narzędzie pierwszości działało, więc od tego zaczynam za każdym razem, gdy muszę coś działać.

Zdobądź jedną czystą kompilację, a następnie zacznij usuwać to, co jest wadliwe - mam prawie 108 milionów naciśnięć klawiszy używalnego kodu, robiąc to w ten sposób, ... użyj, co możesz.

Jutro będę pracował nad moją wersją.

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

Wypróbuj ten kod.

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();
    }

Oto kod aspx.

<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>

Wyniki: 10000 liczb pierwszych w mniej niż jedną sekundę

100000 liczb pierwszych w 63 sekundy

Zrzut ekranu pierwszych 100 liczb pierwszych