Jumlah faktor prima terkecil

19

SF (n) adalah fungsi yang menghitung faktor prima terkecil untuk angka yang diberikan n.

Kami akan memanggil T (N) jumlah setiap SF (n) dengan 2 <= n <= N.

T (1) = 0 (jumlahnya lebih dari 0 puncak)

T (2) = 2 (2 adalah prime pertama)

T (3) = 5 = 2 + 3

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

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

...

T (10000) = 5786451

Pemenang akan menjadi orang yang berhasil menghitung T (N) terbesar dalam 60 detik pada laptop saya sendiri (Toshiba Satellite L845, Intel Core i5, 8GB RAM).


Current top score: Nicolás Siplis - 3.6e13 points - Nim
Nicolás Siplis
sumber
Pf (2) = 2, Pf (3) = 3, Jadi, T (3) = 2 + 3 = 5. Apakah saya benar? Saya diprogram untuk menemukan faktor-faktor utama, tetapi dapatkah Anda menguraikan persyaratan saat ini. Terima kasih
The Coder
1
@ToddLehman Saya menjalankan masing-masing kode di laptop saya sendiri (Sony Vaio SVF14A16CLB), jadi jika itu membutuhkan waktu kurang dari 60 detik saya akan menambah jumlahnya dan menguranginya saat dibutuhkan lebih lama.
Nicolás Siplis
1
Ya, selama itu berjalan di komputer saya sendiri dan mengeluarkan jawaban yang benar dalam 60 detik atau kurang, itu bisa diterima.
Nicolás Siplis
1
Ini memiliki 4 utas.
Nicolás Siplis
1
Apakah Perpustakaan pihak ketiga diizinkan? Tidak masalah jika program ini membuat utas?
The Coder

Jawaban:

12

Nim, 3.6e13

Cukup pengayakan bukanlah jawaban terbaik ketika mencoba menghitung N tertinggi karena persyaratan memori menjadi terlalu tinggi. Inilah pendekatan yang berbeda (dimulai dengan Nim beberapa hari yang lalu dan jatuh cinta dengan kecepatan dan sintaksisnya, saran untuk membuatnya lebih cepat atau lebih mudah dibaca dipersilahkan!).

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
sumber
Saya mencoba menerapkan pembungkus GMP untuk Nim ke dalam kode saya tetapi tidak bisa membuatnya bekerja (tidak pernah menggunakan GMP sebelumnya sehingga tentu saja tidak membantu).
Nicolás Siplis
Anda juga tidak perlu returndi fdefinisi 's. Prok ekspresi tunggal secara otomatis kembali.
kirbyfan64sos
3
Ini bukan kode tercepat pertama yang dimenangkan Nim dengan selisih yang mencolok. Mungkin perlu diselidiki.
Primo
Saya ingin tahu bagaimana kinerjanya saat menggunakan GMP, tetapi tidak dapat menerapkannya dengan benar meskipun ada usaha saya.
Nicolás Siplis
Nim pasti masuk dalam daftar yang harus dipelajari!
Sp3000
5

C, Prime Sieve: 5e9

Hasil:

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

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

Program:

Meskipun ini adalah program yang agak sulit, saya butuh waktu untuk mencari tahu bagaimana mendapatkan manajemen memori yang benar - saya hanya memiliki ram yang cukup untuk 1 byte per angka dalam jangkauan, jadi saya harus berhati-hati. Ini adalah saringan standar 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
sumber
1
Jika memori menjadi masalah, satu bit per angka harus cukup. Anda dapat menggunakan bitmask untuk menyimpan bendera.
Reto Koradi
@RetoKoradi Sayangnya, itu mungkin akan memperlambat program cukup untuk meletakkannya di atas tanda 1 menit.
isaacg
Apa yang Anda butuhkan untuk menegaskan?
Max Ried
@ MaxRied Itu tersisa dari versi earlie.
isaacg
3

Perl, anjak piutang

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

Saya dapat mencapai 9e7 dalam 25 detik pada mesin Linux saya. Itu bisa lebih cepat dengan menggali ke dalam kode C, seperti yang dikatakan setelah cek untuk 2/3/5, benar-benar faktor angka.

Ada banyak cara yang lebih pintar untuk melakukan ini dengan menggunakan pengayakan. Saya pikir cara kasar yang sederhana akan menjadi awal. Omong-omong, ini pada dasarnya adalah masalah Project Euler 521.

DanaJ
sumber
Jika itu berguna untuk diketahui, dengan Python dengan ayakan saya hanya dapat mengelola T (47000). Saya akan mencoba sesuatu yang mirip dengan apa yang Anda lakukan untuk melihat apakah itu lebih cepat.
Kade
Sepertinya tidak menggunakan saringan lebih cepat .. Saya bisa menghitung T (493900) dengan metode yang mirip dengan milik Anda.
Kade
Belum pernah menggunakan Perl sebelumnya tetapi saya berhasil memverifikasi jawaban Anda, saya akan menambahkan Anda ke daftar!
Nicolás Siplis
Agar adil, ini menggunakan modul saya yang melakukan anjak di C (Anda dapat memaksanya untuk menggunakan Perl murni untuk semuanya, tapi tentu saja itu tidak secepat).
DanaJ
Jawabannya dapat dihitung menggunakan kombinasi bahasa apa pun, jadi tidak apa-apa.
Nicolás Siplis
3

Pergi, 21e9

Apakah saringan untuk menemukan faktor minimum dari setiap angka <= N. Memunculkan goroutine untuk menghitung bagian dari ruang angka.

Jalankan dengan "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
}

Perhatikan bahwa jawaban untuk N = 21e9 adalah antara 2 ^ 63 dan 2 ^ 64, jadi saya harus menggunakan int 64-bit yang tidak ditandatangani untuk menghitung dengan benar ...

Keith Randall
sumber
Saya harus memodifikasinya untuk berjalan di mesin saya (menurun N ke 1e9) tetapi runtime itu sendiri cukup cepat, kerja bagus!
Nicolás Siplis
@ NicolásSiplis: penggunaan memori telah diperbaiki.
Keith Randall
Runtime adalah 80 detik tetapi 1,6e10 dihitung dalam hampir tepat 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
sumber
2

Java 8: 1.8e8 2.4e8

Entri ini tidak dibandingkan dengan beberapa entri lain yang sudah ada, tetapi saya ingin memposting jawaban saya karena saya senang mengerjakannya.

Optimalisasi utama dari pendekatan saya adalah sebagai berikut:

  • Setiap bilangan genap memiliki faktor terkecil 2, sehingga ini dapat ditambahkan secara gratis setelah setiap bilangan ganjil diproses. Pada dasarnya, jika Anda telah melakukan pekerjaan untuk menghitung T(N)kapan N % 2 == 1, Anda tahu ituT(N + 1) == T(N) + 2 . Ini memungkinkan saya untuk mulai menghitung pada tiga dan meningkat dengan iterasi oleh dua atau dua.
  • Saya menyimpan bilangan prima saya dalam sebuah array, bukan Collectiontipe. Ini lebih dari dua kali lipat yang Nbisa saya jangkau.
  • Saya menggunakan bilangan prima untuk faktor bilangan sebagai lawan melakukan Saringan Eratosthenes. Ini berarti bahwa penyimpanan memori saya terbatas hampir sepenuhnya ke array primes saya.
  • Saya menyimpan akar kuadrat dari angka yang saya coba cari faktor terkecil. Saya mencoba pendekatan @ user1354678 dengan mengkuadratkan faktor prima setiap kali, tetapi ini menghabiskan sekitar 1e7 dari skor saya.

Itu semua yang ada untuk itu. Kode saya beralih dari 3 ke dua oleh dua hingga mendeteksi bahwa ia telah mencapai atau melebihi batas waktu, pada saat itu ia mengeluarkan jawabannya.

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

Berjalan pada sistem yang berbeda (Windows 8.1, Intel core i7 @ 2.5 GHz, 8 GB RAM) dengan Java 8 versi terbaru memiliki hasil yang jauh lebih baik tanpa perubahan kode:

T(240,308,208) = 1,537,216,753,010,879
sadakatsu
sumber
Jika Anda bisa mengganti mayContinue()in for loop conditiondengan hanya kondisi sederhana, Anda bisa mencapai hasil yang lebih tinggi. Dan saya suka cara Anda menghitung ulang bahkan jumlah, kemudian bertambah dua.
The Coder
@ user1354678, Terima kasih untuk rekomendasinya. Anehnya, itu tidak berhasil. Saya mencoba variasi kode ini di komputer yang berbeda dan menemukan bahwa versi yang diposting adalah yang tercepat. Menghapus panggilan jam dari kode dan menggunakan nomor ambang batas biaya sedikit lebih dari satu detik. Saya bahkan mencoba mengalihkan startTimeke nilai endTimeuntuk menghilangkan ~ 2e7 pengurangan, tapi itu membuat saya 3e7 dari skor saya!
sadakatsu
Apakah Anda sudah mencobanya System.nanoTime() - startTime < TIME_LIMIT, karena itu kencangkan kode Anda sedikit untuk saya. Ini tidak cepat, mengingat fakta, kondisi ini diperiksa jutaan kali, ini akan sedikit cepat. Satu hal yang saya pelajari dari kode Anda adalah, jangan masukkan ke fordalam for.. Setelah pindah forke metode lain dalam kode saya, kecepatan kode saya meningkat sebesar 40%, Terima kasih .. Satu hal yang saya masih pahami adalah, Apakah array jauh lebih efisien daripada ArrayList ketika mempertimbangkan fakta bahwa itu diambil jutaan kali ..
The Coder
Anda dapat mencapai x2hasil jika Anda menerapkan MultiThreading. Tetapi perlu menghitung ulang seluruh array sebelum menjalankan perhitungan Prime.
The Coder
@ user1354678, memindahkan cek dari mayContinue()metode ke loop for biaya saya 8e6 dari skor saya. Ini mungkin masalah optimisasi lokal. Saya bereksperimen dengan beberapa tipe data untuk menyimpan bilangan prima ketika saya mengembangkan solusi ini. Saya hanya dapat mencapai 8.8e7 dengan ArrayList, tapi saya menekan 1.8e8 (sekarang 2.4e8) menggunakan array. Mungkin ada beberapa peningkatan kinerja yang terlibat dengan pencarian, tetapi ada dorongan pasti untuk alokasi memori. Saya telah memikirkan tentang multi-threading algoritme, tetapi saya mengalami masalah.
sadakatsu
1

R, 2.5e7

Saringan Eratosthenes yang berpikiran sederhana, vektor sebanyak mungkin. R tidak benar-benar dirancang untuk masalah seperti ini dan saya cukup yakin itu bisa dibuat lebih cepat.

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
sumber
Titik wajar tentang T. 2: MAX adalah vektor bilangan bulat sehingga untuk nilai MAX yang besar, sum(vec)mengarah ke bilangan bulat bilangan bulat dan mengembalikan NA. sum(as.numeric(vec))menjumlahkan vektor ganda yang tidak meluap (meskipun mungkin tidak memberikan jawaban yang tepat)
mawir
1

Python, ~ 7e8

Menggunakan Saringan tambahan Erathostenes. Beberapa kehati-hatian perlu diperhatikan bahwa nilai yang ditandai ditandai dengan pembagi terendah, tetapi implementasinya sebaliknya cukup lurus ke depan.

Waktu diambil dengan PyPy 2.6.0, input diterima sebagai argumen baris perintah.

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

Contoh Penggunaan

$ pypy sum-lpf.py 10000
5786451

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

Julia, 5e7

Tentunya Julia bisa berbuat lebih baik tetapi inilah yang saya miliki untuk saat ini. Ini melakukan 5e7 dalam waktu sekitar 60 detik pada JuliaBox tapi saya belum bisa menguji secara lokal. Semoga saat itu saya akan memikirkan pendekatan yang lebih pintar.

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

Di sini kami membuat fungsi lpfyang beralih melalui bilangan prima berurutan dan memeriksa input untuk dapat dibagi oleh masing-masing. Fungsi mengembalikan pembagi pertama yang ditemukan, sehingga memperoleh faktor prima terkecil.

Fungsi utama menghitung lpfbilangan bulat dari 2 ke input secara paralel dan mengurangi hasilnya dengan menjumlahkan.

Alex A.
sumber
0

Gangguan Umum, 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)))))

Saya telah memilih untuk pertama-tama menghasilkan daftar bilangan prima dari 2 hingga (sqrt input) , kemudian menguji setiap nilai dengan bilangan prima, sedangkan sebelumnya saya akan menguji setiap bilangan hingga(sqrt input) , yang tidak ada gunanya (misalnya, jika angka dapat dibagi 4, itu juga habis dibagi 2, jadi sudah diperhitungkan.)

Terima kasih Tuhan untuk efek samping saat saya melakukannya. Hapus-jika keduanya menurunkan ukuran daftar dan menghitung berapa banyak elemen yang dihapus, jadi saya hanya perlu mengalikannya dengan nilai berapapun loop aktif dan menambahkannya ke total berjalan.

(Fakta menyenangkan: deleteadalah padanan yang merusak remove, tetapi karena alasan apa pun, deletesemua jenisnya lebih lambat daripada removedalam kasus ini.)

Lilin
sumber
Belum pernah menggunakan Lisp sebelumnya, saya mendapatkan kesalahan kompiler ketika mencoba menjalankan kode Anda: (total defvar 0) (penghitung defvar 0) (input defvar 10000) (angka defvar (loop untuk saya dari 2 ke input mengumpulkan i)) () loop untuk i dari 2 ke (lantai (input sqrt)) (penghitung setf 0) menjumlahkan (prog2 (nsubstitute-if 0 # '(lambda (x) (if (eq (mod xi) 0) (progn (incf counter) t ))) angka) (* i counter) (angka setf (hapus 0 angka))) menjadi total akhirnya (return (+ total (kurangi # '+ angka)))))
Nicolás Siplis
Saya menggunakan SBCL 1.0.38, tetapi ketika saya sampai di rumah saya akan memperbarui ke versi terbaru dan melihat bagaimana hasilnya. Jika Anda menyimpannya dalam file, Anda dapat menjalankannya dengan "sbcl --script <filename>".
Lilin
Saya mencoba tetapi masih tidak berhasil, kalau-kalau saya mencoba kompilasi online dengan Ideone tetapi itu tidak berhasil.
Nicolás Siplis
Oh, maaf, saya lupa kata kunci "lakukan" pada baris 6. Namun harus dijalankan sekarang, coba lagi.
Lilin
Hebat, ini menghitung 6e6 dalam 60 detik di mesin saya! Ngomong-ngomong, jika saya memutuskan untuk memasukkan kode saya sendiri, apakah Anda tahu jika saya harus mengirimkannya sebagai jawaban? Saya tidak yakin apakah itu akan memungkinkan pengiriman baru.
Nicolás Siplis
0

Karat 1.5e9

Saringan Eratosthene yang sangat naif, tetapi saya merasa Rust tidak menerima cinta apa pun di sini!

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

Java 2.14e9

Saringan Murni Eratosthenes dengan keunggulan BitSet

Saya telah menghitung Terkecil faktor sum Perdana upto Integer.MAX_VALUE - 1hanya di 33.89 s. Tapi saya tidak bisa melanjutkan lebih besar karena lebih jauh akan mengarah ke Integer Overflow pada Ukuran Bitset. Jadi saya sedang mengerjakan untuk membuat Bitset lain untuk set Ranges berikutnya. Sampai saat itu, ini adalah yang tercepat yang bisa saya hasilkan.


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

}
Sang Coder
sumber