Domanda

Voglio stampare i primi 10000 numeri primi.Qualcuno può darmi il codice più efficiente per questo?Chiarimenti:

  1. Non importa se il tuo codice è inefficiente per n >10000.
  2. La dimensione del codice non ha importanza.
  3. Non è possibile semplicemente codificare i valori in alcun modo.
È stato utile?

Soluzione

Il setaccio di Atkin è probabilmente quello che stai cercando, il suo tempo di esecuzione limite superiore è O(N/log log N).

Se esegui solo i numeri 1 in più e 1 in meno rispetto ai multipli di 6, potrebbe essere ancora più veloce, poiché tutti i numeri primi sopra 3 sono distanti 1 da un multiplo di sei.Risorsa per la mia dichiarazione

Altri suggerimenti

Raccomando un setaccio, o il Setaccio di Eratostene o il Setaccio di Atkin.

Il crivello o Eratostene è probabilmente il metodo più intuitivo per trovare una lista di numeri primi.Fondamentalmente tu:

  1. Scrivi un elenco di numeri da 2 al limite che desideri, diciamo 1000.
  2. Prendi il primo numero che non è stato cancellato (per la prima iterazione è 2) e cancella tutti i multipli di quel numero dall'elenco.
  3. Ripetere il passaggio 2 fino a raggiungere la fine dell'elenco.Tutti i numeri che non sono cancellati sono primi.

Ovviamente ci sono alcune ottimizzazioni che si possono fare per far funzionare questo algoritmo più velocemente, ma questa è l'idea di base.

Il setaccio di Atkin utilizza un approccio simile, ma sfortunatamente non ne so abbastanza per spiegartelo.Ma so che l'algoritmo che ho collegato impiega 8 secondi per capire tutti i numeri primi fino a 1000000000 su un antico Pentium II-350

Setaccio di Eratostene Codice sorgente: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Setaccio del codice sorgente Atkin: http://cr.yp.to/primegen.html

Ciò non è strettamente contrario alla restrizione dell'hardcoding, ma si avvicina terribilmente.Perché invece non scaricare questo elenco in modo programmatico e stamparlo?

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

GateKiller, che ne dici di aggiungere a break a tale if nel foreach ciclo continuo?Ciò accelererebbe le cose molto perché se tipo 6 è divisibile per 2 non è necessario verificare con 3 e 5.(Voterei comunque la tua soluzione se avessi abbastanza reputazione :-) ...)

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

In Haskell possiamo scrivere quasi parola per parola la definizione matematica del crivello di Eratostene, "i numeri primi sono numeri naturali superiori a 1 senza numeri compositi, dove i compositi si trovano enumerando i multipli di ciascun numero primo":

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

primes !! 10000 è quasi istantaneo.

Riferimenti:


Il codice sopra può essere facilmente modificato per funzionare solo sulle quote, primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)).La complessità temporale è molto migliorata (fino a circa a tronco d'albero fattore superiore a quello ottimale) ripiegandosi in una struttura ad albero e la complessità dello spazio lo è drasticamente migliorato di produzione di primer multistadio, In

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

(In Haskell le parentesi sono usate per il raggruppamento, una chiamata di funzione è indicata solo dalla giustapposizione, (:) è un contro operatore per elenchi e (.) è un operatore di composizione funzionale: (f . g) x = (\y -> f (g y)) x = f (g x)).

@Opaco:log(log(10000)) è ~2

Dall'articolo di Wikipedia (che hai citato) Setaccio di Atkin:

Questo setaccio calcola fino a N usando O(N/log log N) operazioni con solo n1/2+o(1) pezzetti di memoria.Questo è un po 'meglio del setaccio di Eratostene che usa O(N)operazioni e O(N1/2(registro registro n)/registro n) bit di memoria (A.O.L.Atkin, D.J.Bernstein, 2004).Queste complessità computazionali asintotiche includono semplici ottimizzazioni, come la fattorizzazione delle ruote e la divisione del calcolo in blocchi più piccoli.

Date le complessità computazionali asintotiche O(N) (per Eratostene) e O(N/log(log(N))) (per Atkin) non possiamo dire (per small N=10_000) quale algoritmo se implementato sarà più veloce.

Ha scritto Achim Flammenkamp Il crivello di Eratostene:

citato da:

@num1

Per intervalli più grandi di circa 10^9, sicuramente per quelli> 10^10, il setaccio di Eratostene è sovraperformato dal setaccio di Atkins e Bernstein che utilizza forme quadratiche binarie irriducibili.Vedi il loro documento per le informazioni di fondo e il paragrafo 5 di W.Dottorato di ricerca di Galwaytesi.

Pertanto per 10_000 Il Setaccio di Eratostene può essere più veloce del Setaccio di Atkin.

Per rispondere OP il codice è prime_sieve.c (citato da num1)

Usando GMP, si potrebbe scrivere quanto segue:

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

Sul mio MacBook Pro da 2,33 GHz, viene eseguito come segue:

time ./a.out > /dev/null

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

Calcolo di 1.000.000 di numeri primi sullo stesso laptop:

time ./a.out > /dev/null

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

GMP è altamente ottimizzato per questo genere di cose.A meno che tu non voglia veramente comprendere gli algoritmi scrivendone uno tuo, ti consigliamo di utilizzare libGMP in C.

Non è affatto efficiente, ma puoi utilizzare un'espressione regolare per verificare i numeri primi.

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

Questo verifica se, per una stringa composta da K1"S, K È non primo (cioè.se la stringa è composta da uno “1" o qualsiasi numero di "1” che può essere espresso come an N-ario prodotto).

Ho adattato il codice trovato sul file CodiceProgetto per creare quanto segue:

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

Il test sul mio server ASP.NET ha richiesto circa 1 minuto per l'esecuzione della routine.

Ecco un Sieve of Eratostene che ho scritto in PowerShell qualche giorno fa.Ha un parametro per identificare il numero di numeri primi che dovrebbero essere restituiti.

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

Setaccio di Eratostene è la strada da percorrere, perché è semplice e veloce.La mia implementazione in 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;
}

Tempo CPU per trovare i numeri primi (su Pentium Dual Core E2140 1,6 GHz, utilizzando single core)

~ 4s per lim = 100.000.000

Adattamento e seguito da GateKiller, ecco la versione finale che ho usato.

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

Fondamentalmente è lo stesso, ma ho aggiunto il suggerimento "interruzione su Sqrt" e modificato alcune variabili per adattarlo meglio alle mie esigenze.(Stavo lavorando su Eulero e avevo bisogno del 10001esimo numero primo)

Il Setaccio sembra essere la risposta sbagliata.Il setaccio ti dà i numeri primi fino a un numero N, non il primo N primi.Esegui @Imran o @Andrew Szeto e otterrai i numeri primi fino a N.

Il setaccio potrebbe ancora essere utilizzabile se continui a provare i setacci per numeri sempre più grandi finché non raggiungi una certa dimensione del set di risultati e utilizzi un po' di memorizzazione nella cache dei numeri già ottenuti, ma credo che non sarebbe comunque più veloce di una soluzione come quella di @Pat .

In Pitone

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

IL algoritmo deque sieve menzionato da BenGoldberg merita uno sguardo più attento, non solo perché è molto elegante ma anche perché occasionalmente può essere utile nella pratica (a differenza del Setaccio di Atkin, che è un esercizio puramente accademico).

L'idea di base dietro l'algoritmo del deque-sieve è quella di utilizzare un piccolo crivello scorrevole che sia abbastanza grande da contenere almeno un multiplo separato per ciascuno dei fattori primi attualmente "attivi", cioèquei numeri primi il cui quadrato non supera il numero più basso attualmente rappresentato dal crivello mobile.Un'altra differenza rispetto al SoE è che il deque sieve memorizza i fattori effettivi negli slot dei compositi, non dei booleani.

L'algoritmo estende la dimensione della finestra del filtro secondo necessità, ottenendo prestazioni abbastanza uniformi su un ampio intervallo finché il filtro non inizia a superare in modo apprezzabile la capacità della cache L1 della CPU.L'ultimo numero primo che si adatta perfettamente è 25.237.523 (il numero primo 1.579.791), che fornisce una cifra approssimativa per il ragionevole intervallo operativo dell'algoritmo.

L'algoritmo è abbastanza semplice e robusto e offre prestazioni anche su un intervallo molto più ampio rispetto a un Setaccio di Eratostene non segmentato.Quest'ultimo è molto più veloce finché il suo setaccio entra completamente nella cache, cioèfino a 2 ^ 16 per un setaccio di sole quote con bool di dimensioni in byte.Successivamente le sue prestazioni diminuiscono sempre di più, anche se nonostante l'handicap rimane sempre molto più veloce della deque (almeno nei linguaggi compilati come C/C++, Pascal o Java/C#).

Ecco un rendering dell'algoritmo deque sieve in C#, perché trovo che il linguaggio, nonostante i suoi numerosi difetti, sia molto più pratico per la prototipazione di algoritmi e la sperimentazione rispetto al estremamente ingombrante e pedante C++. (Nota a margine:Sto usando il servizio gratuito LINQPad che rende possibile immergersi direttamente, senza tutta la confusione con l'impostazione di progetti, makefile, directory o quant'altro, e mi dà lo stesso grado di interattività di un prompt Python).

C# non ha un tipo deque esplicito ma il plain List<int> funziona abbastanza bene per dimostrare l'algoritmo.

Nota:questa versione non utilizza una deque per i numeri primi, perché semplicemente non ha senso estrarre sqrt(n) da n numeri primi.A cosa servirebbe rimuovere 100 numeri primi e lasciare 9900?Almeno in questo modo tutti i numeri primi vengono raccolti in un vettore ordinato, pronti per ulteriori elaborazioni.

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

Ecco le due funzioni di supporto:

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

Probabilmente il modo più semplice per comprendere l'algoritmo è immaginarlo come uno speciale crivello segmentato di Eratostene con una dimensione del segmento pari a 1, accompagnato da un'area di overflow dove i numeri primi si fermano quando sparano oltre l'estremità del segmento.Tranne che la singola cella del segmento (a.k.a. sieve[0]) è già stato setacciato quando ci arriviamo, perché è stato investito mentre faceva parte della zona di tracimazione.

Il numero rappresentato da sieve[0] è trattenuto sieve_base, Sebbene sieve_front O window_base sarebbero anche dei buoni nomi che permettessero di tracciare paralleli con il codice di Ben o con le implementazioni di setacci segmentati/a finestra.

Se sieve[0] contiene un valore diverso da zero, quel valore è un fattore di sieve_base, che può quindi essere riconosciuto come composito.Poiché la cella 0 è un multiplo di quel fattore, è facile calcolare il salto successivo, che è semplicemente 0 più quel fattore.Se quella cella è già occupata da un altro fattore, aggiungiamo semplicemente nuovamente il fattore, e così via finché non troviamo un multiplo del fattore dove nessun altro fattore è attualmente parcheggiato (estendendo il setaccio se necessario).Ciò significa anche che non è necessario memorizzare gli attuali offset di lavoro dei vari numeri primi da un segmento al successivo, come in un normale crivello segmentato.Ogni volta che troviamo un fattore in sieve[0], il suo offset di lavoro corrente è 0.

L’attuale numero primo entra in gioco nel modo seguente.Un numero primo può diventare attuale solo dopo la sua presenza nel flusso (cioèquando sarà stato rilevato come primo, perché non contrassegnato da un fattore), e rimarrà attuale fino al momento esatto in cui ciò avverrà sieve[0] raggiunge la sua piazza.Tutti i multipli inferiori di questo primo devono essere stati cancellati a causa delle attività dei numeri primi più piccoli, proprio come in un normale SoE.Ma nessuno dei numeri primi più piccoli può eliminare il quadrato, poiché l’unico fattore del quadrato è il primo stesso e a questo punto non è ancora in circolazione.Ciò spiega le azioni intraprese dall’algoritmo nel caso sieve_base == current_prime_squared (il che implica sieve[0] == 0, A proposito).

Ora il caso sieve[0] == 0 && sieve_base < current_prime_squared è facilmente spiegabile:significa che sieve_base non può essere un multiplo di nessuno dei numeri primi più piccoli del numero primo corrente, altrimenti sarebbe stato contrassegnato come composto.Non posso nemmeno essere un multiplo più alto del primo attuale, poiché il suo valore è inferiore al quadrato del primo attuale.Quindi deve essere un nuovo numero primo.

L'algoritmo è ovviamente ispirato al Setaccio di Eratostene, ma altrettanto ovviamente è molto diverso.Il Setaccio di Eratostene deve la sua velocità superiore alla semplicità delle sue operazioni elementari:una singola aggiunta di indice e un archivio per ogni passaggio dell'operazione è tutto ciò che fa per lunghi periodi di tempo.

Ecco un semplice Setaccio di Eratostene non segmentato che normalmente utilizzo per setacciare i fattori primi nell'intervallo ucorto, cioèfino a 2^16.Per questo post l'ho modificato per funzionare oltre 2 ^ 16 sostituendo int per 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;
}

Durante il setacciamento dei primi 10000 numeri primi verrà superata la tipica cache L1 di 32 KiByte ma la funzione è ancora molto veloce (frazione di millisecondo anche in C#).

Se confronti questo codice con il deque sieve, allora è facile vedere che le operazioni del deque sieve sono molto più complicate e non può ammortizzare efficacemente il suo sovraccarico perché esegue sempre il tratto più breve possibile di incroci di fila (esattamente una singola cancellazione, dopo aver saltato tutti i multipli già cancellati).

Nota:utilizza il codice C# int invece di uint perché i compilatori più recenti hanno l'abitudine di generare codice scadente per uint, probabilmente per spingere le persone verso gli interi con segno...Nella versione C++ del codice sopra ho usato unsigned dappertutto, naturalmente;il benchmark doveva essere in C++ perché volevo che fosse basato su un tipo di deque apparentemente adeguato (std::deque<unsigned>;non c'è stato alcun miglioramento delle prestazioni dall'utilizzo unsigned short).Ecco i numeri per il mio laptop 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

Nota:i tempi C# sono praticamente esattamente il doppio dei tempi C++, il che è abbastanza buono per C# e lo dimostra List<int> non è una cosa da poco anche se abusata come una deque.

Il semplice codice di setaccio fa comunque saltare la deque fuori dall'acqua, anche se sta già funzionando oltre il suo normale intervallo di funzionamento (dimensione della cache L1 superata del 50%, con relativo thrashing della cache).La parte dominante qui è la lettura dei numeri primi filtrati, e questo non è influenzato molto dal problema della cache.In ogni caso la funzione è stata progettata per vagliare i fattori dei fattori, cioèlivello 0 in una gerarchia di setacci a 3 livelli e in genere deve restituire solo poche centinaia di fattori o un numero basso di migliaia.Da qui la sua semplicità.

Le prestazioni potrebbero essere migliorate di oltre un ordine di grandezza utilizzando un setaccio segmentato e ottimizzando il codice per l'estrazione dei numeri primi setacciati (gradino mod 3 e srotolato due volte, o mod 15 e srotolato una volta), e tuttavia si potrebbero ottenere maggiori prestazioni il codice utilizzando una ruota mod 16 o mod 30 con tutte le rifiniture (es.srotolamento completo di tutti i residui).Qualcosa del genere è spiegato nella mia risposta a Trova il numero primo posizionato primo su Code Review, dove è stato discusso un problema simile.Ma è difficile capire l'utilità di migliorare i tempi inferiori al millisecondo per un'attività una tantum...

Per mettere le cose un po' in prospettiva, ecco i tempi C++ per il setacciamento fino a 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

Al contrario, un setaccio segmentato in C# con alcuni fronzoli fa lo stesso lavoro in 95 ms (non sono disponibili tempistiche in C++, dal momento che al momento eseguo sfide di codice solo in C#).

Le cose possono apparire decisamente diverse in un linguaggio interpretato come Python, dove ogni operazione ha un costo elevato e il sovraccarico dell'interprete sminuisce tutte le differenze dovute alla differenza prevista rispetto a quella prevista.rami o operazioni sottociclo errate (spostamento, addizione) vs.operazioni multiciclo (moltiplicazione e forse anche divisione).Ciò è destinato a erodere il vantaggio di semplicità del Setaccio di Eratostene, e questo potrebbe rendere la soluzione deque un po’ più attraente.

Inoltre, molti dei tempi riportati da altri intervistati in questo argomento sono probabilmente dominati da tempo di uscita.Questa è una guerra completamente diversa, in cui la mia arma principale è una classe semplice come questa:

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

Ciò richiede meno di 1 ms per scrivere 10000 numeri (ordinati).È una classe statica perché è destinata all'inclusione testuale negli invii di sfide di codifica, con il minimo sforzo e zero spese generali.

In generale ho trovato che lo fosse tanto più velocemente se il lavoro mirato viene eseguito su interi batch, ovvero setacciare un certo intervallo, quindi estrarre tutti i numeri primi in un vettore/array, quindi eliminare l'intero array, quindi setacciare l'intervallo successivo e così via, invece di mescolare tutto insieme.Avere funzioni separate focalizzate su attività specifiche semplifica inoltre la combinazione e l'abbinamento, consente il riutilizzo e facilita lo sviluppo/test.

Ecco il mio codice VB 2008, che trova tutti i numeri primi <10.000.000 in 1 minuto e 27 secondi sul mio laptop da lavoro.Salta i numeri pari e cerca solo i numeri primi < del quadrato del numero di prova.È progettato solo per trovare numeri primi da 0 a un valore sentinale.

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

Il seguente codice Mathcad calcola il primo milione di numeri primi in meno di 3 minuti.

Tieni presente che questo utilizzerebbe i doppi in virgola mobile per tutti i numeri e viene sostanzialmente interpretato.Spero che la sintassi sia chiara.

enter image description here

Ecco una soluzione C++, utilizzando una forma di 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;
}

Si noti che questa versione del Sieve può calcolare i numeri primi indefinitamente.

Da notare anche il file STL deque prende O(1) tempo per esibirsi push_back, pop_front, e accesso casuale tramite abbonamento.

IL resize l'operazione richiede O(n) tempo, dove n è il numero di elementi da aggiungere.A causa del modo in cui utilizziamo questa funzione, possiamo considerarla una piccola costante.

Il corpo del while entrare in loop my_insert viene eseguito O(log log n) volte, dove n è uguale alla variabile maybe_prime.Questo perché l'espressione della condizione di while valuterà vero una volta per ciascun fattore primo di maybe_prime.Vedere "Funzione divisore"su Wikipedia.

Moltiplicando per il numero di volte my_insert si chiama, mostra che dovrebbe prendere O(n log log n) tempo di elencare n primi...che è, non sorprendentemente, la complessità temporale che si suppone abbia il Setaccio di Eratostene.

Tuttavia, mentre questo codice È efficiente, non è il più efficiente...Suggerirei vivamente di utilizzare una libreria specializzata per la generazione di numeri primi, come primesieve.Qualsiasi soluzione veramente efficiente e ben ottimizzata richiederà più codice di quanto chiunque voglia inserire in Stackoverflow.

Usando il Setaccio di Eratostene, il calcolo è molto più veloce rispetto all'algoritmo dei numeri primi "a livello noto".

Utilizzando lo pseudocodice dal suo wiki (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), posso avere la soluzione su 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) impiega 2 secondi e 330 ms.

NOTA:Il valore potrebbe variare in base alle specifiche hardware.

Trascorro un po' di tempo a scrivere un programma che calcola molti numeri primi e questo è il codice che utilizzo per calcolare un file di testo contenente i primi 1.000.000.000 di numeri primi.È in tedesco, ma la parte interessante è il metodo calcPrimes().I numeri primi sono memorizzati in un array chiamato Primzahlen.Raccomando una CPU a 64 bit perché i calcoli sono con numeri interi a 64 bit.

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

L'ho scritto usando Python, poiché ho appena iniziato a impararlo, e funziona perfettamente.Il 10.000esimo numero primo generato da questo codice è uguale a quello menzionato in http://primes.utm.edu/lists/small/10000.txt.Per verificare se n è primo o no, dividi n dai numeri da 2 A sqrt(n).Se uno qualsiasi di questi intervalli di numeri si divide perfettamente n allora non è primo.

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

Sto lavorando alla ricerca dei numeri primi da circa un anno.Questo è quello che ho trovato essere il più veloce:

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 secondi per arrivare a 2147483629 a partire da 2.

Ecco il mio codice che trova i primi 10.000 numeri primi in 0,049655 sec sul mio laptop, primi 1.000.000 numeri primi in meno di 6 secondi e primi 2.000.000 in 15 secondi
Una piccola spiegazione.Questo metodo utilizza 2 tecniche per trovare i numeri primi

  1. prima di tutto qualsiasi numero non primo è un composto di multipli di numeri primi quindi questo codice testa dividendo il numero di prova per numeri primi più piccoli invece che per qualsiasi numero, questo diminuisce il calcolo di almeno 10 volte per un numero di 4 cifre e anche di più per un numero maggiore
  2. in secondo luogo, oltre a dividere per numeri primi, divide solo per numeri primi che sono minori o uguali alla radice del numero da testare riducendo ulteriormente i calcoli, questo funziona perché qualsiasi numero maggiore della radice del numero avrà un numero di controparte che deve essere più piccolo della radice del numero ma poiché abbiamo già testato tutti i numeri più piccoli della radice, non dobbiamo preoccuparci del numero maggiore della radice del numero da testare.

Output di esempio per i primi 10.000 numeri primi
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Ecco il codice in lingua C, inserisci 1 e poi 10.000 per stampare i primi 10.000 numeri primi.
Modificare:Ho dimenticato che questo contiene una libreria matematica, se utilizzi Windows o Visual Studio dovrebbe andare bene, ma su Linux devi compilare il codice utilizzando l'argomento -lm altrimenti il ​​codice potrebbe non funzionare
Esempio: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);
}

Ecco il codice che ho creato:


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

Utilizzando il metodo Array.prototype.find() in 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

Posso darti qualche consiglio, devi metterlo in pratica.

  1. Per ogni numero, ottieni la metà di quel numero.Per esempio.per controllare 21, ottieni solo il resto dividendolo dall'intervallo 2-10.
  2. Se è un numero dispari, dividi solo per il numero dispari e viceversa.Ad esempio per 21, dividi solo per 3, 5, 7, 9.

Il metodo più efficiente che ho utilizzato finora.

Dal momento che vuoi i primi 10000 primi 10000, piuttosto che codificare algoritmo complesso, suggerirò quanto segue

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

ora la chiamata è fondamentale perché ne hai bisogno

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}
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();
        }
    }
}
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top