Suma de factores primos más pequeños

19

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
Nicolás Siplis
fuente
Pf (2) = 2, Pf (3) = 3, Entonces, T (3) = 2 + 3 = 5. ¿Estoy en lo cierto? Estoy programado para encontrar factores primos, pero ¿podría explicar el requisito actual? Gracias
The Coder
1
@ToddLehman Estoy ejecutando cada código en mi propia computadora portátil (Sony Vaio SVF14A16CLB), por lo que si tarda menos de 60 segundos, aumentaré el número y lo disminuiré cuando tome más tiempo.
Nicolás Siplis
1
Sí, siempre que se ejecute en mi propia máquina y muestre la respuesta correcta en 60 segundos o menos, es aceptable.
Nicolás Siplis
1
Tiene 4 hilos.
Nicolás Siplis
1
¿Se permiten bibliotecas de terceros? ¿Está bien si el programa está creando hilos?
The Coder

Respuestas:

12

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!).

import math
import sequtils
import nimlongint # https://bitbucket.org/behrends/nimlongint/

proc s(n : int) : int128 =
    var x = toInt128(n)
    (x * x + x) div 2 - 1

proc sum_pfactor(N : int) : int128 =    
    var
        root = int(sqrt(float(N)))
        u = newSeqWith(root+1,false)
        cntA,cntB,sumA,sumB = newSeq[int128](root+1)
        pcnt,psum,ret : int128
        interval,finish,d,q,t : int

    for i in 0..root:
        cntA[i] = i-1
        sumA[i] = s(i)

    for i in 1..root:
        cntB[i] = N div i - 1
        sumB[i] = s(N div i)

    for p in 2..root:
        if cntA[p] == cntA[p-1]:
            continue

        pcnt = cntA[p - 1]
        psum = sumA[p - 1]
        q = p * p
        ret = ret + p * (cntB[p] - pcnt)
        cntB[1] = cntB[1] - cntB[p] + pcnt
        sumB[1] = sumB[1] - (sumB[p] - psum) * p
        interval = (p and 1) + 1
        finish = min(root,N div q)

        for i in countup(p+interval,finish,interval):

            if u[i]:
                continue

            d = i * p

            if d <= root:
                cntB[i] = cntB[i] - cntB[d] + pcnt
                sumB[i] = sumB[i] - (sumB[d] - psum) * p
            else:
                t = N div d
                cntB[i] = cntB[i] - cntA[t] + pcnt
                sumB[i] = sumB[i] - (sumA[t] - psum) * p

        if q <= root:
            for i in countup(q,finish-1,p*interval):
                u[i] = true

        for i in countdown(root,q-1):
            t = i div p
            cntA[i] = cntA[i] - cntA[t] + pcnt
            sumA[i] = sumA[i] - (sumA[t] - psum) * p

    sumB[1] + ret

var time = cpuTime()
echo(sum_pfactor(int(3.6e13))," - ",cpuTime() - time)
Nicolás Siplis
fuente
Intenté implementar el contenedor de GMP para Nim en mi código, pero simplemente no pude hacerlo funcionar (nunca antes usé GMP, por lo que ciertamente no ayudó).
Nicolás Siplis
Tampoco necesita la definición de returnin f. Los procesos de expresión única regresan automáticamente.
kirbyfan64sos
3
Este no es el primer código más rápido que Nim ha ganado por un margen notable. Puede valer la pena investigar.
primo
Tengo curiosidad por ver cómo funciona cuando utilizo GMP, pero no pude implementarlo correctamente a pesar de mis esfuerzos.
Nicolás Siplis
¡Nim definitivamente va a mi lista de aprendizaje!
Sp3000
5

C, tamiz principal: 5e9

Resultados:

$ time ./sieve 
Finding sum of lowest divisors of n = 2..5000000000
572843021990627911

real    0m57.144s
user    0m56.732s
sys 0m0.456s 

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.

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

#define LIMIT ((unsigned long long)5e9 +1)
#define ROOT_LIMIT floor(sqrt(LIMIT))

int main()
{
    printf("Finding sum of lowest divisors of n = 2..%llu\n", LIMIT - 1);
    char * found_divisor;
    found_divisor = malloc(LIMIT * sizeof(char));
    if (found_divisor == NULL) {
        printf("Error on malloc");
        return -1;
    }
    unsigned long long i;
    unsigned long long trial_div;
    unsigned long long multiple;
    unsigned long long sum = 0;

    for (i = 0; i < LIMIT; ++i) {
        found_divisor[i] = 0;
    }

    for (trial_div = 2; trial_div <= ROOT_LIMIT; ++trial_div) {
        if (found_divisor[trial_div] == 0) {
            for (multiple = trial_div * trial_div; multiple < LIMIT; multiple += trial_div) {
                if (found_divisor[multiple] == 0) {
                    found_divisor[multiple] = 1;
                    sum += trial_div;
                }
            }
        }
    }

    for (i = 2; i < LIMIT; ++i) {
        if (found_divisor[i] == 0) {
            sum += i;
        }
    }

    free(found_divisor);
    printf("%lld\n", sum);
    return 0;
}
isaacg
fuente
1
Si la memoria es una preocupación, un bit por número debería ser suficiente. Puede usar una máscara de bits para almacenar las banderas.
Reto Koradi
@RetoKoradi Desafortunadamente, eso probablemente ralentizaría el programa lo suficiente como para superar la marca de 1 minuto.
isaacg
¿Para qué necesitas afirmar.h?
Max Ried
@MaxRied Se dejó de una versión anterior.
isaacg
3

Perl, factorización de fuerza bruta

use ntheory ":all";
sub T {
  my $sum=0;
  for (1..$_[0]) {
    $sum += !($_%2) ? 2 : !($_%3) ? 3 : !($_%5) ? 5 : (factor($_))[0];
  }
  $sum
}
T(90_000_000);

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.

DanaJ
fuente
Si es útil saberlo, en Python con un tamiz solo puedo administrar T (47000). Voy a intentar algo similar a lo que estás haciendo para ver si es más rápido.
Kade
Parece que no usar un tamiz es más rápido. Pude calcular T (493900) con un método similar al tuyo.
Kade
Nunca he usado Perl antes, pero logré verificar tu respuesta, ¡te agregaré a la lista!
Nicolás Siplis
Para ser justos, esto usa mi módulo que factoriza en C (puede forzarlo a usar Perl puro para todo, pero por supuesto no es tan rápido).
DanaJ
La respuesta se puede calcular usando cualquier combinación de idiomas, así que está bien.
Nicolás Siplis
3

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

package main

import (
    "flag"
    "fmt"
    "runtime"
)

const S = 1 << 16

func main() {
    var N, P int
    flag.IntVar(&N, "N", 10000, "N")
    flag.IntVar(&P, "P", 4, "number of goroutines to use")
    flag.Parse()
    fmt.Printf("N = %d\n", N)
    fmt.Printf("P = %d\n", P)
    runtime.GOMAXPROCS(P)

    // Spawn goroutines to check sections of the number range.
    c := make(chan uint64, P)
    for i := 0; i < P; i++ {
        a := 2 + (N-1)*i/P
        b := 2 + (N-1)*(i+1)/P
        go process(a, b, c)
    }
    var sum uint64
    for i := 0; i < P; i++ {
        sum += <-c
    }
    fmt.Printf("T(%d) = %d\n", N, sum)
}

func process(a, b int, res chan uint64) {
    // Find primes up to sqrt(b).  Compute starting offsets.
    var primes []int
    var offsets []int
    for p := 2; p*p < b; p++ {
        if !prime(p) {
            continue
        }
        primes = append(primes, p)
        off := a % p
        if off != 0 {
            off = p - off
        }
        offsets = append(offsets, off)
    }

    // Allocate sieve array.
    composite := make([]bool, S)

    // Check factors of numbers up to b, a block of S at a time.
    var sum uint64
    for ; a < b; a += S {
        runtime.Gosched()
        // Check divisibility of [a,a+S) by our set of primes.
        for i, p := range primes {
            off := offsets[i]
            for ; off < S; off += p {
                if composite[off] {
                    continue // Divisible by a smaller prime.
                }
                composite[off] = true
                if a+off < b {
                    sum += uint64(p)
                }
            }
            // Remember offset for next block.
            offsets[i] = off - S
        }
        // Any remaining numbers are prime.
        for i := 0; i < S; i++ {
            if composite[i] {
                composite[i] = false // Reset for next block.
                continue
            }
            if a+i < b {
                sum += uint64(a + i)
            }
        }
    }
    res <- sum
}

func prime(n int) bool {
    for i := 2; i*i <= n; i++ {
        if n%i == 0 {
            return false
        }
    }
    return true
}

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

Keith Randall
fuente
Tuve que modificarlo para que se ejecutara en mi máquina (disminuyó N a 1e9) pero el tiempo de ejecución en sí mismo es bastante rápido, ¡buen trabajo!
Nicolás Siplis
@ NicolásSiplis: se ha corregido el uso de memoria.
Keith Randall
¡El tiempo de ejecución fue de 80 segundos, pero 1.6e10 se calculó en casi exactamente 60!
Nicolás Siplis
2

C ++, 1 << 34 ~ 1.7e10

Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz

$ g++ -O2 test3.cpp 
$ time ./a.out 
6400765038917999291

real    0m49.640s
user    0m49.610s
sys 0m0.000s
#include <iostream>
#include <vector>

using namespace std;

const long long root = 1 << 17; // must be a power of two to simplify modulo operation
const long long rootd2 = root >> 1;
const long long rootd2m1 = rootd2 - 1;
const long long mult = root; // must be less than or equal to root
const long long n = root * mult; // unused constant (function argument)

int main() {
  vector < int > sieve(rootd2, 0);
  vector < int > primes;
  vector < long long > nexts;
  primes.reserve(root);
  nexts.reserve(root);
  // initialize sum with result for even numbers
  long long sum = n / 2 * 2;
  // sieve of Erathosthenes for numbers less than root
  // all even numbers are skipped
  for(long long i = 1; i < rootd2; ++i){
    if(sieve[i]){
      sieve[i] = 0;
      continue;
    }
    const long long val = i * 2 + 1;
    primes.push_back(val);
    sum += val;
    long long j;
    for(j = (val + 1) * i; j < rootd2; j += val){
      sum += val * (1 - sieve[j]); // conditionals replaced by multiplication
      sieve[j] = 1;
    }
    nexts.push_back(j);
  }
  int k = primes.size();
  long long last = rootd2;
  // segmented sieve of Erathosthenes
  // all even numbers are skipped
  for(int segment = 2; segment <= mult; ++segment){
    last += rootd2;
    for(int i = 0; i < k; ++i){
      long long next = nexts[i];
      long long prime = primes[i];
      if(next < last){
        long long ptr = next & rootd2m1; // modulo replaced by bitmasking
        while(ptr < rootd2){
          sum += prime * (1 - sieve[ptr]); // conditionals replaced by multiplication
          sieve[ptr] = 1;
          ptr += prime;
        }
        nexts[i] = (next & ~rootd2m1) + ptr;
      }
    }
    for(int i = 0; i < rootd2; ++i){
      sum += ((segment - 1) * root + i * 2 + 1) * (1 - sieve[i]);
      sieve[i] = 0;
    }
  }
  cout << sum << endl;
}
SteelRaven
fuente
2

Java 8: 1.8e8 2.4e8

Esta 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:

  • Cada número par tiene un factor mínimo de 2, por lo que se pueden agregar de forma gratuita después de que se procese cada número impar. Básicamente, si has hecho el trabajo para calcular T(N)cuándo N % 2 == 1, lo sabes T(N + 1) == T(N) + 2. Esto me permite comenzar mi conteo a las tres y aumentar por iteración de dos en dos.
  • Almaceno mis números primos en una matriz en lugar de un Collectiontipo. Esto más que duplicó el Nque puedo alcanzar.
  • Utilizo los números primos para factorizar un número en lugar de realizar el Tamiz de Eratóstenes. Esto significa que mi almacenamiento de memoria está restringido casi por completo a mi matriz de primos.
  • Guardo la raíz cuadrada del número para el que intento encontrar el factor más pequeño. Probé el enfoque de @ user1354678 de cuadrar un factor primo cada vez, pero esto me costó alrededor de 1e7 de mi puntaje.

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.

package sum_of_smallest_factors;

public final class SumOfSmallestFactors {
    private static class Result {
        private final int number;
        int getNumber() {
            return number;
        }

        private final long sum;
        long getSum() {
            return sum;
        }


        Result(int number, long sum) {
            this.number = number;
            this.sum = sum;
        }
    }


    private static final long TIME_LIMIT = 60_000_000_000L; // 60 seconds x 1e9 nanoseconds / second


    public static void main(String[] args) {
        SumOfSmallestFactors main = new SumOfSmallestFactors();
        Result result = main.run();
        int number = result.getNumber();
        long sum = result.getSum();
        System.out.format("T(%,d) = %,d\n", number, sum);
    }


    private int[] primes = new int[16_777_216];
    private int primeCount = 0;
    private long startTime;


    private SumOfSmallestFactors() {}

    private Result run() {
        startClock();
        int number;
        long sumOfSmallestFactors = 2;
        for (number = 3; mayContinue(); number += 2) {
            int smallestFactor = getSmallestFactor(number);
            if (smallestFactor == number) {
                addPrime(number);
            }
            sumOfSmallestFactors += smallestFactor + 2;
        }
        --number;

        Result result = new Result(number, sumOfSmallestFactors);
        return result;
    }

    private void startClock() {
        startTime = System.nanoTime();
    }

    private boolean mayContinue() {
        long currentTime = System.nanoTime();
        long elapsedTime = currentTime - startTime;
        boolean result = (elapsedTime < TIME_LIMIT);
        return result;
    }

    private int getSmallestFactor(int number) {
        int smallestFactor = number;
        int squareRoot = (int) Math.ceil(Math.sqrt(number));

        int index;
        int prime = 3;
        for (index = 0; index < primeCount; ++index) {
            prime = primes[index];

            if (prime > squareRoot) {
                break;
            }

            int remainder = number % prime;
            if (remainder == 0) {
                smallestFactor = prime;
                break;
            }
        }

        return smallestFactor;
    }

    private void addPrime(int prime) {
        primes[primeCount] = prime;
        ++primeCount;
    }
}

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:

T(240,308,208) = 1,537,216,753,010,879
sadakatsu
fuente
Si se pudiera sustituir al mayContinue()de for loop conditioncon 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.
The Coder
@ user1354678, gracias por la recomendación. Curiosamente, no funcionó. Intenté variaciones de este código en una computadora diferente y descubrí que la versión publicada es la más rápida. Quitar las llamadas del reloj del código y usar un número de umbral simple me costó un poco más de un segundo. Incluso intenté cambiar mi startTimea un endTimepara eliminar las restas ~ 2e7, ¡pero eso me costó 3e7 de mi puntaje!
sadakatsu
¿Lo System.nanoTime() - startTime < TIME_LIMITprobaste? 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 coloque fordentro de for... Después de pasar fora 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 ..
The Coder
Podría lograr un x2resultado si lo implementa MultiThreading. Pero necesitaría calcular previamente toda la matriz antes de ejecutar el cálculo Prime.
The Coder
@ user1354678, mover el cheque del 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 con ArrayList, 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.
sadakatsu
1

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.

MAX <- 2.5e7
Tot <- 0
vec <- 2:MAX 
while(TRUE) {
    if (vec[1]*vec[1] > vec[length(vec)]) {
        Tot <- Tot + sum(as.numeric(vec))
        break
    }

    fact <- which(vec %% vec[1] == 0)
    Tot <- Tot + vec[1]*length(vec[fact])
    vec <- vec[-fact]
}
Tot
mawir
fuente
Punto justo sobre T. 2: MAX es un vector de enteros, por lo que para valores grandes de MAX, 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)
mawir
1

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.

from sys import argv
from math import sqrt

n = int(argv[1])
sieve = {}
imax = int(sqrt(n))

t = n & -2
i = 3
while i <= n:
  divs = sieve.pop(i, [])
  if divs:
    t += divs[-1]
    for v in divs:
      sieve.setdefault(i+v+v, []).append(v)
  else:
    t += i
    if i <= imax: sieve[i*i] = [i]
  i += 2

print t

Uso de muestra

$ pypy sum-lpf.py 10000
5786451

$ pypy sum-lpf.py 100000000
279218813374515
primo
fuente
0

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.

const PRIMES = primes(2^16)

function lpf(n::Int64)
    isprime(n) && return n
    for p in PRIMES
        n % p == 0 && return p
    end
end

function T(N::Int64)
    local x::Int64
    x = @parallel (+) for i = 2:N
        lpf(i)
    end
    x
end

Aquí estamos creando una función lpfque 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 lpfen los enteros de 2 a la entrada en paralelo y reduce el resultado sumando.

Alex A.
fuente
0

Lisp común, 1e7

(defvar input 10000000)
(defvar numbers (loop for i from 2 to input collect i))
(defvar counter)
(defvar primes)

(setf primes (loop for i from 2 to (floor (sqrt input))
    when (loop for j in primes
        do (if (eq (mod i j) 0) (return nil))
        finally (return t))
    collect i into primes
    finally (return primes)))

(format t "~A~%"    
    (loop for i in primes
        do (setf counter 0)
        summing (progn (setf numbers (remove-if #'(lambda (x) (if (eq (mod x i) 0) (progn (incf counter) t))) numbers))
                (* i counter)) into total
        finally (return (+ total (reduce #'+ numbers)))))

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: deletees el equivalente destructivo de remove, pero por cualquier razón, deletees todo más lento que removeen este caso).

Velas
fuente
Nunca he usado Lisp antes, obtengo un error de compilación cuando intento ejecutar su código: (defvar total 0) (defvar contador 0) (defvar input 10000) (números defvar (bucle para i de 2 a input collect i)) ( bucle para i de 2 a (floor (sqrt input)) (setf counter 0) summing (prog2 (nsubstitute-if 0 # '(lambda (x) (if (eq (mod xi) 0) (progn (incf counter) t ))) números) (* i contador) (setf números (eliminar 0 números))) en total finalmente (retorno (+ total (reducir # '+ números))))
Nicolás Siplis
Estoy usando SBCL 1.0.38, pero cuando llegue a casa actualizaré a la última versión y veré cómo funciona. Si lo guarda en un archivo, puede ejecutarlo con "sbcl --script <nombre de archivo>".
Velas
Lo intenté pero aún no tuve suerte, por si acaso intenté compilar en línea con Ideone pero tampoco funcionó.
Nicolás Siplis
Oh, lo siento, olvidé la palabra clave "hacer" en la línea 6. Sin embargo, debería ejecutarse ahora, darle otra oportunidad.
Velas
¡Genial, calcula 6e6 en 60 segundos en mi máquina! Por cierto, si decido ingresar mi propio código, ¿sabe si debo enviarlo como respuesta? No estoy seguro de si eso permitiría nuevas presentaciones.
Nicolás Siplis
0

Rust 1.5e9

Un tamiz de Eratóstene muy ingenuo, pero sentí que Rust no recibió ningún amor aquí.

// Expected (approximate) number of primes
fn hint(n:usize) -> usize {
    if n < 2 { 
        1
    } else {
        n / ((n as f64).ln() as usize) + 1
    }
}

fn main() {
    let n:usize = match std::env::args().nth(1) {
        Some(s) => s.parse().ok().expect("Please enter a number !"),
        None => 10000,
    };
    let mut primes = Vec::with_capacity(hint(n));
    let mut sqrt = 2;
    let s = (2..).map(|n:u32| -> u32 {
        if (sqrt * sqrt) < n {
            sqrt += 1;
        }
        let (div, unseen) = match primes.iter().take_while(|&p| *p <= sqrt).filter(|&p| n % p == 0).next() {
            Some(p) => (*p, false),
            None => (n, true),
        };
        if unseen {
            primes.push(div);
        }
        div
    }).take(n-1).fold(0, |acc, p| acc + p);
    println!("{}", s);
}
Valentin CLEMENT
fuente
0

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 - 1justo 33.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.


T(214,74,83,646) = 109931450137817286 in 33.89 s
aka
T(2,147,483,646) = 109931450137817286 in 33.89 s

import java.util.BitSet;

public class SmallPrimeFactorSum {

    static int    limit     = Integer.MAX_VALUE - 1;

    // BitSet is highly efficient against boolean[] when Billion numbers were involved
    // BitSet uses only 1 bit for each number
    // boolean[] uses 8 bits aka 1 byte for each number which will produce memory issues for large numbers
    static BitSet primes    = new BitSet(limit + 1);
    static int    limitSqrt = (int) Math.ceil(Math.sqrt(limit));

    static long   start     = System.nanoTime();

    static long   sum       = 0;

    public static void main(String[] args) {
        genPrimes();
    }

    // Generate Primes by Sieve of Eratosthenes
    // Sieve of Eratosthenes is much efficient than Sieve of Atkins as
    // Sieve of Atkins involes Division, Modulus, Multiplication, Subtraction, Addition but
    // Sieve of Eratosthenes involves only addition
    static void genPrimes() {

        // Inverse the Bit values
        primes.flip(0, limit + 1);

        // Now all Values in primes will now be true,
        // True  represents     prime number 
        // False represents not prime number

        // Set 0 and 1 as not Prime number
        primes.clear(0, 2);

        // Set all multiples of each Prime as not Prime;
        for ( int prime = 2; prime > 0 && prime <= limit && prime > 0; prime = primes.nextSetBit(prime + 1) ) {
            // Add Current Prime as its Prime factor
            sum += prime;
            // Skip marking if Current Prime > SQRT(limit)
            if ( prime > limitSqrt ) {
                continue;
            }
            // Mark Every multiple of current Prime as not Prime
            for ( int multiple = prime + prime; multiple <= limit && multiple > 0; multiple += prime ) {
                // Mark as not Prime only if it's true already
                if ( primes.get(multiple) ) {
                    // Add Current Prime as multiple's Prime factor
                    sum += prime;
                    primes.clear(multiple);
                }
            }
        }

        System.out.printf("T(%d) = %d in %.2f s", limit, sum, (System.nanoTime() - start) / 1000000000.0);
        //System.out.printf("Total Primes upto %d : %d\n", limit, primes.cardinality());
    }

}
El codificador
fuente