Código mais eficiente para o primeiro 10000 números primos?
https://stackoverflow.com/questions/622
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu quero imprimir a primeira 10000 números primos.Alguém pode me dar o código mais eficiente para isso?Esclarecimentos:
- Não importa se o seu código é ineficiente para n >10000.
- O tamanho do código, não importa.
- Você não pode simplesmente rígido código de valores em qualquer forma.
Solução
Peneira de Atkin é, provavelmente, o que você está procurando, o seu limite superior do tempo de execução é O(N/log log N).
Se você executar apenas os números 1 e 1 a menos do que os múltiplos de 6, poderia ser ainda mais rápido, como todos os números primos acima de 3 1 de de distância a partir de múltiplos de seis.De recursos para o meu instrução
Outras dicas
Eu recomendo uma peneira, o Crivo de Eratosthenes ou o Peneira de Atkin.
A peneira ou de Eratóstenes é, provavelmente, o mais intuitivo método para encontrar uma lista de números primos.Basicamente, você:
- Anote uma lista de números de 2 a qualquer limite que você deseja, vamos dizer 1000.
- Se o primeiro número que não está riscado (para a primeira iteração esta é a 2) e cruzar todos os múltiplos desse número a partir da lista.
- Repita o passo 2 até chegar ao final da lista.Todos os números que não são riscado são primos.
Obviamente há algumas otimizações que podem ser feitas para tornar este algoritmo de trabalho mais rápido, mas esta é a idéia básica.
Peneira de Atkin utiliza uma abordagem semelhante, mas infelizmente eu não sei o suficiente sobre ele para explicar para você.Mas eu sei que o algoritmo de eu vinculada leva 8 segundos para descobrir todos os números primos até 1000000000 sobre um antigo Pentium II-350
Crivo de Eratóstenes Código-Fonte: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
Peneira de Atkin Código-Fonte: http://cr.yp.to/primegen.html
Isto não é estritamente contra a codificação de restrição, mas chega muito perto.Por que não através de programação download desta lista e imprima-o, em vez disso?
GateKiller, como sobre a adição de uma break para que if no foreach loop?Isso iria acelerar as coisas um monte porque se como o 6 é divisível por 2, você não precisa verificar com 3 e 5.(Eu voto a solução de qualquer maneira se eu tivesse o suficiente reputação :-) ...)
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 + " ");
}
}
No Entanto, podemos escrever para baixo, quase palavra por palavra a definição matemática do crivo de Eratóstenes "primos são números naturais acima de 1, sem qualquer composto de números, onde os compostos são encontrados pela enumeração de cada primeiro de múltiplos":
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 funcionar em desacordo somente, primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)).Tempo de complexidade é muito melhor (para apenas cerca de um registo fator acima do ideal) dobrando-se em uma estrutura de árvore, e o espaço complexidade é drasticamente melhorada por multistage primos de produção, 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 utilizados para agrupar, uma chamada de função é representado apenas por justaposição, (:) é um contras operador de listas, e (.) é uma composição funcional do operador: (f . g) x = (\y -> f (g y)) x = f (g x)).
@Matt:log(log(10000)) é ~2
Em artigo do wikipedia (que você citou) Peneira de Atkin:
Esta peneira calcula primos até N usando
O(N/log log N)operações com só N1/2+o(1) bits de memória.Que é um pouco melhor do que a peneira de Eratóstenes, que usaO(N)operações e O(N1/2(log log N)/log N) bits de memória (A. O. L.Atkin, D. J.Bernstein, 2004).Essas anī computacional complexidades incluem simples otimizações, tais como roda fatoração e divisão do cálculo para blocos menores.
Dado assintótico complexidade computacional ao longo O(N) (por Eratóstenes) e O(N/log(log(N))) (para Atkin) não podemos dizer (para pequenas N=10_000) que o algoritmo se implementada, 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, Peneira de Eratóstenes é superado pelo Peneira de Atkins e Bernstein, que usa irredutível quadrática binária formulários.Consulte o seu papel para plano de fundo informações, bem como o n.º 5 do W.Galway Ph. D.tese.
Portanto, para a 10_000 Crivo de Eratóstenes, pode ser mais rápido, em seguida, Peneira de Atkin.
Para responder a OP o código é prime_sieve.c (citado por num1)
Usando GMP, pode 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.33 GHz Macbook Pro, ele é executado da seguinte forma:
time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s
Cálculo de 1.000.000 de primos no mesmo laptop:
time ./a.out > /dev/null
real 0m14.824s
user 0m14.606s
sys 0m0.086s
O PBF é altamente otimizado para esse tipo de coisa.A menos que você realmente queira entender os algoritmos de escrever o seu próprio, você seria aconselhável usar libGMP em C.
Não eficiente, mas você pode usar uma expressão regular para testar números primos.
/^1?$|^(11+?)\1+$/
Isso testa se, para uma string que consiste de k “1"s, k é não prime (i.é.se a seqüência de caracteres consiste em um "1"ou qualquer número de "1"s que pode ser expresso como um n-ary produto).
Eu já me adaptei código encontrado no CodeProject 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 + " ");
}
}
Testar isso no meu ASP.NET o Servidor demorou a rountine cerca de 1 minuto para executar.
Aqui está um Crivo de Eratóstenes que eu escrevi no PowerShell alguns dias atrás.Ele tem um parâmetro para identificar o número de números primos que deve ser devolvido.
#
# 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
}
Crivo de Eratosthenes é a forma de o fazer, devido a 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;
}
O Tempo de CPU para encontrar números primos (no Pentium Dual Core E2140 1.6 GHz, utilizando um único núcleo)
~ 4s para lim = 100,000,000
Adaptando-se e seguir em 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 o "quebra Sqrt" sugestão e mudaram algumas variáveis de volta para que ela se encaixe melhor para mim.(Eu estava trabalhando em Euler e necessária a 10001th prime)
A Peneira parece ser a resposta errada.A peneira dá-lhe a primes até um número N, não o primeiro N primos.Executar @Imran ou @André Szeto, e você começa a apronto até N.
A peneira pode ainda ser usado se você continuar tentando peneiras para cada vez mais em maior número até que você bata um determinado tamanho de seu conjunto de resultados, e o uso de alguns cache de números já obtidos, mas acredito que seria ainda ser mais rápido que uma solução como o @Pat.
Em Python
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
O deque peneira algoritmo mencionado por BenGoldberg merece um olhar mais atento, não só porque ele é muito elegante, mas também porque ele pode ocasionalmente ser útil na prática (ao contrário de Peneira de Atkin, que é puramente acadêmicos de exercício).
A idéia básica por trás do deque peneira algoritmo é a utilização de um pequeno deslizamento peneira que é apenas grande o suficiente para conter, pelo menos, um múltiplo separado para cada um dos actualmente "ativo" fatores primos - i.e.os primos cuja praça não exceda o número mais baixo atualmente representado pelo movimento da peneira.Outra diferença para o SoE é que o deque peneira armazena os reais fatores nos slots de compósitos, não booleanos.
O algoritmo estende-se o tamanho da peneira janela quando necessário, resultando em bastante mesmo desempenho em uma ampla gama até a peneira começa a exceder a capacidade da CPU cache L1 de forma significativa.O último primeiro-que se encaixa totalmente é 25,237,523 (a 1,579,791 st prime), que dá uma áspera valor aproximado para o razoável gama de funcionamento do algoritmo.
O algoritmo é bastante simples e robusto, e ele tem mesmo desempenho sobre uma gama muito mais ampla do que um não segmentado Crivo de Eratóstenes.O último é muito mais rápido desde a sua peneira se encaixa totalmente no cache, i.é.até 2^16 de odds somente peneira com tamanho em bytes bools.Em seguida, o seu desempenho cai mais e mais, apesar de sempre continua a ser significativamente mais rápido do que o deque apesar da desvantagem (pelo menos em linguagens compiladas como C/C++, Pascal ou Java/C#).
Aqui é uma composição do deque peneira algoritmo em C#, porque eu acho que a linguagem, apesar de suas muitas falhas - muito mais prático para a criação de protótipos de algoritmos e experimentação do que o extremamente complicado e pedante C++. (Nota:Eu estou usando o livre LINQPad o que torna possível mergulhar diretamente, sem todo o tipo de confusão com a criação de projectos, makefiles, diretórios ou coisas assim, e isso me dá o mesmo grau de interatividade como um prompt do python).
C# não tem um explícito deque tipo, mas o simples List<int> funciona bem o suficiente para demonstrar o algoritmo.
Nota:esta versão não usar um deque para os primos, porque ele simplesmente não faz sentido retirar sqrt(n) de n números primos.Que bom seria para remover a 100 primos e deixar 9900?Pelo menos desta maneira, todos os primos são coletados em um puro vetor, pronta 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 um especial segmentado Crivo de Eratóstenes com um segmento de tamanho de 1, acompanhado por um estouro de área, onde os primos vêm para descansar quando atirar sobre a extremidade do segmento.Exceto que a única célula do segmento (uma.k.um. sieve[0]) já foi peneirado quando chegamos a ele, porque fui atropelado enquanto ele fazia parte de área de excesso.
O número é representado por sieve[0] é realizada em sieve_base, apesar de sieve_front ou window_base também seria uma boa nomes que permitem estabelecer um paralelo para Ben código ou implementações de segmentados/janela peneiras.
Se sieve[0] contém um valor diferente de zero então este valor é um fator de sieve_base, que podem, assim, ser reconhecidos como composto.Desde a célula 0 é um múltiplo de que o fator é fácil calcular o seu próximo salto, que é, simplesmente, 0 mais que a factor.Deve que a célula ser ocupado já por um outro fator, em seguida, basta adicionar o fator de novo, e assim por diante, até encontrar um múltiplo do fator onde nenhum outro fator é atualmente estacionado (estendendo a peneira, se necessário).Isto também significa que não há necessidade de armazenar o trabalho atual deslocamentos de vários primos de um segmento para o outro, como em um normal segmentado peneira.Sempre que encontramos um fator sieve[0], seu trabalho atual offset for 0.
O atual primeiro-entra em jogo da seguinte maneira.Um primeiro-somente podem se tornar corrente depois da sua própria ocorrência na sequência (i.e.quando ele foi detectado como um primeiro, porque não marcado com um fator), e ele vai continuar atual, até o momento exato em que sieve[0] atinge o seu quadrado.Todos os menores múltiplos de este primeiro deve ter sido atingido, devido às atividades de menor primos, tal como um normal SoE.Mas nenhum dos primos menores podem bater fora do quadrado, uma vez que o único fator de a praça é o primeiro-si e ela ainda não está em circulação neste ponto.Que 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_base não pode ser um múltiplo de qualquer um dos primos menores do que o atual primeiro -, ou então ele teria sido marcado como composto.Eu não posso ser uma maior múltiplo de o actual primeiro-qualquer um, desde que o seu valor é menor do que o atual primeiro-praça.Por isso, deve ser uma nova prime.
O algoritmo é obviamente inspirado pelo Crivo de Eratóstenes, mas também, obviamente, é muito diferente.O Crivo de Eratóstenes deriva a sua velocidade superior a partir da simplicidade de suas operações elementares:um índice único de adição e uma loja para cada etapa da operação é tudo o que ele faz por longos períodos de tempo.
Aqui é um simples, não segmentado Crivo de Eratóstenes que eu uso normalmente para peneirar fator de apronto no ushort gama, i.é.até 2^16.Para este post eu já modificado para funcionar além de 2^16 substituindo int para ushort
static List<int> small_odd_primes_up_to (int n)
{
var result = new List<int>();
if (n < 3)
return result;
int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
var odd_composite = new bool[max_bit + 1];
for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
if (!odd_composite[i])
for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
odd_composite[j] = true;
result.Add(3); // needs to be handled separately because of the mod 3 wheel
// read out the sieved primes
for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
if (!odd_composite[i])
result.Add((i << 1) + 1);
return result;
}
Quando peneirar o primeiro 10000 prepara uma típica cache L1 de 32 KiByte vai ser ultrapassado, mas a função ainda é muito rápido (fracção de segundo, mesmo em C#).
Se você comparar este código para o deque da peneira, em seguida, é fácil ver que as operações do deque do sieve são muito mais complicadas, e não pode efetivamente amortizar a sua sobrecarga, porque ele sempre faz o menor possível trecho de travessias em uma linha (exatamente um único cruzamento-off, depois de ignorar todos os múltiplos que tenham sido riscado já).
Nota:o código C# usa int em vez de uint por que os novos compiladores têm o hábito de geração do padrão de código para uint, provavelmente a fim de empurrar as pessoas em direção inteiros assinados...Em C++ versão do código acima eu usei unsigned por toda parte, naturalmente;a referência tinha de ser em C++, porque eu queria ser baseada em uma suposta adequada deque tipo (std::deque<unsigned>;não houve ganho de desempenho utilizando unsigned short).Aqui estão os números para o meu Haswell laptop (VC++ 2015/x64):
deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms
deque vs simple: 1.729 ms vs 0.173 ms
Nota:a C# vezes são muito exatamente o dobro do C++ intervalos, o que é muito bom para C# e ìt mostra que List<int> não é desleixo mesmo se abusou como um deque.
O simples peneira código ainda sopra o deque fora da água, mesmo que ele já está operando para além do seu período normal de trabalho (faixa de tamanho da cache L1 excedido em 50%, com atendedor de cache de degradação).Dominando parte aqui é a leitura fora do crivado primos, e isso não é afetado tanto pelo problema de cache.Em qualquer caso, a função foi concebida para peneirar os fatores de fatores, i.é.nível 0 na a-3 nível de peneira hierarquia, e normalmente ele tem para retornar apenas algumas centenas de fatores ou um número baixo de milhares de pessoas.Daí a sua simplicidade.
O desempenho pode ser melhorado por mais de uma ordem de magnitude usando um segmentada peneira e optimizar o código para extrair o peneirada primes (pisou mod 3 e desenrolado, duas vezes, ou mod 15 e conduzia uma vez) , e ainda mais, o desempenho poderia ser espremido de código usando um mod 16 ou mod 30 roda com todos os acompanhamentos (i.e.total de desenrolamento para todos os resíduos).Algo como o que é explicado em minha resposta para Encontrar o primeiro posicionado número primo sobre a Revisão do Código, onde um problema semelhante foi discutido.Mas é difícil ver o ponto de melhoria sub-milissegundo vezes para uma tarefa...
Para colocar um pouco as coisas em perspectiva, aqui estão as C++ intervalos para peneirar 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, a segmentação da peneira em C# com alguns sinos e assobios faz o mesmo trabalho em 95 ms (não C++ intervalos disponíveis, desde que eu faça o código de desafios apenas em C# no momento).
As coisas podem parecer decididamente diferente em uma linguagem interpretada, como Python, onde cada operação tem um custo pesado e o intérprete sobrecarga supera todas as diferenças devidas previstos vs.mispredicted ramos ou sub-ciclo ops (shift, adição) vs.multi-ciclo de ops (multiplicação, e talvez até mesmo de divisão).Que está vinculado a corroer a simplicidade vantagem do Crivo de Eratóstenes, e isso poderia tornar o deque solução um pouco mais atraente.
Além disso, muitos dos intervalos relatado por outros entrevistados neste tópico são, provavelmente, dominado por hora de saída.Essa é uma maneira inteiramente diferente de guerra, onde minha principal arma é uma classe simples como este:
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;
}
}
}
Que leva menos de 1 ms para a escrita de 10000 (ordenados de números.É uma classe estática, pois destina-se a textual inclusão na codificação desafio de candidaturas, com um mínimo de confusão e sobrecarga de zero.
Em geral, eu achei que fosse muito mais rápido se centrou o trabalho é feito em lotes inteiros, o que significa peneira de um determinado intervalo, em seguida, extrair todos os números primos dentro de um vetor/matriz, em seguida, explosão de toda a matriz, em seguida, peneirar a próxima faixa e assim por diante, em vez de se misturar tudo junto.Tendo funções separadas centrou-se em tarefas específicas também torna mais fácil para misturar e combinar, ele permite a reutilização, e facilita o desenvolvimento/teste.
Aqui é o meu VB 2008 código, a qual encontra-se todos os números primos <10,000,000 em 1 minuto e 27 segundos no meu laptop de trabalho.Ele ignora até mesmo números e só olha para primos que são < a raiz quadrada do número de teste.Ele é projetado apenas para encontrar números primos de 0 para um sentinela valor.
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
O seguinte Mathcad código calculado o primeiro milhão de primos em menos de 3 minutos.
Tenha em mente que este estaria usando ponto flutuante duplos para todos os números e, basicamente, é interpretado.Espero que a sintaxe é claro.
Aqui é um C++ solução, através de um formulário 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 que esta versão da Peneira pode calcular números primos indefinidamente.
Observe também que a STL deque leva O(1) tempo para executar push_back, pop_front, e de acesso aleatório que subscripting.
O resize operação demora O(n) tempo, onde n é o número de elementos a ser adicionado.Devido ao modo como estamos usando esta função, pode-se tratar este é um pequeno e constante.
O corpo da while loop my_insert é executado O(log log n) vezes, onde n a variável é igual a maybe_prime.Isto porque a expressão da condição do while irá avaliar a verdade de uma vez para cada fator primordial de maybe_prime.Ver "Divisor de função"na Wikipédia.
Multiplicando pelo número de vezes que my_insert é chamado, mostra que ele deve tomar O(n log log n) tempo para lista n primos...o que é, como seria de esperar, o tempo de complexidade que o Crivo de Eratóstenes é suposto ter.
No entanto, enquanto este código é eficiente, não é o mais eficiente...Sugiro utilizar uma biblioteca especializada em primos de geração, tais como primesieve.Qualquer verdadeiramente eficiente, bem solução otimizada, vai demorar mais do que qualquer pessoa quer escrever no Stackoverflow.
Usando o Crivo de Eratóstenes, o cálculo é muito mais rápido comparar os conhecidos "-grande" números primos algoritmo.
Utilizando pseudocódigo do 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) demora 2s e 330ms.
NOTA:O valor pode variar depende de Especificações de Hardware.
Passei algum tempo a escrever um programa de cálculo de um monte de primos e este é o código que eu estou usado para calcular um arquivo de texto que contém o primeiro 1.000.000.000 primos.É em alemão, mas a parte interessante é o método de calcPrimes().Os primos são armazenados em uma matriz chamada Primzahlen.Eu recomendo um 64bit CPU porque os cálculos são com 64 bits inteiros.
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);
}
}
}
Eu escrevi isso em python, como eu só comecei a aprender com ele, e ele funciona perfeitamente bem.10.000 th primeiro-gerar por este código como o mesmo, como mencionado no http://primes.utm.edu/lists/small/10000.txt.Para verificar se n é primo ou não, dividir n pelos números de 2 para sqrt(n).Se alguma faixa de número perfeitamente divide n então não é privilegiada.
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))
Tenho vindo a trabalhar em encontrar primos por cerca de um ano.Isso é 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 partida em 2.
Aqui é o meu código que encontra
primeiro 10.000 primos em 0.049655 sec no meu laptop, 1.000.000 de primos em menos de 6 segundos e a primeira 2,000,000 em 15 segundos
Um pouco de explicação.Este método utiliza 2 técnicas para encontrar o primeiro número
- primeiro de tudo, qualquer não-número primo é um composto de múltiplos de números primos para que este código de teste dividindo-se o número de testes por menores números primos em vez de um número qualquer, isso diminui o cálculo por pelo menos 10 vezes para um número de 4 dígitos e, ainda mais, para um maior número de
- em segundo lugar, além de dividir por primeiro -, ele só divide por números primos menores ou igual a raiz do número que está sendo testado reduzindo ainda mais os cálculos muito, isso funciona porque qualquer número que é maior que a raiz de número terá uma contrapartida número que tem de ser menor que a raiz do número, mas desde que nós testamos todos os números menores que a raiz já, Portanto, não precisamos se preocupar com número maior do que a raiz do número que está sendo testado.
Exemplo de saída para 10.000 primeiro número primo
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
Aqui está o código na linguagem C,
Digite 1 e, em seguida, 10.000 para imprimir o primeiro 10.000 primos.
Editar:Eu esqueci este contém a biblioteca de matemática ,se você estiver no windows ou o visual studio de que deve ser bom, mas no linux você deve compilar o código usando -lm argumento 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);
}
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;
}
Usando a Matriz.protótipo.encontrar (em) o método 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
Eu posso lhe dar algumas dicas, você tem a implementá-lo.
- Para cada número, chegar a metade desse número.E. g.para verificar 21, apenas obter o restante, dividindo-a partir do intervalo de 2 a 10.
- Se é um número ímpar, apenas dividir pelo número ímpar, e vice-versa.Tal como para 21, dividir por 3, 5, 7, 9 apenas.
Método mais eficiente levantei-me para tão longe.
Já que você quer primeiro 10000 primos só, em vez de codificar algoritmo complexo, vou sugerir a seguir
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 é privilegiada como você precisa
for(int i=1 ; i<=1000 ; i++){
if(isPrime(i)){
//do something
}
}
using System;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int n, i = 3, j, c;
Console.WriteLine("Please enter your integer: ");
n = Convert.ToInt32(Console.ReadLine());
if (n >= 1)
{
Console.WriteLine("First " + n + " Prime Numbers are");
Console.WriteLine("2");
}
for(j=2;j<=n;)
{
for(c=2;c<=i-1;c++)
{
if(i%c==0)
break;
}
if(c==i)
{
Console.WriteLine(i);
j++;
}
i++;
}
Console.Read();
}
}
}
