código mais eficiente para os primeiros 10.000 números primos?

votos
49

Quero imprimir os primeiros 10000 números primos. Alguém pode me dar o código mais eficiente para isso? esclarecimentos:

  1. Não importa se o seu código é ineficiente para n> 10000.
  2. O tamanho do código não importa.
  3. Você não pode simplesmente difícil codificar os valores de qualquer maneira.
Publicado 03/08/2008 em 06:45
fonte usuário
Em outras línguas...                            


28 respostas

votos
41

O Crivo de Atkin é provavelmente o que você está procurando, seu tempo de execução limite superior é O (N / log log N).

Se você só executar os números mais 1 e 1 menos do que os múltiplos de 6, poderia ser ainda mais rápido, como todos os números primos acima de 3 são 1 fora algum múltiplo de seis. Recurso para a minha declaração

Respondeu 03/08/2008 em 07:03
fonte usuário

votos
35

Eu recomendo uma peneira, ou o Crivo de Eratóstenes ou o Crivo de Atkin.

A peneira ou Eratóstenes é provavelmente o método mais intuitiva de encontrar uma lista de números primos. Basicamente você:

  1. Anote uma lista de números de 2 a tudo o limite que você quer, digamos 1000.
  2. Dê o primeiro número que não é atravessado fora (para a primeira iteração este é 2) e cruzar fora todos os múltiplos de que o número da lista.
  3. Repita o passo 2 até chegar ao final da lista. Todos os números que não são cruzados fora são primos.

Obviamente, existem algumas otimizações que pode ser feito para tornar este algoritmo de trabalho mais rápido, mas esta é a idéia básica.

A peneira de Atkin usa uma abordagem semelhante, mas infelizmente eu não sei o suficiente sobre isso para explicar isso para você. Mas eu sei que o algoritmo I ligada leva 8 segundos para descobrir todos os números primos até 1.000 milhões em um Pentium antiga II-350

Peneira do Código Fonte Eratóstenes: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Peneira do Código Fonte Atkin: http://cr.yp.to/primegen.html

Respondeu 06/08/2008 em 00:49
fonte usuário

votos
17

Isto não é estritamente contra a restrição hardcode, mas vem terrivelmente perto. Por que não programaticamente descarregue esta lista e imprimi-lo, em vez disso?

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

Respondeu 31/08/2008 em 23:20
fonte usuário

votos
11

GateKiller , como sobre a adição de um breakpara que ifno foreachloop? Isso iria acelerar as coisas muito , porque se assim 6 é divisível por 2 você não precisa verificar com 3 e 5. (Eu votaria sua solução de qualquer maneira se eu tivesse reputação suficiente :-) ...)

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 + " ");
    }
}
Respondeu 27/08/2008 em 21:26
fonte usuário

votos
9

Em Haskell, podemos anotar quase palavra por palavra a definição matemática da peneira de Eratóstenes, " primos são números naturais acima de 1 sem quaisquer números compostos, onde compósitos são encontrados por enumeração de múltiplos de cada principais ":

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

primes !! 10000 é quase instantânea.

Referências:


O código acima é facilmente ajustado para trabalhar em apenas probabilidades, primes = 2:3:minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). Complexidade de tempo é muito melhor (para apenas cerca de um log fator acima óptima) por dobragem de uma estrutura em árvore, e a complexidade espaço é drasticamente melhorada pela produção primos de vários estágios , em

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

(Em Haskell os parênteses são usados para agrupar, uma chamada de função é representada apenas por justaposição, (:)é um contras operador para listas, e (.)é um operador de composição funcional: (f . g) x = (\y-> f (g y)) x = f (g x)).

Respondeu 24/04/2012 em 17:30
fonte usuário

votos
9

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

Da Wikipedia (que você citou) Crivo de Atkin :

Esta peneira calcula primos até N usando O(N/log log N)operações com apenas N 02/01 + O (1) bits de memória. Que é um pouco melhor do que a peneira de Eratóstenes que utiliza O(N) operações e O (N 1/2 (log log N) / log N) bits de memória (AOL Atkin, DJ Bernstein, 2004) . Estas complexidades computacionais assimptóticas incluem optimizações simples, tais como fatoração roda, e dividindo o cálculo de blocos mais pequenos.

Dada complexidade computacional assintótica ao longo O(N)(para Eratóstenes) e O(N/log(log(N)))(para Atkin) não podemos dizer (para pequenas N=10_000) que o algoritmo se implementado será mais rápido.

Achim Flammenkamp escreveu em O Crivo de Eratóstenes :

citado por:

@ num1

Para intervalos maiores cerca de 10 ^ 9, certamente para aqueles> 10 ^ 10, o Crivo de Eratóstenes é superado pelo crivo de Atkins e Bernstein, que utiliza formas quadráticas binárias irredutíveis. Consulte o seu papel para informações de fundo, bem como o n.º 5 do Ph.D. de W. Galway tese.

Portanto, para 10_000Crivo de Eratóstenes pode ser mais rápido, então Crivo de Atkin.

Para responder a OP o código é prime_sieve.c (citado por num1)

Respondeu 06/10/2008 em 21:03
fonte usuário

votos
7

Usando GMP, pode-se escrever o seguinte:

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

No meu 2.33GHz Macbook Pro, ele executa as seguintes:

time ./a.out > /dev/null

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

Calculando 1.000.000 primos no mesmo laptop:

time ./a.out > /dev/null

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

GMP é altamente otimizado para esse tipo de coisa. A menos que você realmente quer entender os algoritmos por escrever o seu próprio, você pode ser aconselhado a usar libgmp sob C.

Respondeu 29/08/2008 em 08:06
fonte usuário

votos
4

Eu adaptei o código encontrado na CodeProject para criar o seguinte:

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

Testando isso no meu servidor ASP.NET tomou a rountine cerca de 1 minuto para executar.

Respondeu 05/08/2008 em 20:55
fonte usuário

votos
4

Não é eficiente em tudo, mas você pode usar uma expressão regular para testar números primos.

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

Isto testa se, para uma corda que consiste de K1” s, k é não nobre (isto é se a cadeia é constituída por uma “ 1” ou qualquer número de “ 1” s que pode ser expresso como uma N produto -ary).

Respondeu 03/08/2008 em 19:52
fonte usuário

votos
3

Aqui está a Sieve de Eratosthenes que eu escrevi em PowerShell há poucos dias. Ele tem um parâmetro para identificar o número de números primos que devem ser devolvidos.

#
# 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
}
Respondeu 07/09/2009 em 19:52
fonte usuário

votos
3

Crivo de Eratóstenes é o caminho a percorrer, por causa da sua simplicidade e velocidade. Minha implementação em C

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

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

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

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

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

    return 0;
}

Tempo de CPU para encontrar números primos (no Pentium Dual Core E2140 de 1,6 GHz, usando único núcleo)

~ 4s para lim = 100000000

Respondeu 21/08/2008 em 00:45
fonte usuário

votos
2

O algoritmo de peneira deque mencionado por BenGoldberg merece um olhar mais atento, não só porque é muito elegante, mas também porque pode ocasionalmente ser útil na prática (ao contrário do Crivo de Atkin, que é um exercício puramente acadêmico).

A idéia básica por trás do algoritmo de peneira deque é usar uma peneira pequena, deslizando que só é grande o suficiente para conter pelo menos um múltiplo separado para cada um dos fatores primos atualmente 'ativos' - isto é, os primos cujo quadrado não exceda o menor número actualmente representado pela peneira em movimento. Uma outra diferença para a SOE é que as lojas de peneira deque os factores reais nas ranhuras de compostos, não booleanos.

O algoritmo amplia o tamanho da janela de peneira, conforme necessário, resultando em bastante mesmo desempenho em uma ampla faixa até a peneira começa exceder a capacidade de cache L1 do CPU sensivelmente. A última nobre que se encaixa totalmente é 25237523 (do primeiro-1,579,791st), o que dá um valor aproximado áspera para a faixa de operação razoável do algoritmo.

O algoritmo é bastante simples e robusto, e tem mesmo desempenho em uma gama muito maior do que uma peneira unsegmented de Eratóstenes. Este último é muito mais rápido, desde o seu crivo encaixa inteiramente no cache, isto é, até 2 ^ 16 para um odds somente peneira com bools tamanho de byte. Em seguida, seu desempenho cai mais e mais, embora ele sempre permanece significativamente mais rápido do que o deque apesar da deficiência (pelo menos em linguagens compiladas como C / C ++, Pascal ou Java / C #).

Aqui é uma rendição do algoritmo de peneira deque em C #, porque eu acho que a linguagem - apesar de suas muitas falhas - muito mais prático para os algoritmos de prototipagem e experimentação do que a supremamente pesado e pedante C ++. (Sidenote: Eu estou usando o livre LINQPad que torna possível mergulhar na direita, sem toda a confusão com a criação de projetos, makefiles, diretórios ou outros enfeites, e isso me dá o mesmo grau de interatividade como um prompt de python).

C # não tem um tipo de deque explícita, mas a planície List<int>funciona bem o suficiente para demonstrar o algoritmo.

Nota: esta versão não usa um deque para os primos, porque ele simplesmente não faz sentido a pop off sqrt (n) em n primos. Que bom seria para remover 100 primos e deixar 9900? Pelo menos esta forma, todos os números primos são recolhidos num vector puro, pronto para posterior processamento.

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

Aqui estão as duas funções auxiliares:

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

Provavelmente a maneira mais fácil de entender o algoritmo é imaginá-lo como uma peneira segmentada especial de Eratóstenes com um tamanho de segmento de 1, acompanhado por uma área de transbordo, onde os primos vêm para descansar quando eles atiram sobre a extremidade do segmento. Só que a única célula do segmento (aka sieve[0]) já foi peneirado quando chegarmos a ele, porque ele foi atropelado enquanto ele fazia parte da área de transbordamento.

O número que é representado por sieve[0]é realizada em sieve_base, embora sieve_frontou window_basetambém seria um bom nome que permitem traçar paralelos ao código de Ben ou implementações de peneiras segmentadas / janela.

Se sieve[0]contém um valor diferente de zero, em seguida, esse valor é um factor de sieve_base, o que pode, assim, ser reconhecido como compósito. Desde pilha 0 é um múltiplo desse fator é fácil calcular o seu próximo salto, que é simplesmente 0 mais esse fator. Caso essa célula ser já ocupado por um outro fator, em seguida, basta adicionar o fator de novo, e assim por diante até encontrar um múltiplo do fator de onde nenhum outro fator está estacionado (estendendo a peneira se necessário). Isto também significa que não há necessidade para armazenar os deslocamentos de trabalho actuais dos vários números primos de um segmento para o outro, como em uma peneira segmentada normal. Sempre que encontramos um fator em sieve[0], seu atual deslocada de trabalho é 0.

O atual primeiro entra em jogo da seguinte maneira. Um nobre só pode tornar-se atual depois de sua própria ocorrência na corrente (ou seja, quando ele foi detectado como um nobre, porque não marcado com um fator), e permanecerá vigente até o exato momento em que sieve[0]atinge o seu quadrado. Todos os múltiplos mais baixos deste nobre deve ter sido expulsos devido às atividades de números primos menores, assim como em um SoE normal. Mas nenhum dos números primos menores pode atacar fora da praça, uma vez que o único fator da praça é o próprio primo e ainda não está em circulação neste momento. Isso explica as ações tomadas pelo algoritmo no caso sieve_base == current_prime_squared(o que implica sieve[0] == 0, por sinal).

Agora o caso sieve[0] == 0 && sieve_base < current_prime_squaredé facilmente explicado: isso significa que sieve_basenão pode ser um múltiplo de qualquer um dos números primos menores do que o atual primeiro, ou então ele teria sido marcado como composição. Eu não posso ser um maior múltiplo do atual primeiro, dado que o seu valor é menor do que o quadrado do atual primeiro. Por isso, deve ser um novo auge.

O algoritmo é obviamente inspirado pelo Crivo de Eratóstenes, mas igualmente, obviamente, é muito diferente. O Crivo de Eratóstenes deriva sua velocidade superior da simplicidade de suas operações elementares: uma única adição de índice e uma loja para cada etapa da operação é tudo o que ele faz por longos períodos de tempo.

Aqui é um simples Sieve, unsegmented de Eratóstenes que eu uso normalmente para peneiramento primos fator na faixa ushort, ou seja, até 2 ^ 16. Para este post eu modificado para trabalhar além de 2 ^ 16, substituindo intporushort

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

Quando peneirando o primeiro 10000 prepara um cache típica L1 de 32 KiByte será ultrapassado mas a função ainda é muito rápido (fração de um milésimo de segundo, mesmo em C #).

Se você comparar este código para a peneira deque, então é fácil ver que as operações da peneira deque são muito mais complicado, e não pode efetivamente amortizar sua sobrecarga porque ele sempre faz o menor trecho possível de travessias-off em uma fileira (exatamente um único cruzamento-off, depois de pular todos os múltiplos que foram cruzados fora já).

Nota: o código C # usa intem vez de uintporque os compiladores mais novos têm o hábito de gerar o código abaixo do padrão para uint, provavelmente, a fim de empurrar as pessoas para inteiros assinados ... Na versão C ++ do código acima eu usei unsignedpor toda parte, naturalmente; o valor de referência teve de ser em C ++ porque queria ser baseada num tipo de fila de dupla extremidade adequada supostamente ( std::deque<unsigned>; houve nenhum ganho de desempenho de usar unsigned short). Aqui estão os números para o meu laptop Haswell (VC ++ 2015 / x64):

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

Nota: os C # vezes são muito bonito exatamente o dobro da C ++ horários, o que é muito bom para C # e mostra que List<int>não é desleixo mesmo se abusado como um deque.

O código peneira simples ainda sopra o deque para fora da água, mesmo que ele já está operando além de sua escala de trabalho (tamanho do cache L1 excedeu em 50%, com goleada de cache atendente) normal. A parte dominante aqui é a leitura fora dos primos peneirada, e isso não é muito afetado pelo problema cache. Em qualquer caso, a função foi concebido para peneirando os factores de factores, isto é, nível numa hierarquia 0 peneiro de 3 níveis, e tipicamente tem a retornar apenas algumas centenas de factores ou de um baixo número de milhares. Daí a sua simplicidade.

Desempenho pode ser melhorado por mais do que uma ordem de grandeza utilizando um peneiro segmentada e optimizar o código de extracção dos números primos peneiradas (degraus mod 3 e desenrolado duas vezes, ou modificação 15 e desenrolada uma vez), e ainda mais o desempenho poderia ser espremido para fora o código usando uma modificação 16 ou 30 roda da modificação com todas as guarnições (ou seja, o desenrolamento completo para todos os resíduos). Algo como isso é explicado na minha resposta à Localizar número primo posicionada primo mais sobre o Código Review, onde um problema semelhante foi discutido. Mas é difícil ver o ponto em melhorar os tempos de sub-milissegundos para uma tarefa one-off ...

Para colocar as coisas um pouco em perspectiva, aqui estão sincronismos do C ++ para peneiramento até 100.000.000:

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

Por outro lado, uma peneira segmentada em C # com alguns sinos e assobios faz o mesmo trabalho em 95 ms (sem horários C ++ disponível, uma vez que eu faço código desafia apenas em C # no momento).

O que pode parecer decididamente diferente em uma linguagem interpretada como Python onde cada operação tem um elevado custo e a sobrecarga intérprete supera todas as diferenças devido à previu vs ramos mispredicted ou ops sub-ciclo (de deslocamento, adição) vs. ops multi-ciclo (multiplicação e talvez até mesmo divisão). Que é obrigado a corroer a vantagem simplicidade do Crivo de Eratóstenes, e isso pode fazer a solução deque um pouco mais atraente.

Além disso, muitos dos horários relatados por outros entrevistados neste tópico são provavelmente dominado pelo tempo de saída . Isso é uma guerra completamente diferente, onde a minha principal arma é uma classe simples como isto:

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

Isso leva menos de 1 ms para escrever 10000 números (ordenadas). É uma classe estática, pois destina-se a inclusão de texto na codificação submissões desafio, com um mínimo de barulho e de zero em cima.

Em geral, eu achei que fosse muito mais rápido se o trabalho centrou-se é feito em lotes inteiros, ou seja, peneira um determinado intervalo, em seguida, extrair todos os números primos em um vetor / matriz, em seguida, explodir para fora toda a matriz, em seguida, peneira-se a próxima faixa e assim por diante, em vez de misturar tudo junto. Ter funções distintas focadas em tarefas específicas também torna mais fácil de misturar e combinar, permite a reutilização, e isso facilita o desenvolvimento / testes.

Respondeu 19/04/2016 em 17:07
fonte usuário

votos
2

em Python

import gmpy
p=1
for i in range(10000):
    p=gmpy.next_prime(p)
    print p 
Respondeu 22/02/2010 em 08:45
fonte usuário

votos
2

A Sieve parece ser a resposta errada. A peneira dá-lhe os números primos até um número N , não os primeiros n primos. Run @Imran ou @ Andrew Szeto, e você terá os números primos até N.

A peneira ainda pode ser útil se você continuar tentando peneiras para números cada vez maiores até que atingiu um determinado tamanho de seu conjunto de resultados, e usar alguns cache de números já obtidos, mas acredito que ele ainda não seria mais rápido se que uma solução como @ Pat de .

Respondeu 19/06/2009 em 19:12
fonte usuário

votos
2

Adaptação e na sequência de GateKiller , aqui está a versão final que eu usei.

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

É basicamente o mesmo, mas eu adicionei a sugestão de "quebrar em Sqrt" e mudou algumas das variáveis ​​em torno de torná-lo apto melhor para mim. (Eu estava trabalhando em Euler e precisava do primeiro 10001th)

Respondeu 16/02/2009 em 06:17
fonte usuário

votos
1

Usando Crivo de Eratóstenes, computação é muito mais rápido comparar com algoritmo "wide conhecida" números primos.

Usando pseudocódigo do que é wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), eu ser capaz de ter a solução em 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) toma 2s e 330ms.

NOTA : O valor pode variar dependem de especificações de hardware.

Respondeu 12/05/2016 em 03:40
fonte usuário

votos
1

Aqui é uma solução de C ++, utilizando uma forma de 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;
}

Note-se que esta versão do Sieve pode calcular números primos indefinidamente.

Além disso, note que o STL dequeleva O(1)tempo para realizar push_back, pop_fronte de acesso aleatório embora subscripting.

A resizeoperação leva O(n)tempo, onde nestá o número de elementos a ser adicionados. Devido à forma como estamos usando esta função, podemos tratar este é um pequeno constante.

O corpo do whileem laço my_inserté executado O(log log n)vezes, onde né igual à variável maybe_prime. Isso ocorre porque a expressão condição do whileavaliará como verdadeira uma vez para cada fator primordial de maybe_prime. Consulte " função Divisor " na Wikipedia.

Multiplicando pelo número de vezes que my_inserté chamado, mostra que ele deve tomar O(n log log n)tempo para listar nnúmeros primos ... que é, sem surpresa, a complexidade de tempo que o Crivo de Eratóstenes é suposto ter.

No entanto, enquanto este código é eficiente, não é o mais eficiente ... Gostaria de sugerir usando uma biblioteca especializada para a geração de primos, como primesieve . Qualquer solução verdadeiramente eficaz, bem otimizado, vai demorar mais código do que qualquer um quer digitar em Stackoverflow.

Respondeu 16/04/2016 em 18:33
fonte usuário

votos
1

O seguinte código Mathcad calculados os primeiros números primos milhão em menos de 3 minutos.

Tenha em mente que este estaria usando ponto flutuante duplica para todos os números e é basicamente interpretado. Espero que a sintaxe é clara.

digite descrição da imagem aqui

Respondeu 02/03/2014 em 02:15
fonte usuário

votos
1

Aqui está o meu código VB 2008, que localiza todos os números primos <10.000.000 em 1 min 27 seg no meu laptop de trabalho. Ele ignora até mesmo números e só procura por números primos que são <o sqrt do número de teste. Ele só é projetado para encontrar números primos de 0 a um valor sentinela.

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
Respondeu 11/03/2011 em 03:25
fonte usuário

votos
0

Desde que você quer primeiros 10000 primos única, em vez de codificação algoritmo complexo Vou sugerir o seguinte

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

agora chamada é primo que for necessário

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}
Respondeu 16/11/2018 em 05:34
fonte usuário

votos
0

Eu posso lhe dar algumas dicas, você tem que implementá-lo.

  1. Para cada número, obter a metade desse número. Por exemplo, para a verificação 21, apenas a obter o restante dividindo-à partir de gama 2-10.
  2. Se é um número ímpar, única divisão por número ímpar, e vice-versa. Tal como para 21, divide-se com 3, 5, 7, apenas 9.

método mais eficiente cheguei até tão longe.

Respondeu 29/07/2018 em 19:25
fonte usuário

votos
0

Usando o método Array.prototype.find () em 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
Respondeu 09/06/2018 em 21:49
fonte usuário

votos
0

Aqui, o código que eu fiz:


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;
}
Respondeu 20/01/2018 em 15:50
fonte usuário

votos
0

Aqui está o meu código que encontra primeiras 10.000 primos em 0,049655 segundos no meu laptop, primeiros 1.000.000 primos em menos de 6 segundos e primeira 2.000.000 em 15 segundos
uma pequena explicação. Este método usa 2 técnicas para encontrar números primos

  1. em primeiro lugar, qualquer número não-nobre é um composto de múltiplos de números primos para que este teste de código através da divisão do número de teste por números menores primos em vez de qualquer número, este diminui cálculo por pelo menos 10 vezes para um número de quatro dígitos e ainda mais para um número maior
  2. Em segundo lugar, além de dividir por nobre, ele só divide por números primos que são menores ou iguais à raiz do número que está sendo testado reduzindo ainda mais os cálculos muito, isso funciona porque qualquer número que é maior do que raiz do número terá um número equivalente que tem que ser menor do que raiz do número mas desde que nós testamos todos os números menores que já raiz, por isso não precisa se preocupar com o número maior do que a raiz do número que está sendo testado.

Exemplo de saída para o primeiro número primo 10.000
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Aqui está o código em linguagem C, Entre 1 e, em seguida, 10.000 para imprimir as primeiras 10.000 primos.
Edit: eu esqueci este contém biblioteca de matemática, se você estiver em janelas ou visual studio que isso deve ser bom, mas no linux você deve compilar o código usando argumento -lm ou o código pode não funcionar
Exemplo: 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);
}
Respondeu 06/05/2017 em 11:48
fonte usuário

votos
0

Tenho vindo a trabalhar sobre números primos encontrar para cerca de um ano. Isto é o que eu encontrei para ser o mais rápido:

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 segundos para chegar ao 2147483629 a partir de 2.

Respondeu 14/08/2016 em 00:20
fonte usuário

votos
0

I passar algum tempo escrevendo um programa de cálculo de um monte de primos e este é o código que estou utilizado para calcular um arquivo de texto contendo os primeiros 1.000.000.000 primos. É em alemão, mas a parte interessante é o método calcPrimes(). Os números primos são armazenados em um array chamado Primzahlen. Eu recomendo uma CPU de 64 bits porque os cálculos são com inteiros de 64 bits.

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);
        }
    }
}
Respondeu 23/04/2012 em 20:46
fonte usuário

votos
0

Eu escrevi isso usando python, como eu só comecei a aprender isso, e ele funciona perfeitamente bem. O primeiro-10000 gerar por este código como mesmo como mencionado no http://primes.utm.edu/lists/small/10000.txt . Para verificar se né primo ou não, dividir npelo número de 2para sqrt(n). Se nada disso gama de número divide perfeitamente n, então não é 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))
Respondeu 27/12/2010 em 18:37
fonte usuário

votos
-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();
        }
    }
}
Respondeu 08/05/2012 em 05:15
fonte usuário

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