Najbardziej efektywny kod dla pierwszych 10000 liczb?

głosy
49

Chcę wydrukować pierwszych 10000 liczby pierwsze. Czy ktoś może dać mi najbardziej efektywny kod dla tego? wyjaśnienia:

  1. To nie ma znaczenia, czy kod jest nieefektywne dla n> 10000.
  2. Rozmiar kodu nie ma znaczenia.
  3. Nie można po prostu ciężko kodować wartości w jakikolwiek sposób.
Utwórz 03/08/2008 o 06:45
źródło użytkownik
W innych językach...                            


28 odpowiedzi

głosy
41

Sito Atkin jest chyba to, czego szukasz, jej górna granica czasu pracy wynosi O (N / log log N).

Jeśli tylko uruchomić numery 1 i 1 więcej mniej niż wielokrotność 6, może to być nawet szybciej, ponieważ wszystkie liczby pierwsze powyżej 3 są 1 od jakiegoś wielokrotności sześciu. Zasobów dla mojego rachunku

Odpowiedział 03/08/2008 o 07:03
źródło użytkownik

głosy
35

Polecam sito, albo Sito Eratostenesa lub sito atkina.

Sito lub Eratostenes jest prawdopodobnie najbardziej intuicyjna metoda znalezienia listę liczb pierwszych. Zasadniczo:

  1. Spisać listę liczb od 2 do limitu cokolwiek chcesz, powiedzmy, 1000.
  2. Zrób pierwszy numer, który nie jest wykreślona (dla pierwszej iteracji ten wynosi 2) i krzyżują się wszystkie wielokrotności tej liczby z listy.
  3. Powtórz krok 2 aż do końca listy. Wszystkie numery, które nie zostały wykreślone są pierwsze.

Oczywiście istnieje sporo optymalizacje, które można zrobić, aby ta praca algorytm szybciej, ale jest to podstawowa idea.

Sito z Atkin wykorzystuje podobne podejście, ale niestety nie wiem wystarczająco dużo o to, aby wyjaśnić je do Ciebie. Ale wiem, że algorytm I połączone trwa 8 sekund, aby dowiedzieć się, wszystkie liczby pierwsze aż po 1000000000 na starożytnych Pentium II-350

Sito Eratostenesa Source Code: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Sito atkina Source Code: http://cr.yp.to/primegen.html

Odpowiedział 06/08/2008 o 00:49
źródło użytkownik

głosy
17

To nie jest ściśle przeciwko ograniczeniu sztywno, ale chodzi strasznie blisko. Dlaczego nie programowo pobrać tę listę i wydrukować go, zamiast tego?

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

Odpowiedział 31/08/2008 o 23:20
źródło użytkownik

głosy
11

GateKiller , jak o dodanie breakdo tego ifw foreachpętli? To by przyspieszyć rzeczy dużo , bo jeśli tak jak 6 jest podzielna przez 2, nie trzeba skontaktować się z 3 i 5. (będę głosować swoje rozwiązanie w każdym razie gdybym miał wystarczająco dużo reputacji :-) ...)

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 + " ");
    }
}
Odpowiedział 27/08/2008 o 21:26
źródło użytkownik

głosy
9

W Haskell, możemy zanotować niemal słowo w słowo matematyczną definicję Sito Eratostenesa „ liczby pierwsze są liczby naturalne powyżej 1 bez liczb zespolonych, w których znajdują się kompozyty przez wyliczenie wielokrotności każdego Prime ”:

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

primes !! 10000 jest niemal natychmiastowe.

Referencje:


Powyższy kod jest łatwo manipulowane do pracy tylko na kursie, 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ść czas jest znacznie lepsze (tylko około log współczynnika powyżej optymalnej) poprzez złożenie w strukturze drzewiastej, a przestrzeń złożoność jest znacznie poprawiona przez produkcję liczb pierwszych wieloetapowym , w

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

(Haskell nawiasy służą do grupowania, wywołanie funkcji oznaczały tylko przez zestawienie, (:)to zalety operator list oraz (.)funkcjonalnego operatora skład: (f . g) x = (\y-> f (g y)) x = f (g x)).

Odpowiedział 24/04/2012 o 17:30
źródło użytkownik

głosy
9

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

Z artykułu wikipedia (które cytowane) sito atkina :

Ten oblicza liczby pierwsze sito do N pomocą O(N/log log N)operacji tylko N 1/2 + O (1) bitów w pamięci. To jest trochę lepiej niż sito Eratostenesa który wykorzystuje O(N) operacje i O (N 1/2 (log log N) / log N) bitów z pamięci (AOL Atkin DJ Bernstein, 2004) . Te asymptotyczne złożoność obliczeniowa obejmują proste optymalizacji, takich jak koła, i na czynniki podziału obliczeń na mniejsze bloki.

Biorąc pod uwagę złożoność obliczeniową asymptotyczne wzdłuż O(N)(na Eratostenes) i O(N/log(log(N)))(dla Atkin) nie możemy powiedzieć (za małe N=10_000), które jeśli algorytm realizowany będzie szybciej.

Achim Flammenkamp napisał w The Sito Eratostenesa :

cytowany przez:

@ num1

Dla większych odstępach około 10 ^ 9, z pewnością do tych> 10 ^ 10, sito Eratostenesa jest lepsza niż przez sito Atkins i Bernstein, który wykorzystuje nieredukowalnych binarnej kwadratowe. Zobacz ich papier do informacji tła, a także pkt 5 dr W. Galway Praca dyplomowa.

Dlatego dla 10_000Sito Eratostenesa może być szybciej niż sito atkina.

Aby odpowiedzieć na OP kodu prime_sieve.c (powołuje num1)

Odpowiedział 06/10/2008 o 21:03
źródło użytkownik

głosy
7

Korzystanie z GMP, można napisać, co następuje:

#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 2.33GHz MacBook Pro, wykonuje się następująco:

time ./a.out > /dev/null

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

Obliczanie 1.000.000 liczby pierwsze 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. Chyba że naprawdę chcesz zrozumieć algorytmy pisząc własną rękę, można zalecić użycie libGMP pod C.

Odpowiedział 29/08/2008 o 08:06
źródło użytkownik

głosy
4

Mam dostosowany kod znajdujący się na CodeProject tworzyć następujące:

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 to na moim ASP.NET Server zabrało rountine około 1 minuty do uruchomienia.

Odpowiedział 05/08/2008 o 20:55
źródło użytkownik

głosy
4

Nie skuteczny w ogóle, ale można użyć wyrażenia regularnego do testowania liczb pierwszych.

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

Ten test, jeżeli na sznurkiem obejmującej k1” y, k jest nie pierwsza (to znaczy, czy składa się z jednej łańcuch „ 1” i dowolna liczba „ 1” S, który może być wyrażony jako n -ary produktu).

Odpowiedział 03/08/2008 o 19:52
źródło użytkownik

głosy
3

Oto Sito Eratostenesa, że ​​napisałem w PowerShell kilka dni temu. Ma parametr identyfikacji liczby liczb pierwszych, które powinny być 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
}
Odpowiedział 07/09/2009 o 19:52
źródło użytkownik

głosy
3

Sito Eratostenesa jest droga, 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;
}

CPU czas na znalezienie liczb pierwszych (na Pentium Dual Core E2140 1,6 GHz, przy użyciu jednego rdzenia)

~ 4s dla lim = 100.000.000

Odpowiedział 21/08/2008 o 00:45
źródło użytkownik

głosy
2

Deque algorytm sito wspomniał BenGoldberg zasługuje na uwagę nie tylko dlatego, że jest bardzo elegancki, ale także dlatego, że może czasami być użyteczne w praktyce (w przeciwieństwie do sito atkina, który jest czysto akademicki ćwiczenie).

Podstawową ideą algorytmu sita deque jest użycie małego, przesuwne sito, które jest tylko na tyle duży, aby zawierać co najmniej jeden oddzielny wielokrotność dla każdej z obecnie „aktywny” czynniki pierwsze - czyli tych liczb pierwszych, których kwadratowy nie przekracza najniższy numer obecnie przedstawiony ruchomym sicie. Inną różnicą w SOE jest to, że sito deque przechowuje aktualne czynniki dociśnięto kompozytów nie logicznych.

Algorytm rozszerza rozmiar okna sito w miarę potrzeb, co powoduje dość nawet wydajność w szerokim zakresie aż sito zaczyna przekroczenia pojemności pamięci podręcznej L1 CPU znacznie. Ostatni premier, który pasuje w pełni jest 25.237.523 (prime 1,579,791st), co daje pole do gry postać surowca na rozsądnym zakresie działania algorytmu.

Algorytm jest dość prosta i wytrzymała, a to ma nawet osiągi w znacznie szerszym zakresie niż w niesegmentowanej Sito Eratostenesa. Ten ostatni jest o wiele szybciej jak długo jego sito w pełni wpisuje się w pamięci podręcznej, czyli do 2 ^ 16 dla an kursy tylko sito o wielkości bools bajtowych. Wtedy jego wydajność spada coraz bardziej, chociaż zawsze pozostaje znacznie szybciej niż deque pomimo niepełnosprawności (przynajmniej w skompilowane języków takich jak C / C ++, Pascal lub Java / C #).

Oto wiadczenia deque algorytmu sita w C #, ponieważ uważam, że język - pomimo wielu wad - o wiele bardziej praktyczne dla algorytmów prototypów i eksperymentowania niż niezwykle kłopotliwe i pedantycznym C ++. (Sidenote: Używam wolnego LINQPad co sprawia, że można nurkować w prawo, bez wszystkich niechlujstwo przy tworzeniu projektów, katalogów lub plików Makefile etażerka, a to daje mi ten sam stopień interaktywności jako wierszu Pythona).

C # nie ma wyraźny typ deque ale zwykły List<int>działa wystarczająco dobrze do wykazania algorytmu.

Uwaga: ta wersja nie korzysta z deque dla liczb pierwszych, ponieważ po prostu nie ma sensu, aby zasnąć sqrt (n) z n liczb pierwszych. Co dobre to byłoby usunięcie 100 liczb pierwszych i pozostawić 9900? Przynajmniej ten sposób wszystkie liczby pierwsze są zbierane w schludny wektora, gotowy do dalszej obróbki.

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 najłatwiejszym sposobem zrozumienia algorytmu jest to sobie wyobrazić jako specjalny segmentowej Sito Eratostenesa o wielkości segmentu 1, wraz z obszaru przepełnienia gdzie liczby pierwsze przychodzą odpoczywać, kiedy strzelać na końcu segmentu. Oprócz tego, że pojedyncza komórka segmentu (aka sieve[0]) już zostało przesiane, kiedy się do niego, ponieważ został przejechany podczas gdy było częścią obszaru przelewowego.

Numer, który jest reprezentowany przez sieve[0]odbywa się sieve_base, choć sieve_frontczy window_basebyłoby również dobre nazwy, które pozwalają na paralele do kodu Bena lub implementacje segmentacji / okienkiem sit.

Jeśli sieve[0]zawiera wartość niezerową czym wartość ta jest czynnikiem sieve_base, który może być więc uznany jako kompozyt. Ponieważ komórka 0 jest wielokrotnością tego czynnika nie jest łatwo obliczyć jego następny skok, który jest po prostu 0 oraz tego czynnika. Że komórka powinna być już zajęte przez inny czynnik, a następnie po prostu dodać czynnik znowu, i tak dalej, dopóki nie znajdziemy wielokrotność czynnika gdzie żaden inny czynnik jest obecnie zaparkowanej (rozszerzenie sito, jeśli jest to konieczne). Oznacza to również, że nie ma potrzeby zapisywania bieżących przesunięć pracy różnych liczb pierwszych z jednego segmentu do następnego, jak w normalnym segmentowej sito. Ilekroć znajdujemy się czynnikiem sieve[0], jego prąd przesunięcia pracy wynosi 0.

Obecny premier wchodzi w grę w następujący sposób. Doskonałym może stać się prąd po swoim wystąpieniu w strumieniu (tj gdy został on wykryty jako sile, bo nie oznaczony czynnik) i pozostanie on aktualny aż momencie, że sieve[0]osiągnie swój kwadrat. Wszystkie niższe wielokrotności tej sile musi zostać wykreślona z powodu działalności mniejszych liczb pierwszych, tak jak w normalnym SOE. Ale żaden z mniejszych liczb pierwszych można wykreślić kwadrat, ponieważ jedynym czynnikiem placu jest głównym sama i nie jest jeszcze w obiegu w tym momencie. Wyjaśnia, że działania podjęte przez algorytm w przypadku sieve_base == current_prime_squared(co oznacza sieve[0] == 0, nawiasem mówiąc).

Teraz sprawa sieve[0] == 0 && sieve_base < current_prime_squaredjest łatwo wytłumaczyć: to znaczy, że sieve_basenie może być wielokrotnością którykolwiek z liczb pierwszych mniejszych niż obecny premier, bo inaczej byłaby oznaczona jako kompozyt. I nie może być wyższa wielokrotnością aktualnej sile albo, ponieważ jego wartość jest mniejsza niż placu obecny premier jest. Dlatego musi to być nowy premier.

Algorytm jest oczywiście zainspirowana Sito Eratostenesa, ale równie oczywiste jest to bardzo różne. Sito Eratostenesa czerpie swoją najwyższą prędkość od prostoty swych elementarnych operacji: jeden dodatek wskaźnik single i jeden sklep na każdym etapie operacji jest wszystko, co robi przez długi czas.

Oto prosty, niesegmentowanej Sito Eratostenesa że normalnie używać do przesiewania liczb pierwszych czynnikiem w zakresie ushort, czyli do 2 ^ 16. W tym poście mam zmodyfikowano go do pracy poza 2 ^ 16 podstawiając intdoushort

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

Gdy przesiewanie pierwszy 10000 zapoczątkowuje typowy podręcznej L1 32 KiByte zostanie przekroczona, ale czynność jest nadal bardzo szybko (ułamek milisekundy nawet C #).

Jeśli porównać ten kod na sicie deque to łatwo zauważyć, że operacje deque sito są dużo bardziej skomplikowane i nie mogą skutecznie amortyzować swój narzut, ponieważ zawsze ma najkrótszy odcinek przejazdów jednorazowych w rzędzie (dokładnie jeden pojedynczy crossing-off, po omijając wszystkie wielokrotności, które przekroczyły już wyłączony).

Uwaga: kod C # używa intzamiast uintponieważ nowsze kompilatory mają zwyczaj generowania kodu dla normom uint, prawdopodobnie w celu popchnąć ludzi w kierunku podpisane liczb całkowitych ... W C ++ wersji kodu powyżej użyłem unsignedcałej, naturalnie; punktem odniesienia musi być w języku C ++, bo chciałem być oparty na rzekomo odpowiedniego typu deque ( std::deque<unsigned>; nie było przyrost wydajności z użyciem unsigned short). Oto numery na moim laptopie 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: C # czasy są prawie dokładnie podwoić C ++ czasy, co jest bardzo dobre dla C # i pokazuje, że List<int>nie garbić nawet jeśli nadużywany jako deque.

Prosty kod sito nadal wieje deque z wody, mimo że pracuje już poza jego normalnego zakresu roboczego (L1 cache wielkości przekroczenia o 50%, z towarzyszącym cache bicia). Dominującą część tutaj jest czytanie z przesianej liczb pierwszych, a to nie wpływa znacznie przez problem cache. W każdym przypadku, gdy funkcja jest przeznaczony do przesiewania czynników czynników, to znaczy na poziomie 0 w hierarchii sito 3 poziomu, i zwykle ma powrót tylko kilkaset czynników lub niewielkiej liczbie tysięcy. Stąd jego prostota.

Wydajność może być poprawiona przez więcej niż jeden rząd wielkości, stosując segmentową sito i optymalizacji kodu dla wydobycia przesianej liczb pierwszych (krok mod 3 i rozwinął dwa lub mod 15 i radialnie raz), a jeszcze bardziej wydajność może być wyciśnięta kod za pomocą mod 16 lub 30 mod koła ze wszystkimi dodatkami (to znaczy pełne rozwijanie wszystkich reszt). Coś w tym jest wyjaśnione w mojej odpowiedzi na Znajdź doskonałą umieszczony numer prime nad Code Review, gdzie podobny problem został omówiony. Ale trudno, aby zobaczyć punkt w poprawie razy sub ms dla jednorazowego zadania ...

Ujmując sprawę nieco w perspektywie, oto czasy C ++ dla przesiewanie do 100.000.000:

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

Natomiast segmentowy sito w C # z kilkoma wodotryski robi to samo zadanie w 95 ms (nie c ++ czasy dostępne, ponieważ robię kod kwestionuje jedynie w języku C # w tej chwili).

Rzeczy mogą wyglądać zdecydowanie inaczej w języku interpretowanym jak Python, gdzie każda operacja ma bardzo duże koszty i napowietrznych interpreter przyćmiewa wszystkie różnice ze względu na przewidywaną vs. mispredicted oddziałów lub ops sub-rowerowych (Shift, dodawanie) vs. ops multi-cykl (mnożenie i może nawet podział). Który jest związany z zachwiania zaletę prostoty Sito Eratostenesa, a to może sprawić, że deque rozwiązanie nieco bardziej atrakcyjne.

Ponadto, wiele z synchronizacją zgłaszanych przez innych respondentów w tym temacie są prawdopodobnie zdominowany przez czas wyjścia . To zupełnie inna wojna, gdzie moim głównym broń to prosta klasa tak:

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

Że zajmuje mniej niż 1 ms do pisania 10000 (-i) liczb. Jest to klasa statyczna, ponieważ jest on przeznaczony do włączenia tekstowych w kodowania zgłoszeń wyzwanie, z minimum zamieszania i zerowym obciążeniu.

W ogóle okazało się, że znacznie szybciej, jeśli skoncentrowany praca odbywa się na całej partii, czyli na sicie na pewien zakres, a następnie wyodrębnić wszystkie liczby pierwsze do wektora / tablicy, a następnie wybuch na całą tablicę, a następnie przesianie następny zakres i tak dalej, zamiast mieszając wszystko razem. Posiadające oddzielne funkcje koncentruje się na konkretnych zadaniach również sprawia, że łatwiej łączyć ze sobą, pozwala na ponowne użycie, a to ułatwia rozwoju / testowania.

Odpowiedział 19/04/2016 o 17:07
źródło użytkownik

głosy
2

w Pythonie

import gmpy
p=1
for i in range(10000):
    p=gmpy.next_prime(p)
    print p 
Odpowiedział 22/02/2010 o 08:45
źródło użytkownik

głosy
2

Sicie wydaje się być błędne odpowiedzi. Sito daje liczby pierwsze do liczby N , a nie pierwsze N liczb pierwszych. Run @Imran lub @Andrew Szeto, a otrzymasz liczby pierwsze aż do N.

Sito może nadal być użyteczny, jeśli próbować sita o coraz większych liczbach, aż trafisz pewnego rozmiaru zbioru wynikowego, i korzystać z niektórych buforowanie numerów już pozyskanych, ale wierzę, że to jeszcze nie szybciej będzie niż rozwiązanie podobnego @ Pat ,

Odpowiedział 19/06/2009 o 19:12
źródło użytkownik

głosy
2

Adaptacja i opierając się na GateKiller , oto ostateczna wersja, że 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;
    }

Jest to w zasadzie to samo, ale dodałem „break” na Sqrt sugestię i zmienił niektórych zmiennych wokół, aby lepiej pasować do mnie. (Byłem w pracy Eulera i potrzebował 10001th prime)

Odpowiedział 16/02/2009 o 06:17
źródło użytkownik

głosy
1

Korzystanie Sito Eratostenesa, obliczenie jest dość szybciej porównać do „znanego w całej” algorytm liczb pierwszych.

Przy użyciu Pseudokod ze to wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), będę mógł mieć rozwiązanie na 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) wykonuje 2S i 330ms.

UWAGA : Wartość może się różnić zależy od konfiguracji sprzętowej.

Odpowiedział 12/05/2016 o 03:40
źródło użytkownik

głosy
1

Oto rozwiązanie C ++, stosując 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 Sito może obliczyć liczb pierwszych w nieskończoność.

Należy również pamiętać, STL dequezajmuje O(1)czas, aby wykonać push_back, pop_frontoraz o dostępie swobodnym chociaż indeksowanie.

resizeOperacja zajmuje O(n)czas, w którym njest wiele elementów dodawane. Ze względu na to, jak używamy tej funkcji, możemy traktować to mała stała.

Ciało whilepętli my_insertjest wykonywany O(log log n)razy, gdzie njest równa zmiennej maybe_prime. To dlatego, że wyrażenie stan techniczny whileoceni true raz dla każdego głównego czynnika maybe_prime. Patrz „ Funkcja dzielnik ” na Wikipedii.

Mnożąc przez liczbę razy my_insertnazywa, pokazuje, że powinien wziąć O(n log log n)czas do listy nliczb pierwszych ... co jest zaskoczeniem, złożoność czas, który ma sito Eratostenesa mieć.

Jednakże, podczas gdy ten kod jest wydajny, nie jest to najbardziej skuteczny ... Chciałbym zdecydowanie sugerują, przy użyciu specjalistycznego bibliotekę do generowania liczb pierwszych, takich jak primesieve . Wszelkie naprawdę skuteczny, dobrze zoptymalizowane rozwiązanie zajmie więcej kodu niż ktokolwiek chce się wpisać w Stackoverflow.

Odpowiedział 16/04/2016 o 18:33
źródło użytkownik

głosy
1

Następujący kod Mathcad oblicza pierwszy milion liczb pierwszych w ciągu 3 minut.

Należy pamiętać, że to będzie za pomocą zmiennoprzecinkowych podwaja dla wszystkich liczb i jest zasadniczo interpretowane. Mam nadzieję, że składnia jest jasne.

wprowadzić opis obrazu tutaj

Odpowiedział 02/03/2014 o 02:15
źródło użytkownik

głosy
1

Tu jest mój kodu VB 2008, który wyszukuje wszystkie liczby pierwsze <10.000.000 w 1 min 27 sek na moją pracę laptopa. pomija nawet numery i patrzy tylko dla liczb pierwszych, które są <sqrt liczby testów. Jest przeznaczony tylko znaleźć liczby pierwsze od 0 do wartości sentencją.

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
Odpowiedział 11/03/2011 o 03:25
źródło użytkownik

głosy
0

Ponieważ chcesz pierwszych 10000 liczby pierwsze tylko zamiast kodowania złożony algorytm będę sugerować następujące

boolean isPrime(int n){
//even but is prime
    if(n==2)
        return true;
//even numbers filtered already 
    if(n==0 || n==1 || n%2==0)
        return false;

// loop for checking only odd factors
// i*i <= n  (same as i<=sqrt(n), avoiding floating point calculations)
    for(int i=3 ; i*i <=n ; i+=2){
    // if any odd factor divides n then its not a prime!
        if(n%i==0)
            return false;
    }
// its prime now
    return true;
}

teraz rozmowa jest pierwsza, jak trzeba go

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}
Odpowiedział 16/11/2018 o 05:34
źródło użytkownik

głosy
0

Mogę dać Ci kilka wskazówek, trzeba go wdrożyć.

  1. Dla każdego numeru dostać połowę tej liczby. Na przykład do kontroli 21, tylko otrzymać pozostałość, dzieląc go z zakresu 2-10.
  2. Jeśli jej nieparzysta, podzielić tylko przez nieparzystej, i vice versa. Takie jak 21, dzieli się z 3, 5, 7, tylko 9.

Najskuteczniejszą metodą wstałem do tej pory.

Odpowiedział 29/07/2018 o 19:25
źródło użytkownik

głosy
0

Stosując metodę Array.prototype.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
Odpowiedział 09/06/2018 o 21:49
źródło użytkownik

głosy
0

Oto 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;
}
Odpowiedział 20/01/2018 o 15:50
źródło użytkownik

głosy
0

Tu jest mój kod, który wyszukuje pierwszych 10000 liczby pierwsze w 0.049655 sekund na moim laptopie, pierwsze 1,000,000 liczb pierwszych w poniżej 6 sekund, a pierwszy 2000000 w 15 sekund
Trochę wyjaśnienia. Metoda ta wykorzystuje 2 technik, aby znaleźć liczbę pierwszą

  1. przede wszystkim dowolną liczbę drugorzędnych jest kompozytem wielokrotności liczby pierwsze więc test ten kod przez podzielenie liczby testowego przy małych liczb zamiast dowolnej liczbie, to zmniejsza się obliczanie przez conajmniej 10 razy liczbę 4 cyfr, a nawet na większa liczba
  2. Po drugie oprócz podzielenie przez prime, to dzieli tylko przez liczb pierwszych, które są mniejsze lub równe korzenia numer testowanego dalszej redukcji obliczeń znacznie, to działa, ponieważ każda liczba, która jest większa niż root numeru będzie mieć numer odpowiednik że musi być mniejszy niż pierwiastek o liczbie ale ponieważ testowałem wszystkie liczby mniejsze niż już korzenia, dlatego nie trzeba się niepokoić o numerze większym niż korzenia liczba testowanych.

Przykładowe wyjście dla pierwszego 10000 liczby pierwsze
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Oto kod w języku C, a następnie wpisz 1 10000 wydrukować pierwszych 10000 liczby pierwsze.
Edit: zapomniałem ten zawiera bibliotekę matematyczną, jeśli na okna lub visual studio, niż powinny być w porządku, ale na linux trzeba skompilować kod używając argumentu -lm lub kod może nie działać
Przykład: gcc -o -Wall „% 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);
}
Odpowiedział 06/05/2017 o 11:48
źródło użytkownik

głosy
0

Ja pracuję na bodźce znaleźć dla około roku. To co znalazłem się najszybciej:

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 zaczynając 2.

Odpowiedział 14/08/2016 o 00:20
źródło użytkownik

głosy
0

I spędzić trochę czasu na napisanie programu liczące wiele liczb pierwszych i jest to kod Przywykłem do obliczenia plik tekstowy zawierający pierwsze 1.000.000.000 liczb pierwszych. To w języku niemieckim, ale ciekawe jest to metoda calcPrimes(). Te bodźce są przechowywane w tablicy zwanej Primzahlen. Polecam CPU 64bit ponieważ obliczenia są z liczb 64-bitowych.

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);
        }
    }
}
Odpowiedział 23/04/2012 o 20:46
źródło użytkownik

głosy
0

Pisałem to w Pythonie, jak zaczęłam się go uczyć, i to działa perfekcyjnie. 10000-ta prime generowania przez ten kod tak samo jak wspomniano w http://primes.utm.edu/lists/small/10000.txt . Aby sprawdzić, czy njest pierwsza czy nie, dzielenia nprzez liczby od 2do sqrt(n). Jeżeli którykolwiek z tego zakresu liczby doskonale dzieli nto nie jest liczbą pierwszą.

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))
Odpowiedział 27/12/2010 o 18:37
źródło użytkownik

głosy
-1
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();
        }
    }
}
Odpowiedział 08/05/2012 o 05:15
źródło użytkownik

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more