Apenas para antecipar alguns votos negativos de "Não queremos desafios específicos de idiomas", pedir ajuda para obter algum código é tópico e uma história diferente dos desafios.
Martin Ender
4
Precisamos preservar o algoritmo, ou apenas o resultado final?
John Dvorak
Eu começaria i a 2 para ser estritamente preciso, uma vez que este imprime 0 e 1.
histocrat
você está tentando tornar o código mais rápido ou está usando menos caracteres no código-fonte?
precisa saber é o seguinte
11
Como você está pedindo ajuda com o golfe, seria útil incluir a contagem de caracteres da sua solução atual em sua postagem (eu a considero 89).
Mark Reed
Respostas:
7
59 57 bytes
Baseado na solução @feersum, mas a verificação de primalidade pode ser ainda mais aprimorada
(Eu escrevi isso sem perceber as limitações de tamanho em números inteiros em C, portanto, provavelmente não é realmente útil para encurtar o código.)
Primeiro, uma palavra sobre algoritmo. Antes de jogar seu código, você deve pensar na melhor estratégia geral para obter o resultado.
Você está verificando a primalidade fazendo a divisão de teste - testando cada divisor potencial pde i. Isso é caro em caracteres, porque são necessários dois loops. Portanto, testar a primalidade sem um loop provavelmente salvará caracteres.
Uma abordagem geralmente mais curta é usar o Teorema de Wilson : o número né primo se e somente se
fact(n-1)%n == n-1
Onde facté a função fatorial. Desde que você está testando todos os possíveis na partir 1de 1000, é fácil evitar a implementação factorial, mantendo o controle do produto em execução Pe atualizá-lo por P*=napós cada loop. Aqui está uma implementação em Python dessa estratégia para imprimir números primos de até um milhão.
Como alternativa, o fato de o seu programa ter apenas até 1000 abre outra estratégia: o teste de primalidade de Fermat . Para alguns a, todo primo nsatisfaz
pow(a,n-1)%n == 1
Infelizmente, alguns compostos ntambém passam neste teste para alguns a. Estes são chamados pseudoprimes de Fermat . Mas, a=2e a=3não falhem juntos até n=1105, portanto, eles são suficientes para o seu objetivo de verificar os números primos até 1000. (Se 1000 fossem 100, você seria capaz de usar apenas a=2.) Portanto, verificamos a primalidade com (código não destruído)
pow(2,n-1)%n == 1 and pow(3,n-1)%n == 1
Isso também falha em reconhecer os números primos 2 e 3, portanto esses precisariam ser de caixa especial.
Essas abordagens são mais curtas? Não sei porque não codifico em C. Mas, são idéias que você deve tentar antes de escolher um pedaço de código para começar a identificar caracteres.
O teorema de Wilson não é útil em C porque ints são de 32 bits. O mesmo vale para Fermat.
precisa saber é
@feersum Oh, atire. Isso também é um problema para os fatoriais. Existe um tipo big-int?
xnor
@xnor Não embutido.
Martin Ender
11
se alguém definir fact(int n, int m) { return (n==0) ? 1 : (n*f(n-1)) % m; }, o resultado não excederá um número inteiro de 32 bits, mesmo para valores razoavelmente grandes de n. ( mé o módulo)
apnorton
@ anorton Eu acho que você quer dizer (n*fact(n-1,m)) % m. O que destaca o problema: você não pode evitar a recursão na implementação de, factporque mserá diferente para cada iteração do loop externo.
hvd 10/01
4
78 77 caracteres
(Apenas apliquei alguns truques aprendidos em outros idiomas.)
int i=0,p,c;for(;i<1e3;i++){c=0;for(p=2;p<i;)c+=i%p++<1;c||printf("%u\n",i);}
Respostas:
5957 bytesBaseado na solução @feersum, mas a verificação de primalidade pode ser ainda mais aprimorada
Editado com base nos comentários de Runer112
fonte
d=p++%999. Caso contrário, isso parece um trabalho de golfe bastante hermético!67 bytes
Em C, não há alternativa real à divisão de testes, mas certamente pode ser um pouco de golfe.
Requer declarações iniciais C99, que economizam 1 byte.
fonte
(Eu escrevi isso sem perceber as limitações de tamanho em números inteiros em C, portanto, provavelmente não é realmente útil para encurtar o código.)
Primeiro, uma palavra sobre algoritmo. Antes de jogar seu código, você deve pensar na melhor estratégia geral para obter o resultado.
Você está verificando a primalidade fazendo a divisão de teste - testando cada divisor potencial
pdei. Isso é caro em caracteres, porque são necessários dois loops. Portanto, testar a primalidade sem um loop provavelmente salvará caracteres.Uma abordagem geralmente mais curta é usar o Teorema de Wilson : o número
né primo se e somente seOnde
facté a função fatorial. Desde que você está testando todos os possíveisna partir1de1000, é fácil evitar a implementação factorial, mantendo o controle do produto em execuçãoPe atualizá-lo porP*=napós cada loop. Aqui está uma implementação em Python dessa estratégia para imprimir números primos de até um milhão.Como alternativa, o fato de o seu programa ter apenas até 1000 abre outra estratégia: o teste de primalidade de Fermat . Para alguns
a, todo primonsatisfazInfelizmente, alguns compostos
ntambém passam neste teste para algunsa. Estes são chamados pseudoprimes de Fermat . Mas,a=2ea=3não falhem juntos atén=1105, portanto, eles são suficientes para o seu objetivo de verificar os números primos até 1000. (Se 1000 fossem 100, você seria capaz de usar apenasa=2.) Portanto, verificamos a primalidade com (código não destruído)Isso também falha em reconhecer os números primos 2 e 3, portanto esses precisariam ser de caixa especial.
Essas abordagens são mais curtas? Não sei porque não codifico em C. Mas, são idéias que você deve tentar antes de escolher um pedaço de código para começar a identificar caracteres.
fonte
ints são de 32 bits. O mesmo vale para Fermat.fact(int n, int m) { return (n==0) ? 1 : (n*f(n-1)) % m; }, o resultado não excederá um número inteiro de 32 bits, mesmo para valores razoavelmente grandes den. (mé o módulo)(n*fact(n-1,m)) % m. O que destaca o problema: você não pode evitar a recursão na implementação de,factporquemserá diferente para cada iteração do loop externo.7877 caracteres(Apenas apliquei alguns truques aprendidos em outros idiomas.)
76 caracteres no modo C99
fonte
58 caracteres (ou 61 para um programa completo)
Outra reutilização da minha resposta a uma pergunta semelhante .
EDIT : pedaço de código independente, sem função para chamar.
Programa completo:
fonte
6764 bytesInspirado na solução da Alchymist:
fonte