Soma dos menores fatores primos

19

SF (n) é uma função que calcula o menor fator primo para um determinado número n.

Vamos chamar T (N) a soma de todos os SF (n) com 2 <= n <= N.

T (1) = 0 (a soma ultrapassa 0 soma)

T (2) = 2 (2 é o primeiro primo)

T (3) = 5 = 2 + 3

T (4) = 7 = 2 + 3 + 2

T (5) = 12 = 2 + 3 + 2 + 5

...

T (10000) = 5786451

O vencedor será aquele que conseguir calcular o maior T (N) em 60 segundos no meu próprio laptop (Toshiba Satellite L845, Intel Core i5, 8 GB de RAM).


Current top score: Nicolás Siplis - 3.6e13 points - Nim
Nicolás Siplis
fonte
Pf (2) = 2, Pf (3) = 3, Então, T (3) = 2 + 3 = 5. Estou certo? Programei para encontrar os principais fatores, mas você poderia elaborar sobre o requisito atual. Obrigado
The Coder
11
@ToddLehman Estou executando cada código em meu próprio laptop (Sony Vaio SVF14A16CLB), por isso, se levar menos de 60 segundos, aumentarei o número e o diminuirei quando demorar mais.
Nicolás Siplis 13/07/2015
11
Sim, desde que seja executado em minha própria máquina e produza a resposta correta em 60 segundos ou menos, é aceitável.
Nicolás Siplis 13/07/2015
11
Possui 4 threads.
Nicolás Siplis 13/07/2015
11
Bibliotecas de terceiros são permitidas? Tudo bem se o programa estiver criando threads?
The Coder

Respostas:

12

Nim, 3.6e13

Simplesmente peneirar não é a melhor resposta ao tentar calcular o N mais alto possível, pois os requisitos de memória se tornam muito altos. Aqui está uma abordagem diferente (iniciada com Nim há alguns dias e apaixonada pela velocidade e sintaxe, qualquer sugestão para torná-la mais rápida ou legível é bem-vinda!).

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
fonte
Tentei implementar o wrapper GMP para Nim no meu código, mas simplesmente não consegui fazê-lo funcionar (nunca usei o GMP antes, então isso certamente não ajudava).
Nicolás Siplis 13/07/2015
Você também não precisa do returnna fdefinição 's. Procs de expressão única retornam automaticamente.
kirbyfan64sos
3
Este não é o primeiro código mais rápido que Nim ganhou por uma margem perceptível. Pode valer a pena investigar.
primo
Estou curioso para ver como ele funciona ao usar o GMP, mas não consegui implementá-lo corretamente, apesar dos meus esforços.
Nicolás Siplis 14/07/2015
Nim definitivamente está na minha lista de aprendizado!
Sp3000
5

C, peneira 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:

Embora seja um programa bastante simples, levei um tempo para descobrir como obter o gerenciamento de memória correto - eu só tenho memória RAM suficiente para 1 byte por número no intervalo, então tive que ter cuidado. É uma peneira padrão 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
fonte
11
Se a memória é uma preocupação, um bit por número deve ser suficiente. Você pode usar uma máscara de bits para armazenar os sinalizadores.
Reto Koradi 13/07/2015
@RetoKoradi Infelizmente, isso provavelmente atrasaria o programa o suficiente para colocá-lo acima da marca de 1 minuto.
Isaacg
Para que você precisa do assert.h?
Max Ried
@MaxRied Foi deixado de uma versão inicial.
Isaacg
3

Perl, fator de força 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);

Posso chegar a 9e7 em 25 segundos na minha máquina Linux. Poderia ser mais rápido, digitando o código C, como está dizendo após uma verificação de 2/3/5, fatorar completamente o número.

Existem maneiras muito mais inteligentes de fazer isso usando peneiração. Eu pensei que uma maneira simples de força bruta seria um começo. Este é basicamente o problema do Projeto Euler 521, a propósito.

DanaJ
fonte
Se é útil saber que, em Python com uma peneira, só posso gerenciar o T (47000). Vou tentar algo semelhante ao que você está fazendo para ver se é mais rápido.
KadeJul
Parece que não usar uma peneira é mais rápido. Consegui calcular T (493900) com um método semelhante ao seu.
Kade
Nunca usei o Perl antes, mas consegui verificar sua resposta, vou adicioná-lo à lista!
Nicolás Siplis 13/07/2015
Para ser justo, isso usa meu módulo que faz o fatoramento em C (você pode forçá-lo a usar Perl puro para tudo, mas é claro que não é tão rápido).
DanaJ
A resposta pode ser calculada usando qualquer combinação de idiomas, então tudo bem.
Nicolás Siplis 13/07/2015
3

Go, 21e9

Faz uma peneira para encontrar o fator mínimo de cada número <= N. Gera goroutines para contar seções do espaço numérico.

Execute com "vá executar 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
}

Observe que a resposta para N = 21e9 está entre 2 ^ 63 e 2 ^ 64, então tive que usar ints de 64 bits não assinadas para contar corretamente ...

Keith Randall
fonte
Eu tive que modificá-lo para rodar na minha máquina (diminuiu N para 1e9), mas o tempo de execução em si é bem rápido, bom trabalho!
Nicolás Siplis 13/07/2015
@ NicolásSiplis: o uso da memória foi corrigido.
Keith Randall
O tempo de execução foi de 80 segundos, mas o 1.6e10 foi calculado em quase exatamente 60!
Nicolás Siplis 13/07/2015
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
fonte
2

Java 8: 1.8e8 2.4e8

Esta entrada não se compara a várias outras já publicadas, mas eu queria postar minha resposta, pois me diverti trabalhando nisso.

As principais otimizações da minha abordagem são as seguintes:

  • Cada número par tem um fator menor de 2, então eles podem ser adicionados gratuitamente após o processamento de cada número ímpar. Basicamente, se você fez o trabalho para calcular T(N)quando N % 2 == 1, você sabe disso T(N + 1) == T(N) + 2. Isso me permite iniciar minha contagem às três e incrementar por iteração em dois.
  • Eu armazeno meus números primos em uma matriz em vez de um Collectiontipo. Isso mais que dobrou o que Neu posso alcançar.
  • Eu uso os números primos para fatorar um número em vez de executar a Peneira de Eratóstenes. Isso significa que meu armazenamento de memória é restrito quase completamente à minha matriz de números primos.
  • Eu guardo a raiz quadrada do número para o qual estou tentando encontrar o menor fator. Tentei a abordagem do @ user1354678 de obter um fator primordial a cada vez, mas isso me custou cerca de 1e7 da minha pontuação.

Isso é tudo o que há para isso. Meu código itera de três em dois até detectar que atingiu ou excedeu o limite de tempo; nesse momento, ele fornece a resposta.

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;
    }
}

A execução em um sistema diferente (Windows 8.1, Intel core i7 a 2,5 GHz, 8 GB de RAM) com a versão mais recente do Java 8 apresenta resultados significativamente melhores, sem alterações de código:

T(240,308,208) = 1,537,216,753,010,879
sadakatsu
fonte
Se você poderia substituir o mayContinue()em for loop conditioncom apenas uma condição simples, você poderia alcançar maior resultado. E eu gosto da sua maneira de pré-calcular a soma uniforme e depois aumentar em dois.
The Coder
@ user1354678, Obrigado pela recomendação. Estranhamente, não funcionou. Tentei variações desse código em um computador diferente e descobri que a versão postada é a mais rápida. Remover as chamadas do relógio do código e usar um número simples de limiar me custou um pouco mais de um segundo. Eu até tentei mudar startTimepara um endTimepara eliminar as subtrações ~ 2e7, mas isso me custou 3e7 da minha pontuação!
Sadakatsu
Você já tentou System.nanoTime() - startTime < TIME_LIMIT, porque ele prende seu código um pouco para mim. Não é incrivelmente rápido, considerando o fato, essa condição é verificada milhões de vezes, será um pouco rápido. Uma coisa que aprendi com o seu código é: não coloque fordentro de um for.. Depois de passar forpara outro método no meu código, minha velocidade de código aumenta em 40%, obrigado. Uma coisa que ainda estou descobrindo é: Arrays são muito mais eficientes do que ArrayList quando se considera o fato de que é milhões obtida de vezes ..
a Coder
Você pode obter x2resultado se implementar MultiThreading. Mas seria necessário pré-calcular toda a matriz antes de executar o cálculo Prime.
O codificador
@ user1354678, mover a verificação do mayContinue()método para o loop for me custa 8e6 da minha pontuação. Isso pode ser um problema de otimizações locais. Eu experimentei vários tipos de dados para armazenar os primos quando desenvolvi esta solução. Eu só consegui alcançar 8.8e7 com ArrayList, mas atingi 1.8e8 (agora 2.4e8) usando uma matriz. Pode haver alguns aprimoramentos de desempenho envolvidos na pesquisa, mas há aprimoramentos definidos para a alocação de memória. Eu pensei em multi-threading o algoritmo, mas tive problemas.
Sadakatsu
1

R, 2.5e7

Peneira simples de Eratóstenes, vetorizada tanto quanto possível. O R não foi realmente projetado para esse tipo de problema e tenho certeza de que pode ser feito mais rapidamente.

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
fonte
Ponto justo sobre T. 2: MAX é um vetor de números inteiros; portanto, para grandes valores de MAX, sum(vec)leva a um excesso de número inteiro e retorna NA. sum(as.numeric(vec))é soma de um vector de duplas que não transborde (embora possa não dar a resposta certa)
mawir
1

Python, ~ 7e8

Usando uma peneira incremental de Erathostenes. É necessário tomar cuidado para que um valor marcado seja marcado com seu divisor mais baixo, mas a implementação é razoavelmente direta.

O tempo foi determinado com o PyPy 2.6.0; a entrada é aceita como argumento da linha 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 da amostra

$ pypy sum-lpf.py 10000
5786451

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

Julia, 5e7

Certamente Julia pode fazer melhor, mas é isso que tenho por enquanto. Isso faz 5e7 em cerca de 60 segundos no JuliaBox, mas ainda não posso testar localmente. Espero que até lá eu tenha pensado em uma abordagem mais 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

Aqui, estamos criando uma função lpfque itera através de números primos sequenciais e verifica a entrada quanto à divisibilidade de cada um. A função retorna o primeiro divisor encontrado, obtendo assim o menor fator primo.

A função principal calcula lpfos números inteiros de 2 à entrada em paralelo e reduz o resultado somando.

Alex A.
fonte
0

Lisp comum, 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)))))

Optei por gerar primeiro uma lista de números primos de 2 a (sqrt input)e depois testar todos os valores com os números primos, enquanto anteriormente eu testaria todos os números até (sqrt input), o que seria inútil (por exemplo, se um número é divisível por 4, também é divisível por 2, por isso já é contabilizado.)

Graças a Deus pelos efeitos colaterais enquanto estou nisso. O remove-if reduz o tamanho da lista e conta quantos elementos foram removidos, então eu apenas tenho que multiplicar por qualquer valor que o loop esteja e adicionar isso ao total em execução.

(Curiosidade: deleteé o equivalente destrutivo de remove, mas por qualquer motivo, deleteé mais lento do que removeneste caso.)

Velas
fonte
Nunca usei o Lisp antes, estou recebendo um erro do compilador ao tentar executar seu código: (total 0 do defvar) (contador 0 do defvar 0) (entrada do defvar 10000) (números do defvar 10000) (números do defvar (loop para i de 2 para entrada coletar i)) ( loop para i de 2 a (floor (entrada sqrt)) (setf counter 0) somatório (prog2 (nsubstitute-if 0 # '(lambda (x) (if (eq (mod xi) 0) (progn (contador incf) t ))) numbers) (* i counter) (setf numbers (remove 0 numbers))) no total finalmente (return (+ total (reduzir # '+ número)))))
Nicolás Siplis
Estou usando o SBCL 1.0.38, mas quando chegar em casa, atualizarei para a versão mais recente e verei como vai. Se você o salvar em um arquivo, poderá executá-lo com "sbcl --script <filename>".
Velas
Tentei, mas ainda não tive sorte, apenas no caso de tentar compilar online com o Ideone, mas isso também não funcionou.
Nicolás Siplis 13/07/2015
Oh, desculpe, esqueci a palavra-chave "do" na linha 6. Ela deve ser executada agora, porém, tente outra vez.
Velas
Ótimo, ele calcula 6e6 em 60 segundos na minha máquina! A propósito, se eu decidir inserir meu próprio código, você sabe se devo enviá-lo como resposta? Não tenho certeza se isso permitiria novos envios.
Nicolás Siplis 13/07/2015
0

Ferrugem 1.5e9

Uma peneira muito ingênua de Eratosthene, mas eu senti que Rust não recebeu nenhum amor aqui!

// 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
fonte
0

Java 2.14e9

Peneira pura de Eratóstenes com vantagem do BitSet

Eu calculei a soma do fator menor menor até Integer.MAX_VALUE - 1just in 33.89 s. Mas não posso continuar maior porque mais adiante levará ao Estouro Inteiro no Tamanho do Bitset. Então, estou trabalhando para criar outro Bitset para o próximo conjunto de intervalos. Até lá, é o mais rápido que consigo gerar.


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());
    }

}
O codificador
fonte