Sum of smallest prime factors SF(n) is a function which computes the smallest prime factor for a given number n.

We'll call T(N) the sum of every SF(n) with 2 &lt;= n &lt;= N.

T(1) = 0 (the sum is over 0 summands)

T(2) = 2 (2 is the first prime)

T(3) = 5 = 2 + 3

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

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

...

T(10000) = 5786451

The winner will be the one who manages to compute the largest T(N) in 60 seconds on my own laptop (Toshiba Satellite L845, Intel Core i5, 8GB RAM). 



Current top score: Nicolás Siplis - 3.6e13 points - Nim
Nim, 3.6e13

Simply sieving is not the best answer when trying to calculate the highest N possible since the memory requirements become too high. Here's a different approach (started with Nim a couple days ago and fell in love with the speed and syntax, any suggestions to make it faster or more readable are welcome!).

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 &lt;= 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 &lt;= 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)