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

84

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

David Johnstone
źródło
12
nie, i to też nie jest dla Projektu Euler :-)
David Johnstone,
1
byłoby lepiej, gdybym powtórzył niezliczone <int> i ustępował jeden po drugim
Felice Pollano.
4
Chciałbym wiedzieć, jaki jest najmniej elegancki sposób generowania liczb pierwszych. Myślę o czymś związanym z bazą danych Access?
j_random_hacker
1
dla porównania, 2008 kod Haskell przez BMeph : nubBy (((>1).).gcd) [2..]. Pozostawia tylko liczby naturalne, które nie są zduplikowane, począwszy od 2, podczas gdy uważa się za zduplikowaną dowolną liczbę, której gcdkażda z poprzednio znalezionych liczb jest większa niż 1. Jest to bardzo nieefektywne, kwadratowe pod względem liczby wyprodukowanych liczb pierwszych. Ale jest elegancki .
Will Ness
najbardziej elegancki , IMO, należy do Haskella, import Data.List.Ordered ; let { _Y g = g (_Y g) ; primes = 2 : _Y( (3:) . minus [5,7..] . unionAll . map (\p-> [p*p, p*p+p*2..]) ) }ale jest to oczywiście całkowicie oparte na opiniach .
Will Ness,

Odpowiedzi:

48

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;
}
starblue
źródło
3
To bardzo fajna implementacja sita Eratostenesa
David Johnstone,
1
czy nie powinno wystarczyć pętli i <= Math.sqrt(limit)w zewnętrznej pętli?
Christoph
1
@David Johnstone Nie, pi (n) = n / log (n) nie docenia liczby liczb pierwszych do n, co idzie w przeciwnym kierunku. Cieszę się jednak, że znalazłeś znacznie lepsze przybliżenie.
starblue
1
jeśli chcesz usunąć wszystkie wielokrotności 2 w jego własnej pętli, możesz użyć j + = 2 * i jako przyrostu pętli, aby zaoszczędzić trochę dodatkowego czasu wykonywania, i możesz to obliczyć raz, używając nieco przesunięcia
Nick Larsen
5
Zastępując BitSetklasą wdrażającą rozkład na koła dla 2, 3 i 5, staje się prawie 3 razy szybszy.
starblue
37

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;
}
David Johnstone
źródło
FYI - musiałem zmienić licznik głównej pętli na „for (int i = 0; i * i <= limit && i * i> 0; i ++)”, aby zapobiec przepełnieniu.
Jacobs Data Solutions
Ta implementacja Sieve of Sundaram jest jedną z nielicznych poprawnych. Większość z nich używa niewłaściwych granic dla i i j podczas obliczania, i+j+2*i*jco prowadzi do nieprawidłowego wyniku.
jahackbeth
15

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();
}
spookycoder
źródło
1
Dlaczego nie jest to akceptowana odpowiedź? Kod w tym miejscu jest znacznie krótszy, bardziej elegancki i szybszy niż kod w akceptowanej odpowiedzi. Chciałbym móc zagłosować więcej niż raz!
Avrohom Yisroel
9

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;
}
Peter Smit
źródło
1
testowanie tej liczby prime * prime <= curTest w pętli zamiast wcześniejszego obliczania pierwiastka kwadratowego prawdopodobnie przyspieszy i uczyni go bardziej ogólnym (będzie działać dla bignum itp.)
yairchu
Dlaczego warto używać pierwiastka kwadratowego? Jakie jest tło matematyczne takiej opcji? Prawdopodobnie tępo podzieliłbym tylko przez 2.
Luis Filipe
3
Ponieważ jeśli liczba ma czynniki pierwsze, co najmniej jeden z nich musi być mniejszy lub równy pierwiastkowi kwadratowemu. Jeśli a * b = c i a <= b, to a <= sqrt (c) <= b.
David Johnstone,
8

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);
    }
}
dfa
źródło
2
Miller-Rabbin jest bardzo szybki, a kod jest bardzo prosty. Zapewnienie wystarczającej liczby iteracji czyni go wystarczająco niezawodnym, aby konkurować z przypadkową awarią procesora pod względem prawdopodobieństwa fałszywie dodatniego wyniku. Wadą algorytmu jest to, że zrozumienie, dlaczego faktycznie działa, jest trudnym zadaniem.
Brian
6

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.

RaphM
źródło
5

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)
Steffen Wittum
źródło
4

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.

Darin Dimitrov
źródło
3
Cytując OP: „Nie przeszkadza mi, która metoda jest używana (naiwna, sito czy cokolwiek innego), ale chcę, aby była dość krótka i oczywista, jak to działa”. Myślę, że moja odpowiedź jest jak najbardziej trafna. Jest to również najszybsza metoda.
Darin Dimitrov
14
Nawet jeśli mówi: „Nie mam nic przeciwko, która metoda…” Nie sądzę, że obejmuje to „otwórz listę liczb pierwszych”. To by było jak odpowiedź na pytanie „jak zbudować komputer” poprzez „kup komputer”. -1
stevenvh
8
Byłoby szybciej, gdybyś faktycznie zapisał liczby pierwsze w samym kodzie źródłowym, zamiast czytać je z pliku.
Daniel Daranas,
3
Zużywasz dużo pamięci? więcej niż czytanie pełnej listy liczb pierwszych jako tekstu do ... pamięci? Czy wiesz, jak działają łańcuchy znaków w .net?
jmservera
6
Lista liczb pierwszych jest listą nieskończoną, ale niezmienną, więc użycie wstępnie obliczonej listy aż do prawdopodobnej górnej granicy aplikacji ma sens. Po co tracić czas na pisanie kodu, który może być błędny, skoro dostępna jest prawidłowa lista publiczna, której można użyć do spełnienia wymagań.
AndyM,
4

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.

Daniel Brückner
źródło
Jestem prawie pewien, że obliczanie pierwiastka kwadratowego jest optymalizowane przez kompilator JIT (po skompilowaniu z włączoną optymalizacją). Musiałbyś to zweryfikować, badając wygenerowany zestaw (IL jest tylko częściowo zoptymalizowany i nie zbliża się do optymalizacji wykonanej przez kompilator JIT. Czasy podnoszenia pętli i innych mikrooptymalizacji są już dawno za nami. W rzeczywistości czasami próbujemy przechytrzenie JIT może spowolnić twój kod
Dave Black
4

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
    }
Alon Gubkin
źródło
zrobiłbym to z boolem zamiast enum ...
Letterman
3

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);
}
jmservera
źródło
3

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
grom
źródło
Tak, też jestem wielkim fanem Haskella (szkoda, że ​​nie wiedziałem tego lepiej)
David Johnstone,
3

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;
    }
}
Maghis
źródło
1
Żałuję, że nie znałem LINQ na tyle, by docenić i lepiej zrozumieć tę odpowiedź :-) Ponadto mam wrażenie, że to nie jest implementacja sita Eratostenesa i że działa koncepcyjnie tak samo jak moja pierwotna funkcja (znajdź następną liczba, której nie można podzielić przez żadną z wcześniej znalezionych liczb pierwszych).
David Johnstone
Tak, ale „znajdź następną liczbę, której nie da się podzielić przez żadną z poprzednio znalezionych liczb pierwszych (mniejszą od liczby)” jest koncepcyjnie podobne do sita eratostenów. Jeśli wolisz, mogę go nieco zmienić, aby był bardziej czytelny, nawet jeśli nie znasz LINQ. Czy znasz iteratory?
Maghis
To, co mi się podoba w tym podejściu, to to, że następna liczba pierwsza jest obliczana właśnie wtedy, gdy dzwoniący o to poprosi, więc rzeczy takie jak „weź pierwsze n liczb pierwszych” lub „weź liczby pierwsze mniejsze od n” stają się trywialne
Maghis
1
Dzięki, ale rozumiem to na tyle, żeby mniej więcej wiedzieć, co robi :-) Podoba mi się leniwa ocena, ale nadal nie nazwałbym tego implementacją sita Eratostenesa.
David Johnstone
1

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

cjk
źródło
1

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;
            }
        });
    }
});
Vincent Robert
źródło
1

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

David Božjak
źródło
3
Ten zwraca nieprawidłowy wynik dla numberToGenerate <2
Peter Smit
To prawda, ale nie projektowałem algorytmu, po prostu pokazałem mu, jak można uczynić jego metodę bardziej elegancką. Tak więc ta wersja jest równie błędna jak ta w pytaniu otwierającym.
David Božjak
1
Nie przyszło mi do głowy, że jest zepsuty na n = 1. Zmieniłem nieco pytanie, żeby funkcja działała tylko dla n> 1 :-)
David Johnstone
to dopuszcza kwadraty liczb pierwszych jako liczby pierwsze.
Will Ness
1

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;
Apocalisp
źródło
1

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;
}
Zarkonnen
źródło
1

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();
RameshVel
źródło
1
// 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("");
Raj Parmar
źródło
0

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
grom
źródło
0

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;
stevenvh
źródło
1
A jak wyrazisz to w kodzie? :-)
David Johnstone
0

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);
Zakir Sajib
źródło
0

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
Nicholas Jordan
źródło
0

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 wprowadź opis obrazu tutaj

riz
źródło
1
Próbując go, mogłem ocenić jego skuteczność i sposób prezentacji wyników: proszę argumentować o jego elegancji.
siwobrody
Stylizacja wyniku jest tylko dodatkiem. Pozwólcie, że omówię algorytm zwracania prawdy / fałszu jako liczby pierwszej. n% 2 wyeliminuje połowę liczb, ponieważ liczba parzysta jest zawsze podzielna przez 2. W innym kodzie dzielę tylko przez liczby nieparzyste, zwiększając liczbę podzielną przez dwa (więc następna podzielna również jest nieparzysta) do połowy liczby pierwszej albo nie. Dlaczego połowa, żeby nie tracić czasu, ponieważ da nam to odpowiedź w ułamku.
riz
log10 (63) ~ = 1,8, czyli twoje dane pokazują tempo wzrostu n ^ 1,8. To jest bardzo powolne; optymalne sito implementacji Eratostenesa exibit ~ n ^ 1.01..1.05; optymalny podział próbny ~ n ^ 1,35..1,45. Twój isPrimeNubmerrzeczywiście wdrożyć podział suboptimal tril; jego asymptotyzm pogorszy się do około n ^ 2 (lub nawet powyżej), gdy spróbujesz wygenerować jeszcze więcej liczb pierwszych.
Will Ness,