Suma najmniejszych czynników pierwszych

19

SF (n) jest funkcją, która oblicza najmniejszy czynnik pierwszy dla danej liczby n.

Nazwiemy T (N) sumą każdej SF (n) z 2 <= n <= N.

T (1) = 0 (suma jest powyżej 0 sum)

T (2) = 2 (2 jest pierwszą liczbą pierwszą)

T (3) = 5 = 2 + 3

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

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

...

T (10000) = 5786451

Zwycięzcą zostanie ten, któremu uda się obliczyć największą T (N) w 60 sekund na własnym laptopie (Toshiba Satellite L845, Intel Core i5, 8 GB pamięci RAM).


Current top score: Nicolás Siplis - 3.6e13 points - Nim
Nicolás Siplis
źródło
Pf (2) = 2, Pf (3) = 3, więc T (3) = 2 + 3 = 5. Czy mam rację? Zaprogramowałem, aby znaleźć czynniki pierwsze, ale czy mógłbyś rozwinąć kwestię obecnych wymagań. Dziękuję
The Coder
1
@ToddLehman Korzystam z każdego kodu na własnym laptopie (Sony Vaio SVF14A16CLB), więc jeśli zajmie to mniej niż 60 sekund, zwiększę liczbę i zmniejszę, gdy zajmie to więcej czasu.
Nicolás Siplis,
1
Tak, o ile działa na moim komputerze i wyświetla prawidłową odpowiedź w ciągu 60 sekund lub mniej, jest to do przyjęcia.
Nicolás Siplis,
1
Ma 4 wątki.
Nicolás Siplis,
1
Czy biblioteki stron trzecich są dozwolone? W porządku, jeśli program tworzy wątki?
The Coder,

Odpowiedzi:

12

Nim, 3.6e13

Samo przesiewanie nie jest najlepszą odpowiedzią, gdy próbujesz obliczyć najwyższy możliwy N, ponieważ wymagania pamięci stają się zbyt wysokie. Oto inne podejście (zacząłem od Nima kilka dni temu i zakochałem się w szybkości i składni, mile widziane są wszelkie sugestie dotyczące przyspieszenia lub zwiększenia czytelności!).

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
źródło
Próbowałem zaimplementować opakowanie GMP dla Nima w moim kodzie, ale po prostu nie mogłem go uruchomić (nigdy wcześniej nie korzystałem z GMP, więc na pewno nie pomogło).
Nicolás Siplis,
Ty też nie trzeba returnw f„s definicji. Procesy z pojedynczym wyrażeniem zwracają się automatycznie.
kirbyfan64sos
3
To nie pierwszy najszybszy kod, który Nim wygrał z zauważalną przewagą. Może warto to zbadać.
primo
Jestem ciekawy, jak to działa podczas korzystania z GMP, ale mimo moich wysiłków nie udało mi się go poprawnie wdrożyć.
Nicolás Siplis
Nim zdecydowanie znajdzie się na mojej liście do nauki!
Sp3000,
5

C, Prime Sito: 5e9

Wyniki:

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

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

Program:

Chociaż jest to dość prosty program, zajęło mi trochę czasu, aby dowiedzieć się, jak właściwie zarządzać pamięcią - mam tylko tyle pamięci RAM na 1 bajt na liczbę w zakresie, więc musiałem być ostrożny. To standardowe sito 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
źródło
1
Jeśli problemem jest pamięć, wystarczy jeden bit na liczbę. Możesz użyć maski bitowej do przechowywania flag.
Reto Koradi,
@RetoKoradi Niestety, prawdopodobnie spowolniłoby to program na tyle, aby przekroczył 1 minutę.
isaacg,
Do czego potrzebujesz assert.h?
Max Ried
@MaxRied Pozostało z wczesnej wersji.
isaacg
3

Perl, faktoring brutalny

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

Mogę dostać się do około 9e7 w 25 sekund na moim komputerze z systemem Linux. Może być szybsze po wkopaniu w kod C, jak to mówi po sprawdzeniu 2/3/5, całkowicie uwzględnij liczbę.

Są o wiele bardziej sprytne sposoby na to za pomocą przesiewania. Myślałem, że prosty sposób na brutalną siłę będzie początkiem. Nawiasem mówiąc, jest to zasadniczo problem dotyczący projektu Euler 521.

DanaJ
źródło
Jeśli w ogóle warto wiedzieć, w Pythonie z sitem mogę zarządzać tylko T (47000). Spróbuję czegoś podobnego do tego, co robisz, aby zobaczyć, czy jest szybszy.
Kade,
Wygląda na to, że nieużywanie sita jest szybsze. Udało mi się obliczyć T (493900) metodą podobną do twojej.
Kade,
Nigdy wcześniej nie korzystałem z Perla, ale udało mi się zweryfikować twoją odpowiedź, dodam cię do listy!
Nicolás Siplis,
Szczerze mówiąc, używa mojego modułu, który wykonuje faktoring w C (możesz zmusić go do używania czystego Perla do wszystkiego, ale oczywiście nie jest tak szybki).
DanaJ
Odpowiedź można obliczyć przy użyciu dowolnej kombinacji języków, więc nie ma problemu.
Nicolás Siplis,
3

Idź, 21e9

Wykonuje sito, aby znaleźć minimalny współczynnik dla każdej liczby <= N. Odradza goroutines, aby policzyć części przestrzeni liczbowej.

Uruchom z „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
}

Zauważ, że odpowiedź dla N = 21e9 zawiera się między 2 ^ 63 a 2 ^ 64, więc musiałem użyć 64-bitowych liczb całkowitych bez znaku, aby poprawnie policzyć ...

Keith Randall
źródło
Musiałem go zmodyfikować, aby działał na moim komputerze (zmniejszono N do 1e9), ale sam środowisko wykonawcze jest dość szybkie, dobra robota!
Nicolás Siplis,
@ NicolásSiplis: naprawiono użycie pamięci.
Keith Randall,
Czas działania wynosił 80 sekund, ale 1.6e10 został obliczony na prawie dokładnie 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
źródło
2

Java 8: 1.8e8 2.4e8

Ten wpis nie porównuje się z kilkoma innymi, które już się pojawiły, ale chciałem opublikować swoją odpowiedź, ponieważ dobrze się nad tym bawiłem.

Główne optymalizacje mojego podejścia są następujące:

  • Każda liczba parzysta ma najmniejszy współczynnik 2, więc można je dodawać za darmo po przetworzeniu każdej liczby nieparzystej. Zasadniczo, jeśli wykonałeś pracę, aby obliczyć, T(N)kiedy N % 2 == 1to wiesz, wiesz o tym T(N + 1) == T(N) + 2. Pozwala mi to rozpocząć liczenie od trzeciej i zwiększać o iterację po dwa.
  • Moje liczby pierwsze przechowuję w tablicy, a nie w Collectiontypie. To ponad dwukrotnie zwiększyło Nzasięg.
  • Używam liczb pierwszych do obliczenia liczby, w przeciwieństwie do wykonywania sita Eratostenesa. Oznacza to, że moja pamięć jest prawie całkowicie ograniczona do mojej tablicy liczb pierwszych.
  • Przechowuję pierwiastek kwadratowy z liczby, dla której próbuję znaleźć najmniejszy czynnik. Próbowałem za każdym razem @ user1354678 podejścia do kwadratu liczby pierwszej, ale kosztowało mnie to około 1e7 od mojego wyniku.

To wszystko. Mój kod iteruje od 3 do 2, aż wykryje, że przekroczył limit czasu, w którym to momencie wyrzuca odpowiedź.

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

Działa w innym systemie (Windows 8.1, Intel Core i7 @ 2,5 GHz, 8 GB RAM) z najnowszą wersją Java 8 ma znacznie lepsze wyniki bez zmian kodu:

T(240,308,208) = 1,537,216,753,010,879
sadakatsu
źródło
Jeśli można wymienić mayContinue()w for loop conditionza pomocą jednego prostego warunku, można osiągnąć wyższy wynik. Podoba mi się twój sposób wstępnego obliczania nawet sumy, a następnie zwiększania o dwa.
The Coder
@ user1354678, Dziękujemy za zalecenie. O dziwo, to nie zadziałało. Próbowałem odmian tego kodu na innym komputerze i odkryłem, że opublikowana wersja jest najszybsza. Usunięcie wywołań zegara z kodu i użycie prostego numeru progu kosztowało mnie nieco ponad sekundę. Próbowałem nawet zmienić moje startTimena, endTimeaby wyeliminować odejmowanie ~ 2e7, ale to kosztowało mnie 3e7 od mojego wyniku!
sadakatsu
Czy próbowałeś tego System.nanoTime() - startTime < TIME_LIMIT, bo to trochę poprawia twój kod. Nie jest to niesamowicie szybkie, biorąc pod uwagę fakt, że ten warunek jest sprawdzany miliony razy, będzie trochę szybki. Jednej rzeczy nauczyłem się z twojego kodu: nie wkładaj fordo for.. Po przejściu forna inną metodę w moim kodzie, moja prędkość kodu wzrasta o 40%, Dzięki .. Jedną rzeczą, którą wciąż się zastanawiam jest, czy tablice są znacznie wydajniejsze niż ArrayList, biorąc pod uwagę fakt, że jest pobierany miliony razy ..
The Coder
Możesz osiągnąć x2wynik, jeśli wdrożysz MultiThreading. Musiałby jednak wstępnie obliczyć całą tablicę przed uruchomieniem obliczeń Prime.
The Coder,
@ user1354678, przeniesienie czeku z mayContinue()metody do pętli for kosztuje mnie 8e6 od mojego wyniku. Może to być problem lokalnych optymalizacji. Podczas opracowywania tego rozwiązania eksperymentowałem z kilkoma typami danych do przechowywania liczb pierwszych. Byłem w stanie osiągnąć jedynie 8,8e7 ArrayList, ale uderzyłem 1,8e8 (teraz 2,4e8) za pomocą tablicy. Wyszukiwanie może wiązać się z pewnym wzrostem wydajności, ale istnieją wyraźne przyspieszenia przydziału pamięci. Myślałem o algorytmie wielowątkowości, ale napotkałem problemy.
sadakatsu
1

R 2,5e7

Prosto myślące sito Eratostenesa, wektoryzowane w jak największym stopniu. R tak naprawdę nie jest przeznaczony do tego rodzaju problemów i jestem pewien, że można go przyspieszyć.

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
źródło
Dobry punkt na temat T. 2: MAX jest wektorem liczb całkowitych, więc dla dużych wartości MAX sum(vec)prowadzi do przepełnienia liczb całkowitych i zwraca NA. sum(as.numeric(vec))podsumowuje wektor dubletów, który się nie przepełnia (choć może nie dać właściwej odpowiedzi)
mawir
1

Python, ~ 7e8

Używając przyrostowego sita Erathostenes. Należy zachować ostrożność, aby zaznaczona wartość była oznaczona najniższym dzielnikiem, ale w przeciwnym razie implementacja jest dość prosta.

Mierzono czas w PyPy 2.6.0, dane wejściowe są akceptowane jako argument wiersza poleceń.

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

Przykładowe użycie

$ pypy sum-lpf.py 10000
5786451

$ pypy sum-lpf.py 100000000
279218813374515
primo
źródło
0

Julia, 5e7

Z pewnością Julia może sobie poradzić lepiej, ale teraz to właśnie mam. To robi 5e7 w około 60 sekund na JuliaBox, ale nie mogę jeszcze przetestować lokalnie. Mam nadzieję, że do tego czasu wymyślę bardziej sprytne podejście.

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

Tutaj tworzymy funkcję, lpfktóra iteruje przez sekwencyjne liczby pierwsze i sprawdza dane wejściowe pod kątem podzielności według każdego z nich. Funkcja zwraca pierwszy napotkany dzielnik, uzyskując w ten sposób najmniejszą liczbę pierwszą.

Główna funkcja oblicza lpfna liczbach całkowitych od 2 do wejścia równolegle i zmniejsza wynik sumując.

Alex A.
źródło
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)))))

Zdecydowałem się najpierw wygenerować listę liczb pierwszych od 2 do (sqrt input), a następnie przetestować każdą wartość za pomocą liczb pierwszych, podczas gdy poprzednio testowałem każdą liczbę do (sqrt input), co byłoby bezcelowe (np. Jeśli liczba jest podzielna przez 4, jest również podzielny przez 2, więc został już uwzględniony.)

Dzięki Bogu za skutki uboczne, gdy jestem przy tym. Funkcja remove-if obniża rozmiar listy i liczy liczbę elementów, które zostały usunięte, więc muszę tylko pomnożyć to przez dowolną wartość, która jest włączona, i dodać ją do sumy bieżącej.

(Ciekawostka: deletejest niszczycielskim odpowiednikiem remove, ale z jakiegokolwiek powodu deletejest trochę wolniejszy niż removew tym przypadku).

Świece
źródło
Nigdy wcześniej nie używałem Lisp, dostaję błąd kompilatora podczas próby uruchomienia kodu: (defvar total 0) (defvar counter 0) (defvar input 10000) (defvar numbers (pętla dla i od 2 do wejścia zbierać i)) ( pętla dla i od 2 do (floor (wejście sqrt)) (zliczanie setf 0) sumowanie (prog2 (nsubstitute-if 0 # '(lambda (x) (if (eq (mod xi) 0)) (progn (incf counter) t ))) liczby) (licznik * i) (liczby setf (usuń 0 liczb)))) w końcu na końcu (powrót (+ suma (zmniejszenie # '+ liczb)))))
Nicolás Siplis
Korzystam z SBCL 1.0.38, ale kiedy wrócę do domu, zaktualizuję do najnowszej wersji i zobaczę, jak to działa. Jeśli zapiszesz go w pliku, możesz go uruchomić za pomocą polecenia „sbcl --script <nazwa_pliku>”.
Świece
Próbowałem, ale wciąż nie miałem szczęścia, na wypadek, gdybym próbował skompilować online z Ideone, ale to też nie zadziałało.
Nicolás Siplis,
Och, przepraszam, zapomniałem słowa kluczowego „do” w wierszu 6. Powinien on jednak działać teraz, dać mu jeszcze jedną szansę.
Świece
Świetnie, oblicza 6e6 w 60 sekund na mojej maszynie! Nawiasem mówiąc, jeśli zdecyduję się wprowadzić własny kod, czy wiesz, czy powinienem go przesłać jako odpowiedź? Nie jestem pewien, czy pozwoliłoby to na nowe zgłoszenia.
Nicolás Siplis,
0

Rdza 1.5e9

Bardzo naiwne sito Eratosthene, ale czułem, że Rust nie otrzymał tu żadnej miłości!

// 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
źródło
0

Java 2.14e9

Czyste sito Eratostenesa z przewagą BitSet

Integer.MAX_VALUE - 1Właśnie przeliczyłem sumę najmniejszego współczynnika Prime 33.89 s. Ale nie mogę przejść dalej, ponieważ dalsze doprowadzą do przepełnienia liczby całkowitej w rozmiarze zestawu bitów. Pracuję więc nad stworzeniem kolejnego zestawu bitów dla następnego zestawu zakresów. Do tego czasu jest to najszybszy, jaki mogę wygenerować.


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

}
The Coder
źródło