Сумма наименьших простых факторов

19

SF (n) - это функция, которая вычисляет наименьший простой множитель для данного числа n.

Мы будем называть T (N) суммой каждого SF (n) с 2 <= n <= N.

T (1) = 0 (сумма превышает 0 слагаемых)

T (2) = 2 (2 - первое простое число)

Т (3) = 5 = 2 + 3

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

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

...

Т (10000) = 5786451

Победителем станет тот, кому удастся вычислить наибольшее значение T (N) за 60 секунд на моем собственном ноутбуке (Toshiba Satellite L845, Intel Core i5, 8 ГБ ОЗУ).


Current top score: Nicolás Siplis - 3.6e13 points - Nim
Николас Сиплис
источник
Pf (2) = 2, Pf (3) = 3, поэтому T (3) = 2 + 3 = 5. Я прав? Я запрограммирован, чтобы найти основные факторы, но не могли бы вы уточнить о текущем требовании. Спасибо
Кодер
1
@ToddLehman Я запускаю каждый код на своем ноутбуке (Sony Vaio SVF14A16CLB), поэтому, если это займет менее 60 секунд, я увеличу число и уменьшу его, когда это займет больше времени.
Николас Сиплис
1
Да, до тех пор , как он работает на своей машине и выдает правильный ответ в течение 60 секунд или меньше, это приемлемо.
Николас Siplis
1
Имеет 4 темы.
Николас Siplis
1
Разрешены ли сторонние библиотеки? Это нормально , если программа создания потоков?
Кодер

Ответы:

12

Nim, 3.6e13

Простое просеивание - не лучший ответ при попытке вычислить максимально возможное значение N, поскольку требования к памяти становятся слишком высокими. Вот другой подход (начатый с Nim пару дней назад и влюбленный в скорость и синтаксис, любые предложения, чтобы сделать его более быстрым или более читабельным, приветствуются!).

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)
Николас Сиплис
источник
Я пытался внедрить обертку GMP для Nim в свой код, но просто не мог заставить ее работать (никогда раньше не использовал GMP, так что это, конечно, не помогло).
Николас Сиплис
Кроме того, не нужно returnв fопределении «S. Процедуры с одним выражением автоматически возвращаются.
kirbyfan64sos
3
Это не первый быстрый код , который Nim выиграл заметным отрывом. Может быть стоит исследовать.
прима
Мне любопытно посмотреть, как он работает при использовании GMP, но не смог правильно его реализовать, несмотря на мои усилия.
Николас Siplis
Nim определенно идет на моем освоении списка!
Sp3000
5

C, Prime Сито: 5e9

Результаты:

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

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

Программа:

Хотя это довольно простая программа, мне потребовалось некоторое время, чтобы понять, как правильно управлять памятью - у меня достаточно оперативной памяти только на 1 байт на число в диапазоне, поэтому я должен был быть осторожным. Это стандартное сито 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
источник
1
Если память является проблемой, один бит на число должно быть достаточно. Вы можете использовать битовую маску для хранения флагов.
Рето Коради
@RetoKoradi К сожалению, это, вероятно , замедлить работу программы достаточно , чтобы поставить его на 1 - й минуте.
isaacg
Для чего вам нужен assert.h?
Макс Ried
@MaxRied Он остался от версии earlie.
Исаак
3

Perl, перебор факторинг

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

Я могу получить до 9e7 в течение 25 секунд на моей машине Linux. Это может быть быстрее, если копаться в коде C, как говорится после проверки на 2/3/5, полностью учитывать число.

Есть гораздо более умные способы сделать это с помощью просеивания. Я думал, что простой перебор путь будет началом. Это в основном Проект Эйлера проблемы 521, кстати.

DanaJ
источник
Если это вообще полезно знать, в Python с ситом можно управлять только Т (47000). Я собираюсь попробовать что - то подобное тому , что вы делаете , чтобы увидеть , если это быстрее.
Кейд
Похоже, не использовать сито быстрее .. Я смог рассчитать T (493900) с помощью метода, аналогичного вашему.
Каде
Никогда не использовал Perl раньше , но мне удалось подтвердить свой ответ, я добавлю вас в список!
Николас Siplis
Чтобы быть справедливым, это использует мой модуль , который делает факторинг в C (вы можете заставить его использовать чистый Perl для всех, но, конечно , это не так быстро).
DanaJ
Ответ может быть вычислен с использованием любой комбинации языков, так что все нормально.
Николас Siplis
3

Go, 21e9

Делает ли сито для нахождения минимального множителя для каждого числа <= N. порождает подпрограммы для подсчета разделов числового пространства.

Запуск с "идти работать 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
}

Обратите внимание, что ответ для N = 21e9 находится между 2 ^ 63 и 2 ^ 64, поэтому мне пришлось использовать 64-разрядные целые числа без знака для правильного подсчета ...

Кит Рэндалл
источник
Я должен был изменить его , чтобы работать на моей машине (снижение N до 1e9) , но сама среда довольно быстро, хорошая работа!
Николас Сиплис
@ NicolásSiplis: использование памяти было исправлено.
Кит Рэндалл
Время работы составило 80 секунд, но 1.6e10 было рассчитано почти точно за 60!
Николас Сиплис
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
источник
2

Java 8: 1.8e8 2.4e8

Эта запись не сравнится с несколькими другими, которые уже есть, но я хотел опубликовать свой ответ, так как мне было весело работать над этим.

Основные оптимизации моего подхода заключаются в следующем:

  • Каждое четное число имеет наименьший коэффициент 2, поэтому их можно добавить бесплатно после обработки каждого нечетного числа. По сути, если вы выполнили работу, чтобы рассчитать, T(N)когда N % 2 == 1, вы это знаете T(N + 1) == T(N) + 2. Это позволяет мне начать отсчет с трех и увеличивать по итерации по два.
  • Я храню мои простые числа в массиве, а не в Collectionтипе. Это более чем вдвое больше, чем Nя могу достичь.
  • Я использую простые числа для вычисления числа в отличие от исполнения Решета Эратосфена. Это означает, что объем моей памяти практически полностью ограничен массивом простых чисел.
  • Я храню квадратный корень числа, для которого я пытаюсь найти наименьший фактор. Я попытался @ подход user1354678 о квадратуре главным фактором каждый раз, но это стоило мне о чем 1e7 от моего счета.

Вот и все, что нужно сделать. Мой код перебирает с 3 по двойками до тех пор, пока не обнаружит, что он ударил или превысил лимит времени, и в этот момент он выплевывает ответ.

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

Работа в другой системе (Windows 8.1, Intel Core i7 @ 2,5 ГГц, 8 ГБ ОЗУ) с последней версией Java 8 заметно улучшила результаты без изменений кода:

T(240,308,208) = 1,537,216,753,010,879
sadakatsu
источник
Если бы вы могли заменить mayContinue()в for loop conditionтолько с условием простого, можно добиться более высокого результата. И мне нравится твой способ предварительного вычисления четной суммы, а затем увеличения на два.
Кодер
@ user1354678, спасибо за рекомендации. Странно, это не сработало. Я попробовал варианты этого кода на другом компьютере и обнаружил, что опубликованная версия является самой быстрой. Удаление вызовов часов из кода и использование простого порогового числа обошлось мне чуть более секунды. Я даже пытался переключиться startTimeна an, endTimeчтобы исключить вычитания ~ 2e7, но это стоило мне 3e7 из моего счета!
sadakatsu
Вы пробовали это сделать System.nanoTime() - startTime < TIME_LIMIT, потому что это немного закрепляет ваш код для меня. Это не слишком быстро, учитывая тот факт, что это условие проверяется миллионы раз, оно будет немного быстрым. Одна вещь, которую я узнал из вашего кода, заключается в том, что не помещайте forвнутрь a for.. После перехода forк другому методу в моем коде моя скорость кода увеличивается на 40%, спасибо .. Одна вещь, которую я до сих пор выясняю, состоит в том, делали ли массивы намного эффективнее, чем ArrayList, если учитывать тот факт, что он выбирается миллионы раз ..
The Coder
Вы могли бы добиться x2результата, если бы вы реализовали MultiThreading. Но необходимо выполнить предварительный расчет всего массива перед запуском вычисления Prime.
Кодер
@ user1354678, перемещение чека из mayContinue()метода в цикл for будет стоить мне 8e6 из моего счета. Это может быть проблемой локальной оптимизации. Я экспериментировал с несколькими типами данных для хранения простых чисел при разработке этого решения. Я смог достичь только 8.8e7 с ArrayList, но я ударил 1.8e8 (теперь 2.4e8), используя массив. С поиском могут быть некоторые повышения производительности, но есть определенные повышения для выделения памяти. Я думал о многопоточности алгоритма, но столкнулся с проблемами.
садакацу
1

R 2,5e7

Простое сито из Эратосфена, максимально векторизованное. R на самом деле не предназначен для такого рода проблем, и я уверен, что это можно сделать быстрее.

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
источник
Справедливо по поводу T. 2: MAX является вектором целых чисел, поэтому для больших значений MAX sum(vec)приводит к переполнению целого числа и возвращает NA. sum(as.numeric(vec))
суммирует вектор двойных чисел,
1

Питон, ~ 7e8

Использование добавочного сита из эратостенов. Необходимо позаботиться о том, чтобы помеченное значение было отмечено его самым низким делителем, но в остальном реализация довольно проста.

Время было взято с PyPy 2.6.0, ввод принимается как аргумент командной строки.

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

Образец использования

$ pypy sum-lpf.py 10000
5786451

$ pypy sum-lpf.py 100000000
279218813374515
Примо
источник
0

Юлия, 5е7

Конечно, Юля может сделать лучше, но это то, что у меня есть сейчас. Это делает 5e7 примерно за 60 секунд на JuliaBox, но я пока не могу проверить локально. Надеюсь, к тому времени я подумаю о более умном подходе.

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

Здесь мы создаем функцию, lpfкоторая перебирает последовательные простые числа и проверяет входные данные на делимость для каждого. Функция возвращает первый встреченный делитель, тем самым получая наименьший простой множитель.

Основная функция вычисляет lpfцелые числа от 2 до входных данных параллельно и уменьшает результат путем суммирования.

Алекс А.
источник
0

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

Я решил сначала создать список простых чисел от 2 до (sqrt input), а затем проверить каждое значение с помощью простых чисел, тогда как ранее я проверял каждое число до(sqrt input) , что было бы бессмысленно (например, если число делится на 4, оно также делится на 2, поэтому оно уже учтено.)

Слава Богу за побочные эффекты, пока я в этом. Команда remove-if уменьшает размер списка и подсчитывает, сколько элементов было удалено, поэтому мне просто нужно умножить это значение на любое значение цикла и добавить его в промежуточный итог.

(Интересный факт: deleteдеструктивный эквивалент remove, но по какой-то причине он deleteнамного медленнее, чем removeв этом случае.)

Свечи
источник
Никогда ранее не использовал Lisp, я получаю ошибку компилятора при попытке запустить ваш код: (defvar total 0) (defvar counter 0) (defvar input 10000) (числа defvar (цикл для i от 2 до ввода, собирать i)) ( цикл для i от 2 до (floor (sqrt input)) (setf counter 0) суммирование (prog2 (nsubstitute-if 0 # '' (лямбда (x) (if (eq (mod xi) 0)) (progn (incf counter) t ))) числа) (* i counter) (setf numbers (убрать 0 цифр))) в итоге окончательно (возврат (+ total (уменьшить # '+ числа))))
Николас Сиплис
Я использую SBCL 1.0.38, но когда я вернусь домой, я обновлюсь до последней версии и посмотрю, как это происходит. Если вы сохраните его в файл, вы можете запустить его с помощью «sbcl --script <filename>».
свечи
Я пытался, но все равно не повезло, на всякий случай я попытался собрать онлайн с Ideone, но это тоже не сработало.
Николас Сиплис
Ой, извините, я забыл ключевое слово "do" в строке 6. Теперь оно должно запуститься, дать ему еще один шанс.
свечи
Отлично, он вычисляет 6e6 за 60 секунд на моей машине! Кстати, если я решу ввести свой собственный код, знаете ли вы, если я должен представить его в качестве ответа? Я не уверен, что это позволит новые представления.
Николас Сиплис
0

Ржавчина 1.5е9

Очень наивное сито Эратосфена, но я чувствовал, что Руст не получил здесь никакой любви!

// 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);
}
Валентин Клемент
источник
0

Java 2.14e9

Чистое Сито Эратосфена с преимуществом BitSet

Я вычислил сумму наименьшего Integer.MAX_VALUE - 1простого множителя до 33.89 s. Но я не могу продолжать дальше, потому что это приведет к переполнению целочисленного размера. Поэтому я работаю над созданием другого набора битов для следующего набора диапазонов. До тех пор, это самый быстрый, который я могу генерировать.


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

}
Кодер
источник