Najskuteczniejszy kod dla pierwszych 10000 liczb pierwszych?

Polecam sito, albo Sito Eratostenesa albo Sito Atkina.

Sita lub Eratostenes jest prawdopodobnie najbardziej intuicyjną metodą znajdowania listy liczb pierwszych. Zasadniczo ty:

1. Zapisz listę liczb od 2 do dowolnego limitu, powiedzmy 1000.
2. Weź pierwszą liczbę, która nie jest przekreślona (dla pierwszej iteracji jest to 2) i skreśl wszystkie wielokrotności tej liczby z listy.
3. Powtórz krok 2 dopóki nie dotrzesz do końca listy. Wszystkie liczby, które nie są przekreślone są pierwsze.

Oczywiście istnieje sporo optymalizacji, które można zrobić, aby ten algorytm działał szybciej, ale to jest podstawowa idea.

Sito Atkina używa podobnego podejścia, ale niestety nie wiem na tyle, by Ci to wyjaśnić. Ale wiem, że algorytm, który połączyłem zajmuje 8 sekund, aby dowiedzieć się wszystkich liczb pierwszych do 1000000000 na starożytnym Pentium II-350

Kod źródłowy Eratostenesa: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Kod źródłowy Atkina: http://cr.yp.to/primegen.html

Nie jest to ściśle sprzeczne z ograniczeniami hardcodingu, ale jest strasznie blisko. Dlaczego nie pobrać tej listy programowo i wydrukować ją zamiast tego?

Http://primes.utm.edu/lists/small/10000.txt

GateKiller , może dodasz break do tego if W pętli foreach? To przyspieszyłoby sprawę dużo , ponieważ jeśli jak 6 jest podzielne przez 2, nie musisz sprawdzać z 3 i 5. (I tak zagłosowałbym na twoje rozwiązanie, gdybym miał wystarczającą reputację :-) ...)

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count < 10000; i++) {
    bool divisible = false;

    foreach(int number in primeNumbers) {
        if(i % number == 0) {
            divisible = true;
            break;
        }
    }

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}

W Haskell, możemy zapisać niemal słowo w słowo matematyczną definicję sita Eratostenesa, " liczby pierwsze są liczbami naturalnymi powyżej 1 bez żadnych liczb zespolonych, gdzie kompozyty znajdują się przez wyliczenie wielokrotności każdej liczby pierwszej":

primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
                                [] primes)

primes !! 10000 jest prawie natychmiastowy.

Bibliografia:

• Sito Eratostenesa
• Richard Bird ' s Seve (por. s. 10,11)
• minus, Unia

_{powyższy kod można łatwo dostosować do pracy tylko na kursach, primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). Złożoność czasu jest znacznie ulepszona (do około log współczynnik powyżej optymalnego) przez złożenie w strukturze przypominającej drzewo, a złożoność przestrzeni jest drastycznie ulepszona przez wielostopniową produkcję liczb pierwszych , w} {10]}

primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
  where
    _Y g = g (_Y g)                        -- non-sharing fixpoint combinator
    _U ((x:xs):t) = x : (union xs . _U . pairs) t       -- ~= nub.sort.concat
    pairs    (xs:ys:t)  = union xs ys : pairs t
    sieve k s@(x:xs) | k < x      = k : sieve (k+2) s   -- ~= [k,k+2..]\\s,
                     | otherwise  =     sieve (k+2) xs  --   when s⊂[k,k+2..]

_{(W Haskell nawiasy są używane do grupowania, wywołanie funkcji jest oznaczane tylko przez zestawienie, (:) jest operatorem cons dla list, oraz (.) jest operatorem kompozycji funkcjonalnej: (f . g) x = (\y -> f (g y)) x = f (g x)).}

@Matt: log(log (10000)) is ~2

Z artykułu Wikipedii (który zacytowałeś) Sito Atkina :

To sito oblicza liczbę początkową do N za pomocą O(N/log log N) operacji z tylko N^1/2+o(1) bitów pamięci. To jest trochę lepiej niż Sito z Eratostenes, który używa O(N) operacje i O (N^1/2(log log N) / log N) bity pamięci (A. O. L. Atkin, D. J. Bernstein, 2004) . Te asymptotyczne złożoność obliczeniowa include proste optymalizacje, takie jak koło faktoryzacji, a podział obliczenia do mniejszych bloków.

Biorąc pod uwagę asymptotyczne złożoności obliczeniowe wzdłuż O(N) (dla Eratostenesa) i O(N/log(log(N))) (dla Atkina) nie możemy powiedzieć (dla małego N=10_000), który algorytm, jeśli zostanie zaimplementowany, będzie szybszy.

Achim Flammenkamp napisał w Sito Eratostenesa :

Cytowany przez:

@num1

Dla interwałów większych o 10^9, na pewno dla tych > 10^10, Sito z Eratostenes jest lepszy od Sito Atkinsa i Bernsteina, które używa nieredukowalnych kwadratów binarnych formularze. Zobacz ich Artykuł w tle informacje, jak również ust. 5 Praca doktorska W. Galwaya.

Dlatego dla 10_000 Sito Eratostenesa może być szybsze niż Sito Atkina.

Aby odpowiedzieć, kod to prime_sieve.c (cytowany przez num1)

Używając GMP, można napisać:

#include <stdio.h>
#include <gmp.h>

int main() {
  mpz_t prime;
  mpz_init(prime);
  mpz_set_ui(prime, 1);
  int i;
  char* num = malloc(4000);
  for(i=0; i<10000; i++) {
    mpz_nextprime(prime, prime);
    printf("%s, ", mpz_get_str(NULL,10,prime));
  }
}

Na moim MacBooku Pro 2,33 GHz, wykonuje się w następujący sposób:

time ./a.out > /dev/null

real    0m0.033s
user    0m0.029s
sys    0m0.003s

Obliczanie 1,000,000 liczb pierwszych na tym samym laptopie:

time ./a.out > /dev/null

real    0m14.824s
user    0m14.606s
sys     0m0.086s

GMP jest wysoce zoptymalizowany do tego rodzaju rzeczy. Jeśli naprawdę nie chcesz zrozumieć algorytmów pisząc własne, powinieneś używać libGMP pod C.

Dostosowałem kod znaleziony na CodeProject , aby utworzyć:

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count < 10000; i++) {
    bool divisible = false;

    foreach(int number in primeNumbers) {
        if(i % number == 0) {
            divisible = true;
        }
    }

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}

Testowanie tego na moim ASP.NET Serwer trwał około 1 minuty.

Niezbyt wydajny, ale można użyć wyrażenia regularnego do testowania liczb pierwszych.

/^1?$|^(11+?)\1+$/

Sprawdza, czy dla ciągu składającego się z k "1"s, k jest nie liczbą pierwszą (tzn. czy łańcuch składa się z jednego" 1 "lub dowolnej liczby"1 " s, która może być wyrażona jako N-iloczyn ary).

Oto Sito Eratostenesa, które napisałem w PowerShell kilka dni temu. Posiada parametr do identyfikacji liczby pierwszych liczb, które powinny zostać zwrócone.

#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    param ($target,$count = 0)
    $sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
    $sieve = @($false) * $sieveBound
    $crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
    for ($i = 1; $i -le $crossLimit; $i ++) {
        if ($sieve[$i] -eq $false) {
            $prime = 2 * $i + 1
            write-debug "Found: $prime"
            for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
                $sieve[$x] = $true
            }
        }
    }
    $primes = @(2)
    for ($i = 1; $i -le $sieveBound; $i ++) {
        if($count -gt 0 -and $primes.length -ge $count) {
            break;
        }
        if($sieve[$i] -eq $false) {
            $prime = 2 * $i + 1
            write-debug "Output: $prime"
            $primes += $prime
        }
    }
    return $primes
}

Sito Eratostenesa jest drogą do zrobienia, ze względu na jego prostotę i szybkość. Moja implementacja w C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void)
{
    unsigned int lim, i, j;

    printf("Find primes upto: ");
    scanf("%d", &lim);
    lim += 1;
    bool *primes = calloc(lim, sizeof(bool));

    unsigned int sqrtlim = sqrt(lim);
    for (i = 2; i <= sqrtlim; i++)
        if (!primes[i])
            for (j = i * i; j < lim; j += i)
                primes[j] = true;

    printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
    for (i = 2; i < lim; i++)
        if (!primes[i])
            printf("%d\n", i);

    return 0;
}

~ 4s dla lim = 100,000,000

Adaptacja i kontynuacja GateKiller , Oto ostateczna wersja, której użyłem.

    public IEnumerable<long> PrimeNumbers(long number)
    {
        List<long> primes = new List<long>();
        for (int i = 2; primes.Count < number; i++)
        {
            bool divisible = false;

            foreach (int num in primes)
            {
                if (i % num == 0)
                    divisible = true;

                if (num > Math.Sqrt(i))
                    break;
            }

            if (divisible == false)
                primes.Add(i);
        }
        return primes;
    }

To w zasadzie to samo, ale dodałem sugestię "break on sqrt" i zmieniłem niektóre zmienne, aby lepiej pasowały do mnie. (Pracowałem nad Eulerem i potrzebowałem 10001-go prime)

Sito wydaje się być błędną odpowiedzią. Sito daje liczby pierwsze aż do liczby N, a nie Pierwsze N liczby pierwsze. Uruchom @Imran lub @Andrew Szeto, a dostaniesz pierwsze do N.

Sito może być nadal użyteczne, jeśli będziesz próbować sitów dla coraz większych liczb, dopóki nie osiągniesz określonego rozmiaru zestawu wyników i użyjesz buforowania już uzyskanych liczb, ale wierzę, że nadal nie będzie to szybsze niż rozwiązanie takie jak @Pat.

W Pythonie

import gmpy
p=1
for i in range(10000):
    p=gmpy.next_prime(p)
    print p 

Wspomniany przez Bengoldberga algorytm sita deque ' a zasługuje na bliższe przyjrzenie się, nie tylko dlatego, że jest bardzo elegancki, ale także dlatego, że czasami może być przydatny w praktyce (w przeciwieństwie do sita Atkina, które jest ćwiczeniem czysto akademickim).

Podstawową ideą algorytmu sita deque 'a jest użycie małego, przesuwnego sita, które jest wystarczająco duże, aby zawierało co najmniej jedną oddzielną wielokrotność dla każdego z obecnie "aktywnych" czynników pierwszych - tj. tych pierwszych, których kwadrat nie przekracza najniższej liczby reprezentowanej obecnie przez ruchome sito. Inną różnicą w stosunku do SoE jest to, że sito deque przechowuje rzeczywiste czynniki w szczelinach kompozytów, a nie booleanach.

Algorytm rozszerza rozmiar okna sieve w razie potrzeby, co daje dość równą wydajność w szerokim zakresie, aż do momentu, gdy sieve zacznie znacznie przekraczać pojemność pamięci podręcznej L1 procesora. Ostatnia liczba pierwsza, która w pełni pasuje, to 25 237 523 (1 579 791 St prime), która daje przybliżoną liczbę punktów dla rozsądnego zakresu działania algorytmu.

Algorytm jest dość prosty i solidny, a nawet ma wydajność w znacznie szerszym zakresie niż niezegmentowane Sito Eratostenesa. Ten ostatni jest o wiele szybszy, o ile jego sito mieści się w pełni w pamięci podręcznej, tzn. do 2^16 dla sito tylko z boolami wielkości bajtów. Wtedy jego wydajność spada coraz bardziej, choć zawsze pozostaje znacznie szybsza niż deque pomimo handicapu (na najmniej w skompilowanych językach takich jak C / C++, Pascal czy Java / C#).

Oto renderowanie algorytmu deque 'a sieve' a w C#, ponieważ uważam, że ten język - pomimo wielu wad-jest o wiele bardziej praktyczny dla prototypowania algorytmów i eksperymentów niż niezwykle uciążliwy i pedantyczny C++. (Sidenote: używam darmowego LINQPad , który pozwala zanurzyć się od razu, bez całego bałaganu z konfigurowaniem projektów, plików Makefile, katalogi lub cokolwiek innego, i daje mi taki sam stopień interaktywności jak Python prompt).

C# nie ma jawnego typu deque, ale zwykły List<int> działa wystarczająco dobrze, aby zademonstrować algorytm.

Uwaga: Ta wersja nie używa deque dla liczb pierwszych, ponieważ po prostu nie ma sensu wyrzucać sqrt (n) z n liczb pierwszych. Po co usuwać 100 pierwszych i zostawiać 9900? Przynajmniej w ten sposób wszystkie liczby pierwsze są zebrane w schludny wektor, gotowy do dalszego przetwarzam.

static List<int> deque_sieve (int n = 10000)
{
    Trace.Assert(n >= 3);

    var primes = new List<int>()  {  2, 3  };
    var sieve = new List<int>()  {  0, 0, 0  };

    for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
    {
        int base_factor = sieve[0];

        if (base_factor != 0)
        {
            // the sieve base has a non-trivial factor - put that factor back into circulation
            mark_next_unmarked_multiple(sieve, base_factor);
        }
        else if (sieve_base < current_prime_squared)  // no non-trivial factor -> found a non-composite
        {
            primes.Add(sieve_base);

            if (primes.Count == n)
                return primes;
        }
        else // sieve_base == current_prime_squared
        {
            // bring the current prime into circulation by injecting it into the sieve ...
            mark_next_unmarked_multiple(sieve, primes[current_prime_index]);

            // ... and elect a new current prime
            current_prime_squared = square(primes[++current_prime_index]);
        }

        // slide the sieve one step forward
        sieve.RemoveAt(0);  sieve_base += 2;
    }
}

Oto dwie funkcje pomocnicze:

static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
    int i = prime, e = sieve.Count;

    while (i < e && sieve[i] != 0)
        i += prime;

    for ( ; e <= i; ++e)  // no List<>.Resize()...
        sieve.Add(0);

    sieve[i] = prime;
}

static int square (int n)
{
    return n * n;
}

Prawdopodobnie najprostszym sposobem zrozumienia algorytmu jest wyobrażenie sobie go jako specjalnego sita segmentowego Eratostenesa o rozmiarze segmentu 1, któremu towarzyszy obszar przelewowy, w którym pierwsze punkty odpoczywają, gdy strzelają nad końcem segmentu. Poza tym, że pojedyncza komórka segmentu (Alias sieve[0]) została już przesiana, gdy do niej dotrzemy, ponieważ została przejechana, gdy była częścią przepełnienia miejsce.

Liczba reprezentowana przez sieve[0] jest przechowywana w sieve_base, chociaż sieve_front lub window_base byłyby również dobrymi nazwami, które pozwalają na rysowanie podobieństw do kodu Bena lub implementacji sita segmentowanego/okienkowego.

Jeśli sieve[0] zawiera niezerową wartość, to wartość ta jest czynnikiem sieve_base, który można zatem uznać za złożony. Ponieważ komórka 0 jest wielokrotnością tego czynnika, łatwo jest obliczyć jego następny skok, który jest po prostu 0 plus ten czynnik. Czy ta komórka powinna być zajęta już przez inny czynnik następnie po prostu dodać czynnik ponownie, i tak dalej, aż znajdziemy wielokrotność czynnika, gdzie żaden inny czynnik nie jest obecnie zaparkowany (rozszerzenie sita w razie potrzeby). Oznacza to również, że nie ma potrzeby przechowywania bieżących przesunięć roboczych różnych liczb pierwszych z jednego segmentu do drugiego, jak w przypadku zwykłego sita segmentowego. Gdy znajdziemy czynnik w sieve[0], jego bieżący offset roboczy wynosi 0.

Obecny prime wchodzi w grę w następujący sposób. Puszka prime staje się prądem dopiero po jego własnym wystąpieniu w strumieniu (tj. gdy został wykryty jako pierwszy, ponieważ nie został oznaczony współczynnikiem) i pozostanie prądem aż do momentu, gdy sieve[0] osiągnie swój kwadrat. Wszystkie niższe wielokrotności tej pierwszej musiały zostać skreślone z powodu aktywności mniejszych liczb pierwszych, tak jak w normalnym SoE. Ale żadna z mniejszych liczb pierwszych nie może odbić się od kwadratu, ponieważ jedynym czynnikiem kwadratu jest sama liczba pierwsza i nie jest jeszcze w obiegu w ten punkt. To wyjaśnia działania podjęte przez algorytm w przypadku sieve_base == current_prime_squared (co oznacza sieve[0] == 0, nawiasem mówiąc).

Teraz przypadek sieve[0] == 0 && sieve_base < current_prime_squared jest łatwo wyjaśniony: oznacza to, że sieve_base nie może być wielokrotnością żadnej z liczb pierwszych mniejszych od bieżącej liczby pierwszej, w przeciwnym razie byłaby oznaczona jako złożona. Nie mogę też być większą wielokrotnością aktualnej liczby pierwszej, ponieważ jej wartość jest mniejsza od kwadratu aktualnej liczby pierwszej. Dlatego musi to być nowy prime.

Algorytm jest oczywiście zainspirowany Sita Eratostenesa, ale równie oczywiście jest bardzo różne. Sito Eratostenesa czerpie swoją wyższą prędkość z prostoty jego podstawowych operacji: jeden pojedynczy dodawanie indeksu i jeden magazyn dla każdego etapu operacji to wszystko, co robi przez długie okresy czasu.

Oto proste, niezegmentowane Sito Eratostenesa, które zwykle używam do przesiewania czynników pierwszych w zakresie ushort, tj. do 2^16. Dla tego postu zmodyfikowałem go do pracy poza 2^16 przez zastąpienie int ushort

static List<int> small_odd_primes_up_to (int n)
{
    var result = new List<int>();

    if (n < 3)
        return result;

    int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
    var odd_composite = new bool[max_bit + 1];

    for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
        if (!odd_composite[i])
            for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
                odd_composite[j] = true;

    result.Add(3);  // needs to be handled separately because of the mod 3 wheel

    // read out the sieved primes
    for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
        if (!odd_composite[i])
            result.Add((i << 1) + 1);

    return result;
}

Podczas przesiewania pierwszych 10000 liczb pierwszych typowa pamięć podręczna L1 o wartości 32 Kibajtów zostanie przekroczona, ale funkcja jest nadal bardzo szybka (ułamek milisekundy nawet w C#).

Jeśli porównać ten kod do sita deque to łatwo zauważyć, że operacje sita deque są o wiele bardziej skomplikowane i nie może skutecznie amortyzować jego napowietrznych, ponieważ zawsze robi najkrótszy możliwy odcinek przejść-off w wiersz (dokładnie jedno skrzyżowanie, po pominięciu wszystkich wielokrotności, które zostały już skreślone).

Uwaga: kod C# używa int zamiast uint, ponieważ nowsze Kompilatory mają zwyczaj generowania kodu niespełniającego standardów dla uint, prawdopodobnie w celu popchnięcia ludzi do podpisanych liczb całkowitych... W wersji C++ powyższego kodu użyłem unsigned przez cały czas, oczywiście; benchmark musiał być w C++, ponieważ chciałem, aby był oparty na rzekomo odpowiednim typie deque (std::deque<unsigned>; nie było wzrost wydajności dzięki zastosowaniu unsigned short). Oto liczby dla mojego laptopa Haswell (VC++ 2015/x64):

deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms 
deque vs simple: 1.729 ms vs 0.173 ms

Uwaga: czasy C# są prawie dokładnie dwukrotnie wyższe od czasów C++, co jest całkiem dobre dla C# i pokazuje, że {[6] } nie jest slouch, nawet jeśli jest używany jako deque.

Prosty kod sitowy nadal wydmuchuje deque ' a z wody, mimo że już działa poza swoim normalnym zakresem roboczym (rozmiar pamięci podręcznej L1 przekroczony o 50%, z obsługą Cache thrashing). Dominujący częścią tego jest odczyt z przesianych liczb pierwszych, a problem z cache nie ma na to większego wpływu. W każdym razie funkcja została zaprojektowana do przesiewania czynników czynników, tj. poziomu 0 W 3-poziomowej hierarchii sitowej i zazwyczaj musi zwracać tylko kilkaset czynników lub małą liczbę tysięcy. Stąd jego prostota.

Wydajność może być poprawiona o więcej niż rząd wielkości poprzez zastosowanie segmentowego sita i optymalizację kodu do ekstrakcji sita pierwszych Mod 3 i rozwinięty dwa razy lub mod 15 i rozwinięty raz), a jeszcze więcej wydajności można wycisnąć z kodu za pomocą koła mod 16 lub mod 30 ze wszystkimi wykończeniami (tj. pełne rozwinięcie dla wszystkich pozostałości). Coś takiego jest wyjaśnione w mojej odpowiedzi naZnajdź liczbę pierwszą na stronie Code Review, gdzie omawiano podobny problem. Ale trudno dostrzec sens poprawy czasu sub-milisekund dla jednorazowego zadania...

To put things a bit w 2004 roku, w ramach projektu, w ramach projektu, rozpoczęto prace nad projektem.]}

deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms

Dla kontrastu, segmentowane sito w C# z kilkoma dzwonkami i gwizdkami robi to samo zadanie w 95 ms (nie ma dostępnych timingów C++, ponieważ wykonuję wyzwania kodowe tylko w C# w tej chwili).

Rzeczy mogą wyglądać zdecydowanie inaczej w języku interpretowanym, takim jak Python, gdzie każda operacja wiąże się z dużym kosztem, a interpreter narzeka na wszystkie różnice wynikające z przewidywanych vs. źle zinterpretowanych gałęzi lub operacje podcykliczne (przesunięcie, dodanie) vs. operacje wielocykliczne (mnożenie, a może nawet dzielenie). Wiąże się to z obniżeniem prostoty Sita Eratostenesa, co mogłoby uczynić rozwiązanie deque ' a nieco bardziej atrakcyjnym.

Ponadto, wiele czasów zgłoszonych przez innych respondentów w tym temacie są prawdopodobnie zdominowane przez czas wyjściowy . To zupełnie inna wojna, gdzie moją główną bronią jest prosta klasa jak ta: {]}

class CCWriter
{
    const int SPACE_RESERVE = 11;  // UInt31 + '\n'

    public static System.IO.Stream BaseStream;
    static byte[] m_buffer = new byte[1 << 16];  // need 55k..60k for a maximum-size range
    static int m_write_pos = 0;
    public static long BytesWritten = 0;         // for statistics

    internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();

    internal static ushort[] create_double_digit_lookup ()
    {
        var lookup = new ushort[100];

        for (int lo = 0; lo < 10; ++lo)
            for (int hi = 0; hi < 10; ++hi)
                lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);

        return lookup;
    }

    public static void Flush ()
    {
        if (BaseStream != null && m_write_pos > 0)
            BaseStream.Write(m_buffer, 0, m_write_pos);

        BytesWritten += m_write_pos;
        m_write_pos = 0;
    }

    public static void WriteLine ()
    {
        if (m_buffer.Length - m_write_pos < 1)
            Flush();

        m_buffer[m_write_pos++] = (byte)'\n';
    }

    public static void WriteLinesSorted (int[] values, int count)
    {
        int digits = 1, max_value = 9;

        for (int i = 0; i < count; ++i)
        {
            int x = values[i];

            if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
                Flush();

            while (x > max_value)
                if (++digits < 10)
                    max_value = max_value * 10 + 9;
                else
                    max_value = int.MaxValue;               

            int n = x, p = m_write_pos + digits, e = p + 1;

            m_buffer[p] = (byte)'\n';

            while (n >= 10)
            {
                int q = n / 100, w = m_double_digit_lookup[n - q * 100];
                n = q;
                m_buffer[--p] = (byte)w;
                m_buffer[--p] = (byte)(w >> 8);
            }

            if (n != 0 || x == 0)
                m_buffer[--p] = (byte)((byte)'0' + n);

            m_write_pos = e;
        }
    }
}

To zajmuje mniej niż 1 ms do zapisu 10000 (posortowanych) liczb. Jest to klasa statyczna, ponieważ jest przeznaczona do tekstowego włączenia w kodowaniu zgłoszeń wyzwań, z minimalnym zamieszaniem i zerowym obciążeniem.

Ogólnie stwierdziłem, że jest to dużo szybciej, jeśli skupiona praca jest wykonywana na całych partiach, co oznacza przesiewanie określonego zakresu, następnie wyodrębnianie wszystkich liczb pierwszych do wektora / tablicy, następnie wysadzanie całej tablicy, następnie przesiewanie następnego zakresu i tak dalej, zamiast mieszania wszystkiego razem. Posiadające oddzielne funkcje skupione na konkretnych zadaniach ułatwiają również mieszanie i dopasowywanie, umożliwiają ponowne użycie i ułatwiają rozwój/testowanie.

Oto Mój kod VB 2008, który znajduje wszystkie liczby pierwsze

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles 
Button1.Click

    Dim TestNum As Integer
    Dim X As Integer
    Dim Z As Integer
    Dim TM As Single
    Dim TS As Single
    Dim TMS As Single
    Dim UnPrime As Boolean
    Dim Sentinal As Integer
    Button1.Text = "Thinking"
    Button1.Refresh()
    Sentinal = Val(SentinalTxt.Text)
    UnPrime = True
    Primes(0) = 2
    Primes(1) = 3
    Z = 1
    TM = TimeOfDay.Minute
    TS = TimeOfDay.Second
    TMS = TimeOfDay.Millisecond
    For TestNum = 5 To Sentinal Step 2
        Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
            If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
                UnPrime = False
            End If
            X = X + 1

        Loop
        If UnPrime = True Then
            X = X + 1
            Z = Z + 1
            Primes(Z) = TestNum
        End If
        UnPrime = True
        X = 0
    Next
    Button1.Text = "Finished with " & Z
    TM = TimeOfDay.Minute - TM
    TS = TimeOfDay.Second - TS
    TMS = TimeOfDay.Millisecond - TMS
    ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub

Następujący kod Mathcad obliczył pierwszy milion liczb pierwszych w mniej niż 3 minuty.

Należy pamiętać, że byłoby to użycie zmiennoprzecinkowych podwajaczy dla wszystkich liczb i jest zasadniczo interpretowane. Mam nadzieję, że składnia jest jasna.

Jest to rozwiązanie w języku C++, wykorzystujące formę SoE:

#include <iostream>
#include <deque>

typedef std::deque<int> mydeque;

void my_insert( mydeque & factors, int factor ) {
    int where = factor, count = factors.size();
    while( where < count && factors[where] ) where += factor;
    if( where >= count ) factors.resize( where + 1 );
    factors[ where ] = factor;
}

int main() {
    mydeque primes;
    mydeque factors;
    int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
    int cnt = 2;
    factors.resize(3);
    std::cout << "2 3 ";

    while( cnt < 10000 ) {
        int factor = factors.front();
        maybe_prime += 2;
        if( factor ) {
            my_insert( factors, factor );
        } else if( maybe_prime < a_square_prime ) {
            std::cout << maybe_prime << " ";
            primes.push_back( maybe_prime );
            ++cnt;
        } else {
            my_insert( factors, a_prime );
            a_prime = primes.front();
            primes.pop_front();
            a_square_prime = a_prime * a_prime;
        }
        factors.pop_front();
    }

    std::cout << std::endl;
    return 0;
}

Zauważ, że ta wersja situ może obliczać liczby pierwsze w nieskończoność.

Zauważ również, że stl deque zajmuje O(1) Czas Na wykonanie push_back, pop_front, i losowy dostęp, chociaż subskrypcja.

Operacja resize zajmuje O(n) czas, gdzie n jest liczbą dodanych elementów. Ze względu na sposób, w jaki używamy tej funkcji, możemy traktować to jako małą stałą.

Ciało while pętli w my_insert jest wykonywane O(log log n) razy, gdzie n jest równa zmiennej maybe_prime. Jest to spowodowane tym, że wyrażenie warunkowe while będzie oceniać na true raz dla każdego czynnika pierwszego z maybe_prime. Zobacz" funkcja dzielnika " na Wikipedii.

Mnożenie przez liczbę razy my_insert pokazuje, że lista liczb pierwszych powinna zająć O(n log log n) Czas... co jest, co nie dziwi, złożonością czasową, jaką ma mieć Sito Eratostenesa.

Jednakże, podczas gdy ten kod jest wydajny, nie jest najbardziej wydajny ... Zdecydowanie sugerowałbym użycie specjalistycznej biblioteki do generowania liczb pierwszych, takiej jak primesieve. Każde naprawdę wydajne, dobrze zoptymalizowane rozwiązanie będzie wymagało więcej kodu niż ktokolwiek chce wprowadzić do Stackoverflow.

Używając Sita Eratostenesa, obliczenia są znacznie szybsze w porównaniu z algorytmem "znanych" liczb pierwszych.

Używając pseudokodu z wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), mogę mieć rozwiązanie w C#.

/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
    if (n <= 1) {
        return new int[] { };
    }

    var mark = new bool[n];
    for(var i = 2; i < n; i++) {
        mark[i] = true;
    }

    for (var i = 2; i < Math.Sqrt(n); i++) {
        if (mark[i]) {
            for (var j = (i * i); j < n; j += i) {
                mark[j] = false;
            }
        }
    }

    var primes = new List<int>();
    for(var i = 3; i < n; i++) {
        if (mark[i]) {
            primes.Add(i);
        }
    }

    return primes.ToArray();
}

GetPrimes(100000000) zajmuje 2s i 330ms.

Uwaga: wartość może się różnić w zależności od specyfikacji sprzętu.

Spędzam trochę czasu na pisaniu programu obliczającego wiele liczb pierwszych i jest to kod, którego używam do obliczania pliku tekstowego zawierającego pierwsze 1.000.000.000 liczb pierwszych. Jest po niemiecku, ale ciekawą częścią jest Metoda calcPrimes(). Pierwsze są przechowywane w tablicy zwanej Primzahlen. Polecam 64-bitowy procesor, ponieważ obliczenia są z 64-bitowymi liczbami całkowitymi.

import java.io.*;
class Primzahlengenerator {
    long[] Primzahlen;
    int LastUnknown = 2;
    public static void main(String[] args)  {
        Primzahlengenerator Generator = new Primzahlengenerator();
        switch(args.length) {
            case 0:  //Wenn keine Argumente übergeben worden:
                Generator.printHelp(); //Hilfe ausgeben
                return; //Durchfallen verhindern
            case 1:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                    //Generelle Hilfe ausgeben
                    return;
                }
                break;//dutchfallen verhindern

            case 2:
                switch (args[1]) {
                    case "-l":
                        System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
                        Generator.printHelp();                                    //Generelle Hilfe ausgeben
                        return;
                }
                break;//durchfallen verhindern
            case 3:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                      //Generelle Hilfe ausgeben
                    return;
                }
                switch(args[1]) {
                    case "-l":
                        Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
                        break;
                    default:
                        Generator.printHelp();
                        break;
                }
                break;
            default:
                Generator.printHelp();
                return;
        }
        Generator.calcPrims();
    }
    void printHelp() {
        System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen.");   //Anleitung wie man das Programm mit Argumenten füttern muss
        System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
        System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
    }
    void loadFromFile(String File) {
        // System.out.println("Lese Datei namens: \"" + File + "\"");
        try{
            int x = 0;
            BufferedReader in = new BufferedReader(new FileReader(File));
            String line;
            while((line = in.readLine()) != null) {
                Primzahlen[x] = new Long(line).longValue();
                x++;
            }
            LastUnknown = x;
        } catch(FileNotFoundException ex) {
            System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
        } catch(IOException ex) {
            System.err.println(ex);
        } catch(ArrayIndexOutOfBoundsException ex) {
            System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
            System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
            }
        /* for(long prim : Primzahlen) {
            System.out.println("" + prim);
        } */
        //Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
        //java Primzahlengenerator 1000 > 1000Primzahlen.txt
        //da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
        //erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
        //falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
        //int[] foo = { 1, 2, 3};
        //int bar = foo[4];
        //dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
    }
    void calcPrims() {
        int PrimzahlNummer = LastUnknown;
        // System.out.println("LAstUnknown ist: " + LastUnknown);
        Primzahlen[0] = 2;
        Primzahlen[1] = 3;
        long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
        boolean IstPrimzahl;
        // System.out.println("2");
        // System.out.println("3");
        int Limit = Primzahlen.length;
        while(PrimzahlNummer < Limit) {
            IstPrimzahl = true;
            double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
            for(int i = 1;i < PrimzahlNummer;i++) {
                if(AktuelleZahl % Primzahlen[i] == 0) {
                    IstPrimzahl = false;
                    break;
                }
                if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
            }
            if(IstPrimzahl) {
                Primzahlen[PrimzahlNummer] = AktuelleZahl;
                PrimzahlNummer++;
                // System.out.println("" + AktuelleZahl);
            }
            AktuelleZahl = AktuelleZahl + 2;
        }
        for(long prim : Primzahlen) {
            System.out.println("" + prim);
        }
    }
}

Napisałem to używając Pythona, ponieważ dopiero zacząłem się go uczyć i działa idealnie. 10,000 TH prime generowane przez ten kod, jak wspomniano w http://primes.utm.edu/lists/small/10000.txt . aby sprawdzić, czy n jest liczbą pierwszą, podziel n przez liczby od 2 do sqrt(n). Jeśli którakolwiek z tych liczb doskonale dzieli n, to nie jest pierwsza.

import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
    b = math.sqrt(c)
    b = int(b)
    x = 0
    for b in range(2,b+1):
        e  = c % b
        e = int(e)
        if (e == 0):
            x = x+1
    if (x == 0):
        print("%d is prime number" % c)
        count = count + 1
print("Total number of prime till %d is %d" % (a,count))

Pracuję nad find primes od około roku. To jest to co uważam za najszybsze:

import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
    public static void main(String[] args) {
        primelist primes = new primelist();
        primes.insert(3);
        primes.insert(5);
        File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
        file.getParentFile().mkdirs();
        long time = System.nanoTime();
        try{
            PrintWriter printWriter = new PrintWriter ("file0024.txt"); 
            int linenum = 0;
            printWriter.print("2");
            printWriter.print (" , ");
            printWriter.print("3");
            printWriter.print (" , ");
            int up;
            int down;           
            for(int i =1; i<357913941;i++){//
                if(linenum%10000==0){
                    printWriter.println ("");
                    linenum++;
                }
                down = i*6-1;
                if(primes.check(down)){
                    primes.insert(down);
                    //System.out.println(i*6-1);
                    printWriter.print ( down );
                    printWriter.print (" , ");
                    linenum++;  
                }
                up = i*6+1;
                if(primes.check(up)){
                    primes.insert(up);
                    //System.out.println(i*6+1);
                    printWriter.print ( up );
                    printWriter.print (" , ");
                    linenum++;  
                }
            }
            printWriter.println ("Time to execute");
            printWriter.println (System.nanoTime()-time);
            //System.out.println(primes.length);
            printWriter.close ();
        }catch(Exception e){}
    } 
}
class node{
    node next;
    int x;
    public node (){
        node next;
        x = 3;
    }
    public node(int z) {
        node next;
        x = z;
    }
}
class primelist{
    node first;
    int length =0;
    node current;
    public void insert(int x){
        node y = new node(x);
        if(current == null){
            current = y;
            first = y;
        }else{
            current.next = y;
            current = y;
        }
        length++;
    }
    public boolean check(int x){
        int p = (int)sqrt(x);
        node y = first;
        for(int i = 0;i<length;i++){
            if(y.x>p){
                return true;
            }else if(x%y.x ==0){
                return false;
            }
            y = y.next;
        }
        return true;
    }
}

1902465190909 nano sekund, aby dostać się do 2147483629 począwszy od 2.

Oto Mój kod, który znajduje pierwsze 10,000 primes w 0,049655 SEK na moim laptopie, pierwsze 1,000,000 primes w mniej niż 6 sekund i pierwsze 2,000,000 w 15 sekund
Małe wyjaśnienie. Metoda ta wykorzystuje 2 techniki do znalezienia liczby pierwszej

1. Po pierwsze każda liczba niepierwsza jest złożeniem wielokrotności liczb pierwszych, więc ten test kodu dzieląc liczbę testową przez mniejsze liczby pierwsze zamiast dowolnej liczby, zmniejsza to obliczenie co najmniej 10 razy dla liczby czterocyfrowej i jeszcze więcej dla większej liczby
2. Po drugie, oprócz dzielenia przez liczbę pierwszą, dzieli się tylko przez liczby pierwsze, które są mniejsze lub równe pierwiastkowi testowanej liczby, co znacznie zmniejsza obliczenia, działa to, ponieważ każda liczba większa niż pierwiastek liczby będzie miała odpowiednik liczby, która musi być mniejsza niż pierwiastek liczby, ale ponieważ przetestowaliśmy wszystkie liczby mniejsze niż pierwiastek, dlatego nie musimy martwić się o liczbę większą niż pierwiastek liczby. pierwiastek badanego numeru.

Przykładowe wyjście dla pierwszych 10 000 liczb pierwszych
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Oto kod w języku C, Wprowadź 1, a następnie 10 000, aby wydrukować pierwsze 10 000 liczb pierwszych.
Edit: zapomniałem, że zawiera bibliotekę math, jeśli jesteś na windows lub visual studio to powinno być dobrze, ale na Linuksie musisz skompilować kod używający argumentu-lm lub kod może nie działać
Przykład: GCC-Wall - o "% e ""% f " - lm

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>

/* Finding prime numbers */
int main()
{   
    //pre-phase
    char d,w;
    int l,o;
    printf("  1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o 
    printf("     Enter 1 or 2 to get anwser of first or second question\n");
    // decision making
    do
    {
        printf("  -->");
        scanf("%c",&d);
        while ((w=getchar()) != '\n' && w != EOF);
        if ( d == '1')
        {
            printf("\n  2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n  -->");
            scanf("%10d",&l);
            o=INT_MAX;
            printf("  Here we go!\n\n");
            break;
        }
        else if ( d == '2' )
        {
            printf("\n  2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n  -->");
            scanf("%10d",&o);
            l=o/log(o)*1.25;
            printf("  Here we go!\n\n");
            break;
        }
        else printf("\n  Try again\n");
    }while ( d != '1' || d != '2' );

    clock_t start, end;
    double cpu_time_used;
    start = clock(); /* starting the clock for time keeping */

    // main program starts here
    int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
    int s,x;

    int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
    p[1]=2;
    p[2]=3;
    p[3]=5;
    printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
    for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
        p[i]=0;

    n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
    s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
    x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */

    /* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */

    // the main loop begins here
    for ( m=4,j=1,c=2; m<=l && n <= o;)
    /* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
    {
            // this will divide n by prime number in p[j] and tries to rule out non-primes
            if ( n%p[j]==0 )
            {
                /* these steps execute if the number n is found to be non-prime */

                ++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
                s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
                if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
                {
                    x=p[c];
                    ++c;
                }
                j=1;
                /* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop for the new cycle */
            }
            // confirmation test for the prime number candidate n
            else if ( n%p[j]!=0 && p[j]==x )
            {
                /* these steps execute if the number is found to be prime */
                p[m]=n;
                printf("%10dth:%10d\n",m,p[m]);
                ++n;
                s = sqrt(n);
                ++m;
                j=1;
                /* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop */
                /* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
            }
            ++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
            // if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
            // and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
    }
    // the loops ends
    printf("  All done !!\n");
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("  Time taken : %lf sec\n",cpu_time_used);
}

Tutaj kod, który zrobiłem:

enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/   

unsigned long int n;

int prime(unsigned long int);

scanf("%ld",&n);

unsigned long int val;

for(unsigned long int i=0;i<n;i++)
{
    int flag=0;

    scanf("%ld",&val);

    flag=prime(val);

    if(flag==1)
        printf("yes\n");

    else
        printf("no\n");
}

return 0;

}

int prime(unsigned long int n)
{

if(n==2) return 1;

else if (n == 1||n%2==0)  return 0;

for (unsigned long int i=3; i<=sqrt(n); i+=2)
    if (n%i == 0)
        return 0;

return 1;
}

Używanie tablicy.prototyp.metoda find () w Javascript. 2214.486 ms

function isPrime (number) {

  function prime(element) {
    let start = 2;
    while (start <= Math.sqrt(element)) {
      if (element % start++ < 1) {
        return false;
      }
    }
    return element > 1;
  }

  return [number].find(prime)

}

function logPrimes (n) {

  let count = 0
  let nth = n

  let i = 0
  while (count < nth) {
    if (isPrime(i)) {
      count++
      console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
      if (count === nth) {
        console.log('while i', i)
        console.log('count', count)
      }
    }
    i++
  }

}

console.time(logPrimes)

logPrimes(10000)

console.timeEnd(logPrimes) // 2214.486ms

Dam ci kilka wskazówek, musisz to wdrożyć.

1. dla każdej liczby, uzyskaj połowę tej liczby. Np. dla sprawdzenia 21, uzyskaj pozostałą część, dzieląc ją z zakresu 2-10.
2. jeśli jest liczbą nieparzystą, dziel tylko przez liczbę nieparzystą i odwrotnie. Na przykład dla 21, podziel tylko przez 3, 5, 7, 9.

Najskuteczniejsza metoda jaką do tej pory osiągnąłem.

using System;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, i = 3, j, c;
            Console.WriteLine("Please enter your integer: ");
            n = Convert.ToInt32(Console.ReadLine());
            if (n >= 1)
            {
                Console.WriteLine("First " + n + " Prime Numbers are");
                Console.WriteLine("2");
            }
            for(j=2;j<=n;)
            {
                for(c=2;c<=i-1;c++)
                {
                    if(i%c==0)
                        break;
                }
                    if(c==i)
                    {
                        Console.WriteLine(i);
                        j++;
                    }
                    i++;                                
            }
            Console.Read();
        }
    }
}