Mest effektiv kode for de første 10000 primtall?

stemmer
49

Jeg ønsker å skrive ut de første 10000 primtall. Kan noen gi meg den mest effektive kode for dette? avklaringer:

  1. Det spiller ingen rolle om koden er ineffektivt for n> 10000.
  2. Størrelsen på koden spiller ingen rolle.
  3. Du kan ikke bare vanskelig å kode verdiene på noen måte.
Publisert på 03/08/2008 klokken 05:45
kilden bruker
På andre språk...                            


28 svar

stemmer
41

Den Sil av Atkin er sannsynligvis det du leter etter, sin øvre grense kjøretid er O (N / log log N).

Hvis du bare kjøre tall en mer og en mindre enn multipler av seks, kan det bli enda raskere, som alle primtall over 3 er en unna noen flere på seks. Ressurs for min uttalelse

Svarte 03/08/2008 kl. 06:03
kilden bruker

stemmer
35

Jeg anbefaler en sil, enten Sil av Eratosthenes eller Sil av Atkin.

Sikten eller Eratosthenes er sannsynligvis den mest intuitive metoden for å finne en liste av primtall. I utgangspunktet du:

  1. Skriv ned en liste med tall fra 2 til hva grensen du ønsker, la oss si 1000.
  2. Ta det første tallet som ikke er krysset av (for første iterasjon dette er to) og kryss av alle multipler av dette nummeret fra listen.
  3. Gjenta trinn 2 til du kommer til slutten av listen. Alle tall som ikke er krysset av er førsteklasses.

Tydeligvis er det ganske mange optimaliseringer som kan gjøres for å gjøre denne algoritmen arbeide raskere, men dette er den grunnleggende ideen.

Sikten fra Atkin bruker en lignende tilnærming, men dessverre jeg ikke vet nok om det å forklare det til deg. Men jeg vet at algoritmen jeg linket tar 8 sekunder på å finne ut alle primtall opp til en milliard på en gammel Pentium II-350

Sil av Eratosthenes Kildekode: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Sil av Atkin Kildekode: http://cr.yp.to/primegen.html

Svarte 05/08/2008 kl. 23:49
kilden bruker

stemmer
17

Dette er ikke strengt mot hardcoding begrensning, men kommer veldig nær. Hvorfor ikke auto laste ned denne listen og skrive det ut, i stedet?

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

Svarte 31/08/2008 kl. 22:20
kilden bruker

stemmer
11

GateKiller , hva med å legge en breaktil som ifi foreachloop? Det ville fremskynde ting mye fordi hvis du som 6 er delelig med 2 trenger du ikke å sjekke med 3 og 5. (jeg vil stemme løsningen opp uansett om jeg hadde nok rykte :-) ...)

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 + " ");
    }
}
Svarte 27/08/2008 kl. 20:26
kilden bruker

stemmer
10

I Haskell, kan vi skrive ned nesten ord for ord den matematiske definisjonen av sil av Eratosthenes, " primtall er naturlige tall over en uten sammensatte tall, der kompositter er funnet av oppregning av hver prime er multipler ":

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

primes !! 10000 er nesten momentant.

referanser:


Koden ovenfor er lett forskjøvet inn i jobber med bare odds, primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). Tid kompleksitet er mye bedre (til omtrent en log faktor ovenfor optimal) ved folding i en trelignende struktur, og plass kompleksitet er drastisk forbedret ved flertrinns prim produksjon , i

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

(I Haskell parentesene er anvendt for gruppering, er et funksjonskall tilkjenne bare ved sidestilling, (:)er et ulemper operatør for lister, og (.)er en funksjonell sammensetning operator: (f . g) x = (\y -> f (g y)) x = f (g x)).

Svarte 24/04/2012 kl. 16:30
kilden bruker

stemmer
9

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

Fra wikipedia artikkel (som du siterte) Sil av Atkin :

Denne sil beregner primtall opp til N ved hjelp av O(N/log log N)operasjoner med bare N- 1/2 + o (1) biter lagerplass. Som er litt bedre enn for sikten med Eratosthenes som bruker O(N) operasjoner og O (N 1/2 (log log N) / log n) biter lagerplass (AOL atkin, DJ Bernstein, 2004) . Disse asymptotiske beregningsmessige kompleksitet omfatte enkle optimaliseringer, slik som hjul faktorisering, og splitte beregning for å bruke mindre blokker.

Gitt asymptotiske beregnings kompleksiteten sammen O(N)(for Eratosthenes) og O(N/log(log(N)))(for Atkin) kan vi ikke si (for lite N=10_000) som algoritme hvis implementert vil være raskere.

Achim Flammenkamp skrev i silen av Eratosthenes :

sitert av:

@ num1

For intervaller større omtrent 10 ^ 9, sikkert for de> 10 ^ 10, Eratostenes 'såld bedre resultater enn ved den Sieve av Atkins og Bernstein som benytter ikke-reduserbare binære kvadratiske former. Se deres papir for bakgrunnen informasjon samt paragraf 5 av W. Galway Ph.D. avhandling.

Derfor for 10_000Sil av Eratosthenes kan være raskere enn Sil av Atkin.

For å svare OP koden prime_sieve.c (sitert av num1)

Svarte 06/10/2008 kl. 20:03
kilden bruker

stemmer
7

Ved hjelp av GMP, kan man skrive følgende:

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

På min 2,33 GHz Macbook Pro, utfører det på følgende måte:

time ./a.out > /dev/null

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

Beregning 1.000.000 primtall på samme laptop:

time ./a.out > /dev/null

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

GMP er svært optimalisert for denne typen ting. Med mindre du virkelig ønsker å forstå algoritmer ved å skrive din egen, vil du bli bedt om å bruke libGMP henhold C.

Svarte 29/08/2008 kl. 07:06
kilden bruker

stemmer
4

Jeg har tilpasset kode på CodeProject å opprette følgende:

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

Testing dette på min ASP.NET Server tok rountine ca 1 minutt å kjøre.

Svarte 05/08/2008 kl. 19:55
kilden bruker

stemmer
4

Ikke effektiv i det hele tatt, men du kan bruke et vanlig uttrykk for å teste primtall.

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

Dette tester dersom det for en streng som består av k1” s, k er ikke prime (dvs. hvorvidt strengen består av ett “ 1” eller et hvilket som helst antall “ 1” s som kan uttrykkes som en n -ary produkt).

Svarte 03/08/2008 kl. 18:52
kilden bruker

stemmer
3

Her er en Sil av Eratosthenes som jeg skrev i Powershell for noen dager siden. Den har en parameter for å identifisere hvor mange primtall som skal returneres.

#
# 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
}
Svarte 07/09/2009 kl. 18:52
kilden bruker

stemmer
3

Sil av Eratosthenes er veien å gå, på grunn av sin enkelhet og hastighet. Min implementering i 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 tid til å finne primtall (på Pentium Dual Core E2140 1,6 GHz, ved hjelp av single core)

~ 4s for lim = 100 millioner

Svarte 20/08/2008 kl. 23:45
kilden bruker

stemmer
2

Den deque sil algoritmen nevnt av BenGoldberg fortjener en nærmere titt, ikke bare fordi det er svært elegant, men også fordi det kan noen ganger være nyttig i praksis (i motsetning til Sil av Atkin, som er et rent akademisk øvelse).

Den grunnleggende ideen bak deque sil algoritmen er å bruke en liten glidende sil som bare er stor nok til å inneholde minst ett separat multiplum for hver av de for tiden 'aktive' primfaktorer - dvs. de primtall som har firkantet, ikke overskrider det laveste antall dag representert ved den bevegelige sikt. En annen forskjell til SOE er at deque sikt lagrer de faktiske forhold i sporene i kompositter, ikke boolske verdier.

Algoritmen strekker seg størrelsen av siktevinduet etter behov, noe som resulterer i ganske jevn ytelse over et bredt område inntil sikten begynner å ut- over CPU-L1-buffer bart. Den siste prime som passer fullt er 25237523 (den 1,579,791st prime), noe som gir en grov omtrentlig tall for rimelig rekkevidde av algoritmen.

Algoritmen er forholdsvis enkel og robust, og det har til og med ytelse over et mye større område enn en unsegmented Eratostenes 'såld. Sistnevnte er mye raskere, så lenge det er sil passer helt inn i cache, dvs. opp til 2 ^ 16 for en odds-bare sil med byte-sized bools. Deretter ytelsen faller mer og mer, selv om det alltid er fortsatt betydelig raskere enn deque tross for handicap (i hvert fall i samlet språk som C / C ++, Pascal eller Java / C #).

Her er en gjengivelse av deque sil algoritmen i C #, fordi jeg synes at språket - til tross for sine mange feil - mye mer praktisk for prototyping algoritmer og eksperimentering enn super tungvint og pedantisk C ++. (Sidenote: Jeg bruker gratis LINQPad som gjør det mulig å hoppe rett i, uten alle messi med å sette opp prosjekter, Make-filer, kataloger eller whatnot, og det gir meg den samme grad av interaktivitet som en python spørsmål).

C # har ikke en eksplisitt deque type, men sletten List<int>fungerer godt nok for å demonstrere algoritmen.

Merk: Denne versjonen bruker ikke en deque for primtall, fordi det rett og slett ikke fornuftig å løsne sqrt (n) ut av n primtall. Hva godt ville det være å fjerne 100 primtall og la 9900? I det minste denne måten blir alle primtallene er samlet i en ryddig vektor, klar for videre bearbeiding.

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

Her er de to hjelpefunksjoner:

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

Sannsynligvis den enkleste måten å forstå algoritmen er å forestille seg det som en spesiell segmentert Sil av Eratosthenes med et segment størrelse på 1, ledsaget av en overløpsområdet der primtall kommer til å hvile når de skyter over enden av segmentet. Bortsett fra at den enkelt celle av segmentet (aka sieve[0]) har allerede blitt siktet når vi kommer til det, fordi det ble overkjørt mens det var en del av overløpsområdet.

Antallet som er representert ved sieve[0]holdes i sieve_base, selv om sieve_fronteller window_baseville også være en god navnene som tillater å trekke paralleller til Ben kode eller implementeringer av segmenterte / vindus sikter.

Hvis sieve[0]inneholder en annen verdi enn null så at verdien er en faktor sieve_base, som således kan bli gjenkjent som kompositt. Siden celle 0 er et multiplum av at faktoren er det lett å beregne sitt neste hop, som ganske enkelt er 0 pluss at faktor. Skulle denne cellen bli okkupert allerede av en annen faktor da vi bare legge den faktoren igjen, og så videre til vi finner et multiplum av faktor der ingen andre faktoren er for øyeblikket parkert (utvide silen hvis nødvendig). Dette betyr også at det ikke er behov for lagring av de aktuelle arbeids forskyvninger av de forskjellige primtall fra ett segment til neste, som i en normal segmentert sil. Når vi finner en faktor i sieve[0]dens nåværende arbeids offset er 0.

Den nåværende stats kommer inn i bildet på følgende måte. En førsteklasses kan bare bli oppdatert etter sin egen forekomst i strømmen (dvs. når det har blitt detektert som et primtall, fordi ikke er merket med en faktor), og det vil forbli strøm inntil det nøyaktige øyeblikk det sieve[0]når sin firkantet. Alle lavere multipler av denne førsteklasses må ha blitt slått av på grunn av virksomheten til mindre primtall, akkurat som i en normal Miljøstatus. Men ingen av de mindre primtall kan slå av plassen, siden den eneste faktoren av plassen er den viktigste selv og det er ennå ikke i omløp på dette punktet. Det forklarer handlinger utført av algoritmen i saken sieve_base == current_prime_squared(som innebærer sieve[0] == 0, forresten).

Nå er saken sieve[0] == 0 && sieve_base < current_prime_squareder lett å forklare: det betyr at sieve_baseikke kan være et multiplum av noen av primtall mindre enn den nåværende stats, ellers ville det ha blitt merket som kompositt. Jeg kan ikke være et høyere multiplum av den nåværende stats heller, siden verdien er mindre enn den nåværende statsPlassen. Derfor må det være en ny glanstid.

Algoritmen er åpenbart inspirert av Sil av Eratosthenes, men like selvsagt er det veldig annerledes. Eratostenes 'såld får sin høye hastigheter fra av de enkle elementære operasjoner: en enkelt indeks tilsetning og en butikk for hvert trinn i operasjonen er alt som det gjør for lange strekninger av gangen.

Her er en enkel, unsegmented Sil av Eratosthenes som jeg vanligvis bruker for sikting faktor primtall i ushort rekkevidde, dvs. opp til 2 ^ 16. For dette innlegget har jeg endret det til å fungere utover 2 ^ 16 ved å erstatte intforushort

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

Ved sikting av den første primer 10000 en typisk L1-buffer av 32 KiByte vil bli overskredet, men funksjonen er fortsatt meget hurtig (brøkdel av et millisekund, selv i C #).

Hvis du sammenligner denne koden til deque sikten så er det lett å se at driften av deque sikten er mye mer komplisert, og det kan ikke effektivt amortisere sin overhead fordi det alltid gjør på kortest mulig strekning av overganger-off på rad (nøyaktig ett enkelt krysset av, etter hopper alle multipler som har blitt krysset av allerede).

Merk: C # -kode bruker inti stedet for uintfordi nyere kompilatorer har en vane for å generere substandard kode for uint, sannsynligvis for å presse folk til signert heltall ... I C ++ versjonen av koden ovenfor brukte jeg unsignedhele, naturlig, referanse måtte være i C ++ fordi jeg ville det være basert på en tilsynelatende tilstrekkelig deque type ( std::deque<unsigned>; det var ingen ytelse gevinst fra å bruke unsigned short). Her er tallene for min Haswell laptop (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

Merk: C # ganger er ganske mye akkurat dobbelt C ++ timings, noe som er ganske bra for C # og det viser at List<int>er ikke på latsiden selv om misbrukt som deque.

Den enkle sil koden fortsatt blåser deque ut av vannet, selv om det allerede er i bruk utover sin normale arbeidsområde (L1 bufferstørrelse overskrides med 50%, med tilhørende hurtigbuffer juling). Den dominerende delen her er å lese ut av de siktede primtall, og dette er ikke påvirket mye av cache problem. I alle fall funksjonen er designet for sikting faktorene faktorer, dvs. nivå 0 i en 3-nivå sil hierarki, og vanligvis har det å komme tilbake bare noen få hundre faktorer eller et lavt antall tusen. Derav dens enkelhet.

Ytelse kan forbedres med mer enn en størrelsesorden ved hjelp av en segmentert sil og optimalisering av koden for å ekstrahere det siktede primtall (trappet mod 3 og rullet ut to ganger, eller mod 15 og utrullet gang), og enda mer ytelse kan bli presset ut av den kode ved hjelp av en mod 16 eller mod 30 hjul med alt tilbehør (dvs. fullstendig avrulling for alle rester). Noe sånt er forklart i mitt svar til Finn prime posisjonert primtall over på Code Review, der et lignende problem ble diskutert. Men det er vanskelig å se poenget i å forbedre sub-millisekund ganger for en one-off oppgave ...

For å sette ting litt i perspektiv, her er C ++ timings for sikting opp til 100 millioner:

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

Derimot, en segmentert sil i C # med noen bjeller og fløyter gjør den samme jobben i 95 ms (ingen C ++ timings tilgjengelig, siden jeg kode utfordringer bare i C # i øyeblikket).

Ting kan se desidert annerledes i et tolket språk som Python der hver operasjon har en tung kostnad og tolken overhead dverger alle forskjeller grunnet forutsagte mot mispredicted grener eller sub-syklus ops (skift, tillegg) vs multi-syklus ops (multiplikasjon og kanskje til og divisjon). Som er bundet til å erodere enkelhet nytte av Sil av Eratosthenes, og dette kan gjøre deque løsningen litt mer attraktiv.

Også mange av de timings rapportert av andre respondenter i dette emnet er sannsynligvis dominert av produksjonen tid . Det er en helt annen krig, hvor min viktigste våpen er en enkel klasse som dette:

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

Det tar mindre enn 1 ms for å skrive 10000 (sortert) tall. Det er en statisk klasse fordi det er ment for tekstlig inkludering i koding utfordring innleveringer, med et minimum av oppstyr og null overhead.

Generelt fant det å være mye raskere hvis fokusert arbeid er gjort på hele grupper, noe som betyr at sikt et visst område, og deretter trekke ut alle primtall inn i en vektor / matrise, og deretter sprenge ut hele matrisen, og deretter sile neste rekke og så videre, i stedet for mingling alt sammen. Å ha separate funksjoner fokusert på spesifikke oppgaver gjør det også lettere å mikse og matche, gjør det mulig gjenbruk, og det gjør det enklere utvikling / testing.

Svarte 19/04/2016 kl. 17:07
kilden bruker

stemmer
2

i Python

import gmpy
p=1
for i in range(10000):
    p=gmpy.next_prime(p)
    print p 
Svarte 22/02/2010 kl. 07:45
kilden bruker

stemmer
2

Den Sieve synes å være feil svar. Silen gir primtall opp til et tall N , ikke de første N primtall. Kjør @Imran eller @Andrew Szeto, og du får primtall opp til N.

Sikten kan fremdeles være brukbart hvis du fortsette å prøve sikter for stadig større antall til du treffer en viss størrelse på resultatsettet, og bruke noen caching av tall allerede oppnådd, men jeg tror det vil fortsatt være noe raskere enn en løsning som @ Pats .

Svarte 19/06/2009 kl. 18:12
kilden bruker

stemmer
2

Tilpasning og følgende på fra GateKiller , her er den endelige versjonen som jeg har brukt.

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

Det er i utgangspunktet det samme, men jeg har lagt til "break på Sqrt" forslag og endret noen av variablene rundt for å gjøre det passer bedre for meg. (Jeg var arbeider på Euler og trengte 10001th prime)

Svarte 16/02/2009 kl. 05:17
kilden bruker

stemmer
1

Bruke Sil av Eratosthenes, blir beregningen ganske raskere sammenlignet med "kjent-wide" prime tall algoritme.

Ved å bruke pseudo fra sin wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), jeg kunne ha løsningen på 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 (100.000.000) tar 2s og 330ms.

MERK : Verdien kan variere avhengig av maskinvarespesifikasjoner.

Svarte 12/05/2016 kl. 03:40
kilden bruker

stemmer
1

Her er en C ++ løsning, ved hjelp av en form for Miljøstatus:

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

Merk at denne versjonen av Sieve kan beregne primtall på ubestemt tid.

Også oppmerksom på at STL dequetar O(1)tid til å utføre push_back, pop_frontog random access skjønt subscripting.

Den resizeoperasjon tar O(n)tid, der ner antallet av elementer som tilsettes. På grunn av hvordan vi bruker denne funksjonen, kan vi behandle dette er en liten konstant.

Kroppen av whilesløyfen my_inserter utført O(log log n)tider, der ner lik den variable maybe_prime. Dette er fordi den betingelse ekspresjonen av det whilevil evaluere til sann gang for hver primfaktor maybe_prime. Se " Divisor funksjon " på Wikipedia.

Multiplisere med antall ganger my_insertkalles, viser at det skal ta O(n log log n)tid å liste nprimtall ... som er, overraskende, tiden kompleksiteten som Sil av Eratosthenes er ment å ha.

Men mens denne koden er effektiv, er det ikke det mest effektive ... Jeg vil på det sterkeste å bruke en spesialisert bibliotek for primtall generasjon, slik som primesieve . Enhver virkelig effektiv, godt optimalisert løsning, vil ta mer kode enn noen ønsker å skrive inn Stackoverflow.

Svarte 16/04/2016 kl. 18:33
kilden bruker

stemmer
1

Følgende Mathcad kode beregnet de første million primtall på under 3 minutter.

Husk at dette ville være å bruke flyttall dobler for alle tallene og er i utgangspunktet tolkes. Jeg håper syntaksen er klart.

skriv bildebeskrivelse her

Svarte 02/03/2014 kl. 01:15
kilden bruker

stemmer
1

Her er mitt VB 2008-kode, som finner alle primtall <10.000.000 i 1 min 27 sek på mitt arbeid laptop. Den hopper partall og bare ser for primtall som er <det sqrt av prøvenummer. Det er kun laget for å finne primtall fra 0 til en sentinal verdi.

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
Svarte 11/03/2011 kl. 02:25
kilden bruker

stemmer
0

Siden du ønsker første 10000 primtall bare, snarere enn koding kompleks algoritme vil jeg foreslå følgende

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

nå samtalen er prime som du trenger det

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}
Svarte 16/11/2018 kl. 05:34
kilden bruker

stemmer
0

Jeg kan gi deg noen tips, du må gjennomføre det.

  1. For hvert nummer, får halvparten av dette nummeret. For eksempel for å kontrollere 21, bare oppnå resten ved å dele den fra området 2-10.
  2. Hvis det er et oddetall, bare dividere med oddetall, og vice versa. Slik som for 21, dele med 3, 5, 7, 9 bare.

Mest effektive metoden jeg kom opp til så langt.

Svarte 29/07/2018 kl. 19:25
kilden bruker

stemmer
0

Bruke Array.prototype.find () i 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
Svarte 09/06/2018 kl. 21:49
kilden bruker

stemmer
0

Her koden som jeg gjorde:


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;
}
Svarte 20/01/2018 kl. 15:50
kilden bruker

stemmer
0

Her er min kode som finner første 10.000 primtall i 0,049655 sek på min laptop, første 1.000.000 primtall på under 6 sekunder og første 2000000 i 15 sekunder
en liten forklaring. Denne metoden bruker 2 teknikker for å finne primtall

  1. først og fremst en ikke-primtall er en kompositt av multipla av primtall slik at denne koden testen ved å dele prøven tall av mindre primtall i stedet for et hvilket som helst tall, reduseres denne beregningen av ihvertfall 10 ganger for en 4-sifret tall, og enda mer for et større antall
  2. for det andre i tillegg til å dele av prim, det bare deler av primtall som er mindre eller lik den roten av antall som testes ytterligere å redusere beregningene sterkt, fungerer dette fordi et hvilket som helst tall som er større enn roten av antallet vil ha et motstykke tall som må være mindre enn roten av antall, men siden vi har testet alle tall mindre enn roten allerede, derfor vi ikke trenger å bry seg med tall større enn roten av antall som blir testet.

Prøve utgang for første 10.000 primtall
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Her er koden i C-språk, Enter en og deretter 10 000 for å skrive ut de første 10.000 primtall.
Edit: Jeg glemte dette inneholder matematikk bibliotek, hvis du er på vinduer eller Visual Studio enn det bør være fint, men på linux må du kompilere koden ved hjelp -lm argument eller koden ikke fungerer
Eksempel: 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);
}
Svarte 06/05/2017 kl. 11:48
kilden bruker

stemmer
0

Jeg har jobbet med funn primtall for omtrent et år. Dette er hva jeg funnet å være den raskeste:

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 sekunder for å komme til 2147483629 starter på to.

Svarte 14/08/2016 kl. 00:20
kilden bruker

stemmer
0

Jeg bruker noe tid på å skrive et program beregning mye av primtall, og dette er koden jeg er vant til å beregne en tekstfil som inneholder de første 1.000.000.000 primtall. Det er på tysk, men det interessante er metoden calcPrimes(). Primtall, er lagret i en matrise som kalles Primzahlen. Jeg anbefaler en 64bit CPU fordi beregningene er med 64bit heltall.

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);
        }
    }
}
Svarte 23/04/2012 kl. 19:46
kilden bruker

stemmer
0

Jeg har skrevet dette med python, som jeg nettopp begynt å lære det, og det fungerer helt greit. Den 10.000 prime generere ved denne koden som samme som nevnt i http://primes.utm.edu/lists/small/10000.txt . For å sjekke om ner prime eller ikke, dele nav tallene fra 2til sqrt(n). Hvis noe av dette rekke nummer perfekt deler nså er det ikke prime.

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))
Svarte 27/12/2010 kl. 17:37
kilden bruker

stemmer
-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();
        }
    }
}
Svarte 08/05/2012 kl. 04:15
kilden bruker

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