¿Necesitamos preservar el algoritmo, o solo el resultado final?
John Dvorak el
Yo empezaría i en 2 sea del todo exacta, ya que este imprime 0 y 1.
histocrat
¿Está tratando de hacer que el código se ejecute más rápido o está tratando de usar menos caracteres en el código fuente?
user3629249
1
Dado que está solicitando asistencia con el golf, sería útil incluir el recuento de caracteres de su solución actual en su publicación (lo hago como 89).
Mark Reed
Respuestas:
7
59 57 bytes
Basado en la solución @feersum, pero el control de primalidad puede ser más avanzado
(Escribí esto sin darme cuenta de las limitaciones de tamaño en los enteros en C, por lo que probablemente no sea realmente útil para acortar el código).
Primero, una palabra sobre algoritmo. Antes de jugar golf su código, debe pensar en la mejor estrategia general para obtener el resultado.
Estás verificando la primalidad haciendo una división de prueba, probando cada divisor potencial pde i. Eso es costoso en los personajes porque requiere dos bucles. Por lo tanto, probar la primalidad sin un bucle probablemente ahorrará caracteres.
Un enfoque a menudo más corto es usar el Teorema de Wilson : el número nes primo si y solo si
fact(n-1)%n == n-1
¿Dónde factestá la función factorial? Como está probando todo lo posible ndesde el 1principio 1000, es fácil evitar implementar factorial al realizar un seguimiento del producto en ejecución Py actualizarlo P*=ndespués de cada ciclo. Aquí hay una implementación de Python de esta estrategia para imprimir primos de hasta un millón.
Alternativamente, el hecho de que su programa solo tenga que ser hasta 1000 abre otra estrategia: la prueba de primalidad de Fermat . Para algunos a, cada primo nsatisface
pow(a,n-1)%n == 1
Desafortunadamente, algunos compuestos ntambién pasan esta prueba para algunos a. Estos se llaman pseudoprimos de Fermat . Pero, a=2y a=3no fracasen juntos hasta n=1105, por lo que son suficientes para su propósito de verificar números primos hasta 1000. (Si 1000 en lugar de 100, solo podría usarlo a=2). Entonces, verificamos la primalidad con (código no protegido)
pow(2,n-1)%n == 1 and pow(3,n-1)%n == 1
Esto tampoco reconoce los números primos 2 y 3, por lo que estos deberían estar en mayúsculas especiales.
¿Son estos enfoques más cortos? No lo sé porque no codifico en C. Pero, son ideas que debes probar antes de decidirte por un código para comenzar a escribir caracteres.
El teorema de Wilson no es útil en C porque los ints son de 32 bits. Lo mismo va para Fermat's.
fiesta del
@feersum Oh, dispara. Eso también es un problema para los factoriales. ¿Hay un tipo big-int?
xnor
@xnor No incorporado.
Martin Ender
1
si se define fact(int n, int m) { return (n==0) ? 1 : (n*f(n-1)) % m; }, el resultado no desbordará un entero de 32 bits incluso para valores bastante grandes de n. ( mes el módulo)
apnorton
@anorton, creo que te refieres (n*fact(n-1,m)) % m. Lo que resalta el problema: no puede evitar la recurrencia en la implementación de factporque mserá diferente para cada iteración del bucle externo.
hvd
4
78 77 caracteres
(Solo apliqué algunos trucos aprendidos en otros 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);}
Respuestas:
5957 bytesBasado en la solución @feersum, pero el control de primalidad puede ser más avanzado
Editado en base a los comentarios de Runer112
fuente
d=p++%999. De lo contrario, ¡esto parece un trabajo de golf bastante hermético!67 bytes
En C no hay una alternativa real a la división de prueba, pero ciertamente se puede jugar un poco.
Requiere declaraciones iniciales C99, lo que ahorra 1 byte.
fuente
(Escribí esto sin darme cuenta de las limitaciones de tamaño en los enteros en C, por lo que probablemente no sea realmente útil para acortar el código).
Primero, una palabra sobre algoritmo. Antes de jugar golf su código, debe pensar en la mejor estrategia general para obtener el resultado.
Estás verificando la primalidad haciendo una división de prueba, probando cada divisor potencial
pdei. Eso es costoso en los personajes porque requiere dos bucles. Por lo tanto, probar la primalidad sin un bucle probablemente ahorrará caracteres.Un enfoque a menudo más corto es usar el Teorema de Wilson : el número
nes primo si y solo si¿Dónde
factestá la función factorial? Como está probando todo lo posiblendesde el1principio1000, es fácil evitar implementar factorial al realizar un seguimiento del producto en ejecuciónPy actualizarloP*=ndespués de cada ciclo. Aquí hay una implementación de Python de esta estrategia para imprimir primos de hasta un millón.Alternativamente, el hecho de que su programa solo tenga que ser hasta 1000 abre otra estrategia: la prueba de primalidad de Fermat . Para algunos
a, cada primonsatisfaceDesafortunadamente, algunos compuestos
ntambién pasan esta prueba para algunosa. Estos se llaman pseudoprimos de Fermat . Pero,a=2ya=3no fracasen juntos hastan=1105, por lo que son suficientes para su propósito de verificar números primos hasta 1000. (Si 1000 en lugar de 100, solo podría usarloa=2). Entonces, verificamos la primalidad con (código no protegido)Esto tampoco reconoce los números primos 2 y 3, por lo que estos deberían estar en mayúsculas especiales.
¿Son estos enfoques más cortos? No lo sé porque no codifico en C. Pero, son ideas que debes probar antes de decidirte por un código para comenzar a escribir caracteres.
fuente
ints son de 32 bits. Lo mismo va para Fermat's.fact(int n, int m) { return (n==0) ? 1 : (n*f(n-1)) % m; }, el resultado no desbordará un entero de 32 bits incluso para valores bastante grandes den. (mes el módulo)(n*fact(n-1,m)) % m. Lo que resalta el problema: no puede evitar la recurrencia en la implementación defactporquemserá diferente para cada iteración del bucle externo.7877 caracteres(Solo apliqué algunos trucos aprendidos en otros idiomas).
76 caracteres en modo C99
fuente
58 caracteres (o 61 para un programa completo)
Otra reutilización de mi respuesta a una pregunta similar .
EDITAR : pieza de código independiente, no hay función para llamar.
Programa completo:
fuente
6764 bytesInspirado por la solución de Alchymist:
fuente