Summe kleinster Primfaktoren

19

SF (n) ist eine Funktion, die den kleinsten Primfaktor für eine gegebene Zahl n berechnet.

Wir nennen T (N) die Summe jedes SF (n) mit 2 <= n <= N.

T (1) = 0 (die Summe ist über 0 Summanden)

T (2) = 2 (2 ist die erste Primzahl)

T (3) = 5 = 2 + 3

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

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

...

T (10000) = 5786451

Der Gewinner ist derjenige, der es schafft, die größte T (N) in 60 Sekunden auf meinem eigenen Laptop (Toshiba Satellite L845, Intel Core i5, 8 GB RAM) zu berechnen.


Current top score: Nicolás Siplis - 3.6e13 points - Nim
Nicolás Siplis
quelle
Pf (2) = 2, Pf (3) = 3, also T (3) = 2 + 3 = 5. Habe ich recht? Ich habe es so programmiert, dass ich Primfaktoren finde, aber könnten Sie etwas über die aktuelle Anforderung sagen? Vielen Dank
The Coder
1
@ToddLehman Ich führe jeden Code in meinem eigenen Laptop aus (Sony Vaio SVF14A16CLB). Wenn es also weniger als 60 Sekunden dauert, erhöhe ich die Zahl und verringere sie, wenn es länger dauert.
Nicolás Siplis
1
Ja, solange es auf meinem eigenen Computer ausgeführt wird und die richtige Antwort in höchstens 60 Sekunden ausgibt, ist es akzeptabel.
Nicolás Siplis
1
Es hat 4 Fäden.
Nicolás Siplis
1
Dürfen Bibliotheken von Drittanbietern verwendet werden? Ist es in Ordnung, wenn das Programm Threads erstellt?
Der Coder

Antworten:

12

Nim, 3,6e13

Ein einfaches Sieben ist nicht die beste Antwort, wenn versucht wird, den höchstmöglichen N-Wert zu berechnen, da der Speicherbedarf zu hoch wird. Hier ist ein anderer Ansatz (hat vor ein paar Tagen mit Nim angefangen und sich in die Geschwindigkeit und Syntax verliebt. Vorschläge, die es schneller oder lesbarer machen, sind willkommen!).

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
quelle
Ich habe versucht, den GMP-Wrapper für Nim in meinen Code zu implementieren, konnte ihn jedoch nicht zum Laufen bringen (ich habe vorher noch nie GMP verwendet, das hat also sicherlich nicht geholfen).
Nicolás Siplis,
Du brauchst auch nicht die returnin fDefinition. Einzelne Ausdrücke werden automatisch zurückgegeben.
kirbyfan64sos
3
Dies ist nicht der erste schnellste Code , den Nim mit einem beachtlichen Vorsprung gewonnen hat. Könnte eine Untersuchung wert sein.
Primo
Ich bin gespannt, wie es sich bei der Verwendung von GMP verhält, konnte es aber trotz meiner Bemühungen nicht korrekt implementieren.
Nicolás Siplis
Nim steht definitiv auf meiner To-Learn-Liste!
Sp3000,
5

C, Prime Sieve: 5e9

Ergebnisse:

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

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

Programm:

Obwohl es sich um ein recht einfaches Programm handelt, habe ich eine Weile gebraucht, um herauszufinden, wie ich die Speicherverwaltung richtig machen kann. Ich habe nur genug RAM für 1 Byte pro Nummer im Bereich, also musste ich vorsichtig sein. Es ist ein Standardsieb von 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
quelle
1
Wenn es um Speicher geht, sollte ein Bit pro Nummer ausreichen. Sie können eine Bitmaske zum Speichern der Flags verwenden.
Reto Koradi
@RetoKoradi Leider würde dies das Programm wahrscheinlich so verlangsamen, dass es die 1-Minuten-Marke überschreitet.
Isaacg
Wofür brauchst du assert.h?
Max Ried
@MaxRied Es wurde von einer frühen Version übrig gelassen.
isaacg
3

Perl, Brute Force Factoring

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

Auf meinem Linux-Rechner kann ich in 25 Sekunden ungefähr 9e7 erreichen. Durch Eingraben in den C-Code könnte es schneller gehen, da nach einer Prüfung auf 2/3/5 die Zahl vollständig berücksichtigt wird.

Es gibt viel cleverere Möglichkeiten, dies durch Sieben zu erreichen. Ich dachte, ein einfacher Brute-Force-Weg wäre ein Anfang. Dies ist übrigens im Grunde Project Euler Problem 521.

DanaJ
quelle
Wenn es überhaupt nützlich ist zu wissen, kann ich in Python mit einem Sieb nur T (47000) verwalten. Ich werde etwas Ähnliches ausprobieren, um zu sehen, ob es schneller ist.
Kade,
Sieht so aus, als wäre es schneller, kein Sieb zu verwenden. Ich konnte T (493900) mit einer ähnlichen Methode wie Ihrer berechnen.
Kade,
Ich habe Perl noch nie benutzt, aber es ist mir gelungen, Ihre Antwort zu bestätigen. Ich werde Sie der Liste hinzufügen!
Nicolás Siplis
Um fair zu sein, wird mein Modul verwendet, das das Factoring in C ausführt (Sie können es zwingen, reines Perl für alles zu verwenden, aber natürlich ist es nicht so schnell).
DanaJ
Die Antwort kann mit einer beliebigen Sprachkombination berechnet werden, das ist also in Ordnung.
Nicolás Siplis
3

Los, 21e9

Führt ein Sieb durch, um den Mindestfaktor jeder Zahl <= N zu ermitteln. Löst Goroutinen aus, um Abschnitte des Zahlenraums zu zählen.

Führen Sie "go run prime.go -P 4 -N 21000000000" aus.

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
}

Beachten Sie, dass die Antwort für N = 21e9 zwischen 2 ^ 63 und 2 ^ 64 liegt, sodass ich vorzeichenlose 64-Bit-Ints verwenden musste, um richtig zu zählen ...

Keith Randall
quelle
Ich musste es modifizieren, um es auf meinem Computer laufen zu lassen (verringert auf 1e9), aber die Laufzeit selbst ist ziemlich schnell, gute Arbeit!
Nicolás Siplis
@ NicolásSiplis: Speichernutzung wurde behoben.
Keith Randall
Die Laufzeit betrug 80 Sekunden, aber 1.6e10 wurde in fast genau 60 Sekunden berechnet!
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
quelle
2

Java 8: 1.8e8 2.4e8

Dieser Eintrag ist nicht mit einigen anderen Einträgen vergleichbar, aber ich wollte meine Antwort posten, da es mir Spaß gemacht hat, daran zu arbeiten.

Die Hauptoptimierungen meines Ansatzes sind wie folgt:

  • Jede gerade Zahl hat den kleinsten Faktor 2, sodass diese nach jeder ungeraden Zahl kostenlos hinzugefügt werden können. Grundsätzlich, wenn Sie die Arbeit gemacht haben, um zu berechnen, T(N)wann N % 2 == 1, wissen Sie das T(N + 1) == T(N) + 2. Dies ermöglicht es mir, mit dem Zählen um drei zu beginnen und durch Iteration um zwei zu erhöhen.
  • Ich speichere meine Primzahlen in einem Array im Gegensatz zu einem CollectionTyp. Das hat sich mehr als verdoppelt, als Nich erreichen kann.
  • Ich verwende die Primzahlen, um eine Zahl zu faktorisieren, anstatt das Sieb des Eratosthenes durchzuführen. Dies bedeutet, dass mein Speicher fast vollständig auf mein Primes-Array beschränkt ist.
  • Ich speichere die Quadratwurzel der Zahl, für die ich den kleinsten Faktor zu finden versuche. Ich habe versucht, bei @ user1354678 jedes Mal einen Primfaktor zu quadrieren, aber das hat mich ungefähr 1e7 von meiner Punktzahl gekostet.

Das ist ungefähr alles, was es zu tun gibt. Mein Code iteriert ab 3 zu zweit, bis er feststellt, dass er das Zeitlimit erreicht oder überschritten hat. Zu diesem Zeitpunkt gibt er die Antwort aus.

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

Das Ausführen auf einem anderen System (Windows 8.1, Intel Core i7 bei 2,5 GHz, 8 GB RAM) mit der neuesten Version von Java 8 führt zu deutlich besseren Ergebnissen ohne Codeänderungen:

T(240,308,208) = 1,537,216,753,010,879
sadakatsu
quelle
Wenn Sie die ersetzen könnten mayContinue()in for loop conditionmit nur einem einfachen Zustand, könnte man höheres Ergebnis erzielen. Und ich mag es, wenn Sie eine gerade Summe vorberechnen und dann um zwei erhöhen.
The Coder
@ user1354678, Danke für die Empfehlung. Seltsamerweise hat es nicht funktioniert. Ich habe Variationen dieses Codes auf einem anderen Computer ausprobiert und festgestellt, dass die veröffentlichte Version die schnellste ist. Das Entfernen der Uhrzeitanrufe aus dem Code und die Verwendung einer einfachen Schwellenwertnummer kosteten mich etwas mehr als eine Sekunde. Ich habe sogar versucht, meine startTimeauf eine endTimeumzustellen, um die ~ 2e7-Subtraktionen zu eliminieren, aber das hat mich 3e7 von meiner Punktzahl gekostet!
Sadakatsu
Hast du es mit System.nanoTime() - startTime < TIME_LIMITprobiert, weil es deinen Code für mich ein wenig beschleunigt. Es ist nicht blitzschnell, wenn man bedenkt, dass dieser Zustand millionenfach überprüft wird, es wird ein bisschen schnell. Eine Sache , die ich aus dem Code gelernt wird, nicht gesetzt forinnerhalb eines for.. Nach dem Umzug forin meinem Code auf eine andere Methode, meinen Code Geschwindigkeit um 40% erhöht wird, Dank .. Eine Sache , ich bin immer noch herauszufinden , ist, Did Arrays sind viel effizienter als ArrayList, wenn man bedenkt, dass es millionenfach abgerufen wurde.
The Coder
Sie könnten ein x2Ergebnis erzielen, wenn Sie implementieren MultiThreading. Es müsste jedoch das gesamte Array vorberechnet werden, bevor die Prime-Berechnung ausgeführt werden kann.
The Coder
@ user1354678, das Verschieben des Schecks von der mayContinue()Methode in die for-Schleife kostet mich 8e6 von meiner Punktzahl. Dies kann ein Problem lokaler Optimierungen sein. Bei der Entwicklung dieser Lösung habe ich mit verschiedenen Datentypen zum Speichern der Primzahlen experimentiert. Ich war nur in der Lage, 8.8e7 mit zu erreichen ArrayList, aber ich schlug 1.8e8 (jetzt 2.4e8) unter Verwendung eines Arrays. Es kann einige Leistungssteigerungen geben, die mit dem Nachschlagen verbunden sind, aber es gibt bestimmte Steigerungen für die Speicherzuweisung. Ich habe über das Multithreading des Algorithmus nachgedacht, bin aber auf Probleme gestoßen.
Sadakatsu
1

R, 2,5e7

Einfaches Sieb von Eratosthenes, so oft wie möglich vektorisiert. R ist nicht wirklich für diese Art von Problem ausgelegt und ich bin mir ziemlich sicher, dass es schneller gemacht werden kann.

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
quelle
Gerechter Punkt zu T. 2: MAX ist ein Vektor von ganzen Zahlen, sum(vec)führt also für große Werte von MAX zu einem Überlauf von ganzen Zahlen und gibt NA zurück. sum(as.numeric(vec))summiert einen doppelten Vektor, der nicht überläuft (obwohl er möglicherweise nicht die richtige Antwort
liefert
1

Python, ~ 7e8

Verwenden eines inkrementellen Siebs von Erathostenes. Es muss sorgfältig darauf geachtet werden, dass ein markierter Wert mit dem niedrigsten Divisor markiert wird, ansonsten ist die Implementierung jedoch recht einfach.

Das Timing wurde mit PyPy 2.6.0 durchgeführt, die Eingabe wird als Befehlszeilenargument akzeptiert.

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

Beispielnutzung

$ pypy sum-lpf.py 10000
5786451

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

Julia, 5e7

Sicher kann Julia es besser machen, aber das ist es, was ich jetzt habe. Dies macht 5e7 in ca. 60 Sekunden auf JuliaBox, aber ich kann lokal noch nicht testen. Hoffentlich habe ich mir bis dahin einen klügeren Ansatz überlegt.

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

Hier erstellen wir eine Funktion lpf , die durch sequenzielle Primzahlen iteriert und die Eingabe auf Teilbarkeit durch jede überprüft. Die Funktion gibt den ersten gefundenen Divisor zurück und erhält so den niedrigsten Primfaktor.

Die Hauptfunktion berechnet lpfparallel die Ganzzahlen von 2 bis zur Eingabe und reduziert das Ergebnis durch Summieren.

Alex A.
quelle
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)))))

Ich habe mich dafür entschieden, zuerst eine Liste von Primzahlen von 2 bis zu generieren (sqrt input)und dann jeden Wert mit den Primzahlen zu testen, während ich zuvor gegen jede Zahl bis zu testen würde(sqrt input) zu testete, was sinnlos wäre (zB wenn eine Zahl durch 4 teilbar ist, es ist auch durch 2 teilbar, es ist also bereits berücksichtigt.)

Gott sei Dank für die Nebenwirkungen, während ich dabei bin. Das Entfernen-Wenn verringert die Größe der Liste und zählt, wie viele Elemente entfernt wurden. Ich muss also nur diesen Wert mit dem Wert multiplizieren, auf dem die Schleife aktiviert ist, und diesen Wert zur laufenden Summe hinzufügen.

(Unterhaltsame Tatsache: deleteist das destruktive Äquivalent von remove, aber aus welchem ​​Grund auch immer, deleteist alles viel langsamer als removein diesem Fall.)

Kerzen
quelle
Ich habe Lisp noch nie benutzt. Beim Versuch, Ihren Code auszuführen, wird ein Compilerfehler angezeigt: (defvar total 0) (defvar counter 0) (defvar input 10000) (defvar numbers (Schleife für i von 2 zur Eingabe von collect i)) ( Schleife für i von 2 bis (Etage (sqrt-Eingabe)) (setf-Zähler 0) Summieren (prog2 (nsubstitute-if 0 # '(Lambda (x) (if (eq (mod xi) 0)) (progn (incf-Zähler) t ))) numbers) (* i counter) (setf numbers (remove 0 numbers))) in total finally (return (+ total (
reduct
Ich verwende SBCL 1.0.38, aber wenn ich nach Hause komme, aktualisiere ich auf die neueste Version und sehe, wie es geht. Wenn Sie es in einer Datei speichern, können Sie es mit "sbcl --script <Dateiname>" ausführen.
Kerzen
Ich habe es versucht, aber immer noch kein Glück, nur für den Fall, dass ich online mit Ideone kompilieren wollte, aber das hat auch nicht funktioniert.
Nicolás Siplis,
Oh, sorry, ich habe das "do" -Schlüsselwort in Zeile 6 vergessen. Es sollte jetzt laufen, versuchen Sie es noch einmal.
Kerzen
Großartig, es berechnet 6e6 in 60 Sekunden auf meinem Computer! Übrigens, wenn ich mich entscheide, meinen eigenen Code einzugeben, weißt du, ob ich ihn als Antwort einreichen soll? Ich bin mir nicht sicher, ob das neue Einreichungen erlauben würde.
Nicolás Siplis
0

Rust 1.5e9

Ein sehr naives Eratosthene-Sieb, aber ich hatte das Gefühl, dass Rust hier keine Liebe erhielt!

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

Java 2.14e9

Reines Eratosthenesieb mit BitSet-Vorteil

Ich habe die Summe der kleinsten Primfaktoren bis Integer.MAX_VALUE - 1genau in berechnet 33.89 s. Größer kann ich aber nicht vorgehen, da sonst ein Integer Overflow bei der Größe des Bitsets auftritt. Also arbeite ich daran, ein weiteres Bitset für die nächsten Ranges zu erstellen. Bis dahin ist dies die schnellste, die ich generieren kann.


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

}
Der Coder
quelle