Nejúčinnější kód prvních 10000 prvočísel?

hlasů
49

Chci vytisknout prvních 10000 prvočísel. Může mi někdo dát nejefektivnější kód na to? objasnění:

  1. Nezáleží na tom, jestli váš kód je neefektivní pro n> 10000.
  2. Velikost kódu nezáleží.
  3. Nemůžete jen těžko kód hodnoty jakýmkoliv způsobem.
Položena 03/08/2008 v 06:45
zdroj uživatelem
V jiných jazycích...                            


28 odpovědí

hlasů
41

Síto Atkin je pravděpodobně to, co hledáte, jeho horní hranici běží dobu, po kterou je O (N / log log N).

Máte-li spustit pouze čísla 1 větší a 1 menší než násobky 6, mohlo by to být ještě rychlejší, protože všechna prvočísla nad 3 jsou 1 od nějakého násobku šesti. Zdroj pro mé tvrzení

Odpovězeno 03/08/2008 v 07:03
zdroj uživatelem

hlasů
35

Doporučuji síto buď eratosthenovo síto nebo síto Atkin.

Sítko nebo Eratosthenes je pravděpodobně nejvíce intuitivní způsob, jak najít seznam prvočísel. V podstatě:

  1. Sepište seznam čísel od 2 do jakéhokoli limitu budete chtít, řekněme 1000.
  2. Vezměte první číslo, které není vyškrtnut (pro první iteraci to je 2) a odškrtnout všechny násobky tohoto čísla ze seznamu.
  3. Opakujte krok 2, dokud se nedostanete na konec seznamu. Všechna čísla, která nejsou zkřížené off je prvočíslo.

Je zřejmé, že jsou poměrně málo optimalizací, které lze udělat, aby se tento algoritmus práce rychleji, ale to je základní myšlenka.

Síto Atkin používá podobný přístup, ale bohužel nemám dost informací o tom, aby to vysvětlit. Ale vím, že algoritmus jsem propojil trvá 8 sekund zjistit všechna prvočísla až do 1000000000 na staré Pentium II-350

Eratosthenovo síto zdrojového kódu: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Síto Atkin zdrojového kódu: http://cr.yp.to/primegen.html

Odpovězeno 06/08/2008 v 00:49
zdroj uživatelem

hlasů
17

To není striktně proti omezení napevno, ale je strašně blízko. Proč ne programatically stáhnout tento seznam a tisknout to, místo toho?

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

Odpovězeno 31/08/2008 v 23:20
zdroj uživatelem

hlasů
11

GateKiller , jak se o přidání breakjako ifv foreachsmyčce? Který by urychlil věci hodně , protože v případě, jako je 6 je dělitelné 2, nemusíte kontrolovat na 3 a 5. (bych volit své řešení up stejně, kdybych měl dost pověst :-) ...)

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 + " ");
    }
}
Odpovězeno 27/08/2008 v 21:26
zdroj uživatelem

hlasů
9

V Haskell, můžeme zapsat téměř doslova matematickou definici eratosthenovo síto, „ prvočísla jsou přirozená čísla vyšší než 1 bez jakýchkoli složených čísel, kde jsou kompozity zjištěných výčet násobků každého Prime “:

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

primes !! 10000 je téměř okamžitá.

Reference:


Výše uvedený kód je snadno vylepšil na práci pouze na kurzy, primes = 2:3:minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). Časová složitost je mnohem lepší (jen asi log faktor nad optimální) ohýbáním ve stromové struktuře, a složitost prostor je výrazně zlepšena tím, výroby vícestupňového prvočísla , v

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

(V Haskell se používají závorky pro seskupení, volání funkce označované jen tím, že vedle sebe, (:)je nevýhody operátor pro seznamy, a (.)je funkční operátor složení: (f . g) x = (\y-> f (g y)) x = f (g x)).

Odpovězeno 24/04/2012 v 17:30
zdroj uživatelem

hlasů
9

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

Z článku Wikipedie (které citované) síto Atkin :

Toto síto počítá prvočísla až N použitím O(N/log log N)operace pouze s N 1/2 + O (1) bitů paměti. To je o něco lepší než síto Eratosthenes, který používá O(N) operace a O (n 1/2 (log log N) / log N) bitů paměti (AOL Atkin, DJ Bernstein, 2004) . Tyto asymptotické výpočetní složitost zahrnují jednoduché optimalizace, jako je faktorizace kola a rozdělení výpočtu na menší bloky.

Vzhledem k tomu, asymptotických výpočetní složitosti spolu O(N)(pro Eratosthenovo) a O(N/log(log(N)))(pro Atkin) nemůžeme říci (pro malé N=10_000), který algoritmus v případě realizace bude rychlejší.

Achim Flammenkamp napsal sítem Eratosthenovo :

citován:

@ num1

Pro intervalech větší o 10 ^ 9, jistě pro ty> 10 ^ 10 je eratosthenovo síto je překonán síto Atkins a Bernstein, který používá nesnížitelné binární kvadratické formy. Viz svůj papír na pozadí informací, jakož i odstavec 5 W. Galway Ph.D. teze.

Proto 10_000eratosthenovo síto může být rychlejší než síta Atkin.

Chcete-li odpovědět OP kód je prime_sieve.c (citováno num1)

Odpovězeno 06/10/2008 v 21:03
zdroj uživatelem

hlasů
7

Používání GMP by se dalo napsat následující:

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

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

Na mém 2.33GHz MacBook Pro, provede takto:

time ./a.out > /dev/null

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

Výpočet 1.000.000 prvočísla na stejném notebooku:

time ./a.out > /dev/null

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

GMP je vysoce optimalizované pro tento druh věci. Pokud opravdu chcete pochopit algoritmy psaním sami, měli byste být doporučeno používat libGMP pod C.

Odpovězeno 29/08/2008 v 08:06
zdroj uživatelem

hlasů
4

I přizpůsobili kód, který naleznete na CodeProject vytvořit následující:

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

Testování to na mém ASP.NET Server vzal rountine asi 1 minutu běžet.

Odpovězeno 05/08/2008 v 20:55
zdroj uživatelem

hlasů
4

Není efektivní vůbec, ale můžete použít regulární výraz pro testování prvočísel.

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

Tyto testy, pokud po řetězec sestávající z k1“ s, k je ne primární (tj, zda je řetězec se skládá z jedné „ 1“, nebo libovolný počet „ 1“ s, které mohou být vyjádřeny jako n -ary výrobku).

Odpovězeno 03/08/2008 v 19:52
zdroj uživatelem

hlasů
3

Zde je eratosthenovo síto, které jsem napsal v PowerShell před několika dny. To má parametr pro určení počtu prvočísel, které by měly být vráceny.

#
# 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
}
Odpovězeno 07/09/2009 v 19:52
zdroj uživatelem

hlasů
3

Eratosthenovo síto je způsob, jak jít, protože to je jednoduchost a rychlost. Moje implementace v jazyce 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 čas najít prvočísla (na Pentium Dual Core E2140 1.6 GHz, s použitím jediného jádra)

~ 4s pro lim = 100.000.000

Odpovězeno 21/08/2008 v 00:45
zdroj uživatelem

hlasů
2

Deque síto algoritmus zmínil BenGoldberg si zaslouží bližší pohled, a to nejen proto, že je to velmi elegantní, ale také proto, že to může občas být užitečné v praxi (na rozdíl od síta Atkin, což je čistě akademické cvičení).

Základní myšlenkou deque síto algoritmu je použít malý, posuvné síto, které je pouze dostatečně velká, aby obsahovaly alespoň jednu oddělenou násobek pro každou ze současnosti ‚aktivních‘ hlavních faktorů - tedy těch prvočísel, jejichž čtvereční nepřekročí nejnižší číslo v současné době reprezentován pohybující se síto. Další rozdíl k Soe je to, že sítové deque ukládá skutečné faktory do drážek kompozitu, nikoliv booleans.

Algoritmus rozšiřuje velikost okna síta podle potřeby, což má za následek poměrně dokonce výkonu v širokém rozsahu, dokud síto začíná překročení kapacity L1 cache CPU znatelně. Poslední prime, který plně zapadá je 25237523 (dále jen 1,579,791st prime), která poskytuje hrubý přibližný údaj za rozumné provozní rozsah algoritmu.

Algoritmus je poměrně jednoduchý a robustní a má i výkon v mnohem širším rozsahu, než jako unsegmented eratosthenovo síto. Ta je mnohem rychlejší, pokud její síto zcela zapadá do mezipaměti, tedy až 2 ^ 16 i pro kurzy pouze síto s bytovými velikosti bools. Pak jeho výkon klesá víc a víc, ačkoliv zůstává stále výrazně rychleji než deque navzdory handicapu (alespoň v kompilované jazyky jako C / C ++, Pascal nebo Java / C #).

Zde je ztvárnění deque algoritmu sítového v jazyce C #, protože jsem zjistil, že jazyk - navzdory mnoha nedostatkům - mnohem praktičtější pro prototypování algoritmů a experimentování než vrcholně těžkopádné a pedantský C ++. (Sidenote: Já používám bezplatný LINQPad který umožňuje potápět přímo, aniž by všechny nepořádek s nastavením projekty, Makefile, adresáře nebo kdoví co ještě, a to mi dává stejný stupeň interaktivity jako python řádku).

C # nemá explicitní typ deque ale prostý List<int>funguje docela dobře pro demonstraci algoritmu.

Poznámka: tato verze nepoužívá deque pro prvočísla, protože to prostě nedává smysl, aby pop off sqrt (N) z n prvočísel. K čemu by to bylo, aby se odstranily 100 prvočísla a odejít 9900? V nejméně Tímto způsobem se všechny připraví shromáždí v čisté vektoru, připravený pro další zpracování.

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

Zde jsou dva pomocné funkce:

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

Pravděpodobně nejjednodušší způsob, jak pochopit algoritmus je to představit jako zvláštní segmentované eratosthenovo síto s velikostí segmentu 1, doprovázené přepadové oblasti, kde se očkuje přicházejí k odpočinku, když se střílet přes konec úseku. Kromě toho, že jediná buňka segmentu (aka sieve[0]) již proseje, když se dostaneme na to, protože to přejela, když to byla část oblasti přetečení.

Číslo, které je reprezentováno sieve[0]se koná sieve_base, ačkoliv sieve_frontani window_baseby také dobré jméno, které umožňují čerpat paralely k Benově kódu nebo implementace segmentových / okénkový sít.

Pokud sieve[0]obsahuje nenulovou hodnotu, pak tato hodnota je faktor sieve_base, který tak může být rozpoznán jako kompozit. Vzhledem k tomu, buňka 0 je násobkem tohoto faktoru je snadné spočítat svou příští hop, který je prostě 0 a tento faktor. Pokud by tato buňka být obsazena již jiným faktorem pak jednoduše přidejte faktor znovu, a tak dále, dokud nenajdeme násobek faktoru, kde žádný jiný faktor v současné době zaparkovaný (prodloužení síto v případě potřeby). To také znamená, že není třeba pro ukládání aktuálních pracovních offsety různých prvočísel z jednoho segmentu do druhého, jako v normální segmentovým síto. Kdykoliv najdeme faktor sieve[0], jeho aktuální smlouvy offset je 0.

Současný předseda přichází do hry a to následujícím způsobem. Ukázkovým se může stát jediným současným po vlastním výskytu v proudu (tj když byla detekována jako primární, protože nejsou označeny faktor), a bude i nadále aktuální, dokud přesně v okamžiku, který sieve[0]dosahuje svého náměstí. Všechny nižší násobky tohoto vrcholu musí být udeřen off díky aktivitě menších připraví, stejně jako v normálním Soe. Ale žádný z menších prvočísel může udeřit mimo čtverec, protože jediným faktorem náměstí je hlavním sám a ještě není v oběhu v tomto okamžiku. Která vysvětluje kroky, které algoritmus v případě sieve_base == current_prime_squared(což znamená sieve[0] == 0, mimochodem).

Nyní případ sieve[0] == 0 && sieve_base < current_prime_squaredje snadno vysvětlit: to znamená, že sieve_basenemůže být násobkem některého z prvočísel menších než aktuální připravit, jinak by byly označeny jako kompozitní. Nemohu být vyšší násobek současného rozkvětu a to buď, protože jeho hodnota je menší než čtvercového současný předseda je. Z tohoto důvodu musí být nový předseda.

Algoritmus je zřejmě inspirován eratosthenovo síto, ale stejně tak samozřejmě je to velmi odlišné. Síto Eratosthenes odvozuje svou vynikající rychlost z jednoduchosti svých základních operací: jediný přírůstek indexu a jeden obchod pro každý krok operace je vše, co dělá pro dlouhé úseky času.

Zde je jednoduchý, unsegmented eratosthenovo síto, které normálně použít pro prosévání faktor prvočísla v rozmezí USHORT, méně než 2 ^ 16. Pro tento post jsem to upravit tak, aby pracovat za 2 ^ 16 nahrazením intproushort

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

Při prosévání první 10000 připraví typické L1 cache 32 KiByte bude překročen, ale tato funkce je stále velmi rychlý (zlomek milisekundy i v jazyce C #).

Srovnáme-li tento kód do deque síto pak je snadné vidět, že operace deque síta jsou mnohem složitější, a to nemůže účinně amortizovat své režii, protože to vždycky nejkratší úsek přechody-off v řadě (přesně jeden jediný přechod-off, po přeskočení všechny násobky, které byly zkřížené off už).

Poznámka: C # kód používá intnamísto uintprotože novější kompilátory mají ve zvyku vytvářet nestandardní kód uint, pravděpodobně s cílem tlačit lidi k podepsané celá čísla ... V C ++ verzi kódu výše jsem používal unsignedpo celou dobu, samozřejmě; měřítkem musel být v jazyce C ++, protože jsem chtěl, aby to být založena na údajně adekvátní typ deque ( std::deque<unsigned>, nebylo zvýšení výkonu používat unsigned short). Zde jsou čísla pro mé Haswell notebooku (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

Poznámka: C # časy jsou do značné míry přesně dvojnásobek C ++ časování, což je docela dobré pro C # a ukazuje, že List<int>je nebere servítky, i když zneužit jako deque.

Jednoduchý síto kód stále fouká deque z vody, i když je již v provozu mimo normální pracovní rozsah (velikost L1 mezipaměti překročena o 50%, s tím související vyrovnávací nakládačka). Dominantní část je zde čtení z proseje prvočísel, a to není ovlivněn hodně problémem mezipaměti. V každém případě byla funkce určena pro prosévání faktory faktorů, tedy úrovně 0 v hierarchii síta 3-úroveň, a obvykle se musí vrátit jen několik stovek faktory nebo nízký počet tisíců. Z tohoto důvodu jeho jednoduchost.

Výkonnost lze zlepšit o více než jeden řád pomocí segmentovaný síto a optimalizaci kódu pro vytažení proseté prvočísla (stupňové mod 3 a rozvinul dvakrát, nebo mod 15 a jednou rozvinul), a ještě výkon by mohly být vytlačeny z kód pomocí mod 16 nebo mod 30 kola se vším (tj plné rozvinutí pro všechny zbytky). Něco takového je vysvětleno v odpovědi na Nalezli vynikající umístěn prvočíslo během dne Code Review, kde byl podobný problém projednán. Ale je to těžké vidět bod při zlepšování časů milisekundové pro jednorázovou úkol ...

K tomu, aby věci trochu do souvislostí, zde je C ++ časování prosévání až 100000000:

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

Naproti tomu segmentovaná síto v jazyce C # s několika zvonky a píšťalky dělá stejnou práci v 95 ms (bez C ++ časování k dispozici, protože já kód napadá pouze v jazyce C # v tomto okamžiku).

Věci mohou vypadat rozhodně liší v interpretovaný jazyk jako je Python, kde každá operace má vysoké náklady a interpret režie převyšuje všechny rozdíly v důsledku předpokládané vs. mispredicted poboček nebo sub-cyklu ops (Shift, navíc) oproti ops multi-cyklu (násobení a snad i divize). Která je vázána na narušit jednoduchost výhodu eratosthenovo síto, a to by mohlo využít deque řešení atraktivnější trochu.

Také, mnoho z časování u jiných respondentů v tomto tématu pravděpodobně dominuje okamžiku výstupu . To je úplně jiná válka, kde je můj hlavní zbraní je jednoduchá třída takto:

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

Která trvá méně než 1 ms pro psaní 10000 (řazeno) čísla. Je to static class, protože je určen pro textovou zařazení do kódování výzvu podání, s minimálním úsilím a nulovou režii.

Obecně jsem zjistil, že je mnohem rychlejší, pokud se zaměřením práce se provádí na celých sériích, což znamená, síto určitý rozsah, pak extrahovat všechny prvočísla do vektoru / matice, pak výbuch z celé pole, pak se proseje další rozsah a tak dále, místo mísí všechno dohromady. Mají samostatné funkce zaměřené na konkrétní úkoly také usnadňuje kombinovat, umožňuje opakované použití, a to usnadňuje vývoj / testování.

Odpovězeno 19/04/2016 v 17:07
zdroj uživatelem

hlasů
2

v Pythonu

import gmpy
p=1
for i in range(10000):
    p=gmpy.next_prime(p)
    print p 
Odpovězeno 22/02/2010 v 08:45
zdroj uživatelem

hlasů
2

Síto se zdá být špatná odpověď. Sítko vám dává prvočísla až do řady N , nikoli prvních N prvočísla. Run @Imran nebo @Andrew Szeto a dostanete prvočísla až N.

Sítko mohlo být ještě použitelný, když se snaží udržet síta o stále větším počtu, dokud nenarazíte určité velikosti vaší sady výsledků a použít nějaký mezipaměti čísel již získaných, ale domnívám se, že by ještě rychleji než řešení, jako @ Pat ,

Odpovězeno 19/06/2009 v 19:12
zdroj uživatelem

hlasů
2

Přizpůsobení a v návaznosti na GateKiller , zde je finální verze, které jsem používal.

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

Je to v podstatě stejné, ale jsem přidal návrh „rozbít na Sqrt“ a změnila některá z proměnných kolem, aby se to hodí lépe pro mě. (Byl jsem pracoval na Euler a potřeboval 10001th prime)

Odpovězeno 16/02/2009 v 06:17
zdroj uživatelem

hlasů
1

Používání eratosthenovo síto, výpočet je mnohem rychleji v porovnání s „známý v celé“ prvočísla algoritmu.

Použitím pseudocode ze je to wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), budu moci mít řešení na C #.

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

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

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

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

    return primes.ToArray();
}

GetPrimes (100000000) trvá 2s a 330ms.

Poznámka : Hodnota může lišit dle specifikace hardwaru.

Odpovězeno 12/05/2016 v 03:40
zdroj uživatelem

hlasů
1

Zde je C ++ řešení, používat formu 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;
}

Všimněte si, že tato verze sítu může spočítat prvočísla do nekonečna.

Také si všimněte, STK dequebere O(1)čas na provedení push_back, pop_fronta random access když indexování.

resizeOperace trvá O(n)dobu, kdy nje počet prvků přidávaná. V důsledku toho, jak jsme pomocí této funkce můžeme léčit je to malý konstantní.

Tělo whileve smyčce my_insertse provede O(log log n)třikrát, kde nse rovná proměnnou maybe_prime. Důvodem je, že stav vyjádřením whilevyhodnotí na true jednou pro každou primární faktor maybe_prime. Viz „ Funkce dělitel “ na Wikipedii.

Vynásobením počtu případů, kdy my_insertse nazývá, ukazuje, že by měla trvat O(n log log n)čas na seznam nprvočísla ... což je, nepřekvapivě, časová složitost, která má sítu Eratosthenovo mít.

I když tento kód je efektivní, to není nejefektivnější ... Chtěl bych důrazně doporučujeme použít specializovanou knihovnu pro generování prvočísel, jako je primesieve . Jakákoliv vskutku účinná, dobře optimalizované řešení, bude trvat více kódu než někdo chce psát do StackOverflow.

Odpovězeno 16/04/2016 v 18:33
zdroj uživatelem

hlasů
1

Následující kód Mathcad vypočítá první milion prvočísla za méně než 3 minuty.

Mějte na paměti, že toto by se používat s plovoucí desetinnou čárkou zdvojnásobí pro všechna čísla a je v podstatě interpretována. Doufám, že syntaxe je jasné.

zadejte popis obrázku zde

Odpovězeno 02/03/2014 v 02:15
zdroj uživatelem

hlasů
1

Zde je můj VB 2008 kód, který nalezne všechny prvočísla <10.000.000 1 min 27 sek na mém pracovním notebooku. Přeskočí sudá čísla a hledá pouze pro prvočísla, které jsou <sqrt zkušebního čísla. Je navržen tak, jen aby zjistil, prvočísla od 0 do Sentinal hodnotu.

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
Odpovězeno 11/03/2011 v 03:25
zdroj uživatelem

hlasů
0

Vzhledem k tomu, budete chtít nejprve 10000 prvočísla jen, spíše než kódování složitý algoritmus budu naznačují následující

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

Nyní volání je prvočíslo, jak ji budete potřebovat

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}
Odpovězeno 16/11/2018 v 05:34
zdroj uživatelem

hlasů
0

Můžu vám dát několik tipů, musíte ji implementovat.

  1. Pro každé číslo, dostanete polovinu tohoto počtu. Například pro kontrolu 21, pouze získat zbytek tím, že jej dělí od rozsahu 2-10.
  2. Pokud je jeho liché číslo, pouze vydělte lichým číslem, a vice versa. Jako je 21, rozdělí se 3, 5, 7, 9, pouze.

Nejúčinnější metodou jsem až tak daleko.

Odpovězeno 29/07/2018 v 19:25
zdroj uživatelem

hlasů
0

Pomocí metody Array.prototype.find () v jazyce 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
Odpovězeno 09/06/2018 v 21:49
zdroj uživatelem

hlasů
0

Zde kód, který jsem udělal:


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;
}
Odpovězeno 20/01/2018 v 15:50
zdroj uživatelem

hlasů
0

Zde je můj kód, který nalezne první 10.000 prvočísla v 0.049655 sekund na mém notebooku, první 1.000.000 prvočísla za méně než 6 sekund a první 2.000.000 15 sekund
Trochu vysvětlení. Tato metoda používá 2 techniky najít prvočíslo

  1. především jakýkoli non-prvočísla je kompozitní násobků prvočísel, takže tento test kód vydělením testovací číslo menší prvočísel místo libovolného počtu, to snižuje výpočty atleast 10 krát pro řadu 4 číslice a ještě více pro větší počet
  2. za druhé kromě dělením připravit, se rozdělí pouze prvočísel, které jsou menší nebo rovné kořenové počtu testovaného dále snižuje výpočty značně, to funguje, protože jakékoliv číslo, které je větší než odmocninou počtu bude mít řadu protějšek, který musí být menší než odmocninou počtu, ale protože jsme testovali všechna čísla menší než kořen již Proto jsme se nemusí obtěžovat s číslem větším než je kořen číslo je testován.

Ukázkový výstup pro první 10,000 prvočíslo
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Zde je kód v jazyce C, zadejte 1 a potom 10.000 vytisknout prvních 10.000 prvočísla.
Edit: Zapomněl jsem, že to obsahuje matematické knihovny, pokud jste na oknech nebo Visual Studio, než které by měly být v pořádku, ale v Linuxu je třeba sestavit kód pomocí -lm argumentu nebo kód nemusí fungovat
Příklad: 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);
}
Odpovězeno 06/05/2017 v 11:48
zdroj uživatelem

hlasů
0

Byl jsem pracoval na vyhledávacích připraví asi rok. To je to, co jsem zjistil, že je nejrychlejší:

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

1902465190909 nano sekund se dostat do 2147483629 počínaje 2.

Odpovězeno 14/08/2016 v 00:20
zdroj uživatelem

hlasů
0

I strávit nějaký čas psaní programu výpočetní mnoho prvočísel, což je kód jsem použita k výpočtu textového souboru, který obsahuje prvních 1.000.000.000 prvočísla. To je v němčině, ale zajímavá část je metoda calcPrimes(). Tyto prvočísla jsou uloženy v poli s názvem Primzahlen. Doporučuji 64bit procesor, protože výpočty jsou s 64bitových celých čísel.

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);
        }
    }
}
Odpovězeno 23/04/2012 v 20:46
zdroj uživatelem

hlasů
0

Napsal jsem to pomocí python, jak jsem právě začal ho učit, a funguje to naprosto v pořádku. 10000. prime generování tohoto kódu stejné jak je uvedeno v http://primes.utm.edu/lists/small/10000.txt . Chcete-li zjistit, zda nje prvočíslo nebo ne, dělit nčísly od 2do sqrt(n). Pokud se některý z této řady počtu dokonale rozděluje npak to není prvočíslo.

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))
Odpovězeno 27/12/2010 v 18:37
zdroj uživatelem

hlasů
-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();
        }
    }
}
Odpovězeno 08/05/2012 v 05:15
zdroj uživatelem

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