SF (n) es una función que calcula el factor primo más pequeño para un número dado n.
Llamaremos a T (N) la suma de cada SF (n) con 2 <= n <= N.
T (1) = 0 (la suma está por encima de 0 sumandos)
T (2) = 2 (2 es el primer primo)
T (3) = 5 = 2 + 3
T (4) = 7 = 2 + 3 + 2
T (5) = 12 = 2 + 3 + 2 + 5
...
T (10000) = 5786451
El ganador será el que logre calcular la T (N) más grande en 60 segundos en mi propia computadora portátil (Toshiba Satellite L845, Intel Core i5, 8GB de RAM).
Current top score: Nicolás Siplis - 3.6e13 points - Nim
math
fastest-code
primes
division
Nicolás Siplis
fuente
fuente
Respuestas:
Nim, 3.6e13
Simplemente tamizar no es la mejor respuesta cuando se trata de calcular el N más alto posible ya que los requisitos de memoria son demasiado altos. Aquí hay un enfoque diferente (comenzó con Nim hace un par de días y se enamoró de la velocidad y la sintaxis, ¡cualquier sugerencia para hacerlo más rápido o más legible es bienvenida!).
fuente
return
inf
. Los procesos de expresión única regresan automáticamente.C, tamiz principal: 5e9
Resultados:
Programa:
Si bien es un programa bastante sencillo, me tomó un tiempo descubrir cómo hacer que la administración de memoria sea correcta: solo tengo suficiente memoria RAM para 1 byte por número en el rango, por lo que tuve que tener cuidado. Es un tamiz estándar de Erasthones.
fuente
Perl, factorización de fuerza bruta
Puedo llegar a aproximadamente 9e7 en 25 segundos en mi máquina Linux. Podría ser más rápido cavando en el código C, como dice después de un cheque para 2/3/5, factorizar completamente el número.
Hay formas mucho más inteligentes de hacer esto mediante tamizado. Pensé que una forma simple de fuerza bruta sería un comienzo. Esto es básicamente el problema 521 del Proyecto Euler, por cierto.
fuente
Ve, 21e9
Hace un tamiz para encontrar el factor mínimo de cada número <= N. Genera gorutinas para contar secciones del espacio numérico.
Ejecute con "go run prime.go -P 4 -N 21000000000".
Tenga en cuenta que la respuesta para N = 21e9 está entre 2 ^ 63 y 2 ^ 64, por lo que tuve que usar entradas de 64 bits sin signo para contar correctamente ...
fuente
C ++, 1 << 34 ~ 1.7e10
fuente
Java 8:
1.8e82.4e8Esta entrada no se compara con varias de las otras ya publicadas, pero quería publicar mi respuesta ya que me divertí trabajando en esto.
Las principales optimizaciones de mi enfoque son las siguientes:
T(N)
cuándoN % 2 == 1
, lo sabesT(N + 1) == T(N) + 2
. Esto me permite comenzar mi conteo a las tres y aumentar por iteración de dos en dos.Collection
tipo. Esto más que duplicó elN
que puedo alcanzar.Eso es todo lo que hay que hacer. Mi código itera de 3 en adelante por dos hasta que detecta que ha alcanzado o excedido el límite de tiempo, momento en el que escupe la respuesta.
Ejecutar en un sistema diferente (Windows 8.1, Intel Core i7 @ 2.5 GHz, 8 GB de RAM) con la última versión de Java 8 tiene resultados notablemente mejores sin cambios de código:
fuente
mayContinue()
defor loop condition
con sólo una condición simple, se puede lograr un mayor resultado. Y me gusta tu forma de calcular previamente la suma par, y luego incrementarla en dos.startTime
a unendTime
para eliminar las restas ~ 2e7, ¡pero eso me costó 3e7 de mi puntaje!System.nanoTime() - startTime < TIME_LIMIT
probaste? Porque me asegura un poco el código. No es increíblemente rápido, teniendo en cuenta el hecho, esta condición se verifica millones de veces, será un poco rápido. Una cosa que aprendí de su código es que no lo coloquefor
dentro defor
... Después de pasarfor
a otro método en mi código, la velocidad de mi código aumenta en un 40%, gracias ... Una cosa que todavía estoy descubriendo es: ¿Hicieron matrices? son mucho más eficientes que ArrayList cuando se considera el hecho de que se obtuvo millones de veces ..x2
resultado si lo implementaMultiThreading
. Pero necesitaría calcular previamente toda la matriz antes de ejecutar el cálculo Prime.mayContinue()
método al ciclo for me cuesta 8e6 de mi puntaje. Esto puede ser un problema de optimizaciones locales. Experimenté con varios tipos de datos para almacenar los números primos cuando estaba desarrollando esta solución. Solo pude alcanzar 8.8e7 conArrayList
, pero golpeé 1.8e8 (ahora 2.4e8) usando una matriz. Puede haber algunos aumentos de rendimiento relacionados con la búsqueda, pero hay aumentos definitivos para la asignación de memoria. He pensado en multiprocesar el algoritmo, pero me encontré con problemas.R, 2.5e7
Tamiz simple de Eratóstenes, vectorizado tanto como sea posible. R no está realmente diseñado para este tipo de problema y estoy bastante seguro de que puede hacerse más rápido.
fuente
sum(vec)
conduce a un desbordamiento de enteros y devuelve NA.sum(as.numeric(vec))
está sumando un vector de dobles que no se desborda (aunque podría no dar la respuesta correcta)Python, ~ 7e8
Usando un Tamiz incremental de Erathostenes. Es necesario tener cuidado de que un valor marcado esté marcado con su divisor más bajo, pero la implementación es bastante sencilla.
El tiempo se tomó con PyPy 2.6.0, la entrada se acepta como un argumento de línea de comando.
Uso de muestra
fuente
Julia, 5e7
Seguramente Julia puede hacerlo mejor, pero esto es lo que tengo por ahora. Esto hace 5e7 en aproximadamente 60 segundos en JuliaBox, pero aún no puedo probar localmente. Espero que para entonces haya pensado en un enfoque más inteligente.
Aquí estamos creando una función
lpf
que itera a través de números primos secuenciales y verifica la entrada para la divisibilidad por cada uno. La función devuelve el primer divisor encontrado, obteniendo así el mínimo factor primo.La función principal calcula
lpf
en los enteros de 2 a la entrada en paralelo y reduce el resultado sumando.fuente
Lisp común, 1e7
Opté por generar primero una lista de números primos del 2 al
(sqrt input)
, luego probar cada valor con los números primos, mientras que anteriormente probaría contra cada número hasta(sqrt input)
, lo que sería inútil (por ejemplo, si un número es divisible por 4, también es divisible por 2, por lo que ya se tiene en cuenta).Gracias a Dios por los efectos secundarios mientras estoy en eso. Remove-if reduce el tamaño de la lista y cuenta cuántos elementos se eliminaron, por lo que solo tengo que multiplicar eso por el valor que tenga el bucle y agregarlo al total acumulado.
(Dato curioso:
delete
es el equivalente destructivo deremove
, pero por cualquier razón,delete
es todo más lento queremove
en este caso).fuente
Rust 1.5e9
Un tamiz de Eratóstene muy ingenuo, pero sentí que Rust no recibió ningún amor aquí.
fuente
Java 2.14e9
Tamiz puro de Eratóstenes con la ventaja de BitSet
He calculado la suma del factor primo más pequeño hasta
Integer.MAX_VALUE - 1
justo33.89 s
. Pero no puedo continuar más grande porque cualquier otra causa conducirá a un desbordamiento de enteros en el tamaño de Bitset. Así que estoy trabajando para crear otro Bitset para el próximo conjunto de Rangos. Hasta entonces, este es el más rápido que puedo generar.fuente