http://yapc.pjeuler.com/dir/yapc2012 10000個の素数の和

README.md

10000個の素数の和

実行するには python benchmark.py yapc2012.py のようにします。 この benchmark スクリプトは PrimeWars で計測のために使われているものです。

benchmark.py

#!/usr/bin/python
# encoding:utf-8
import sys
import os
import time
from StringIO import StringIO
buffer = StringIO()
if len(sys.argv) == 1 or not os.path.exists(sys.argv[1]):
    print "999.999\nERROR SCRIPT NOT FOUND"
    quit()

inputfile = open(sys.argv[1],  'r')
code = inputfile.read()
inputfile.close()

sys.stdout = buffer
start = time.time()
exec code
end = time.time()

sys.stdout = sys.__stdout__
print end-start
print buffer.getvalue()

build_yapcx.py

from distutils.core import setup, Extension
setup(ext_modules=[Extension('yapcx', ['yapcx.c'])])

homuhomu.py

import time
_t = time.time()
time.time = lambda: _t

def main(N):
    from math import log
    if N <= 6:
        return sum([2,3,5,7,11,13][:N])

    MAX_NUM = int(N*log(N) + N*log(log(N)) + 1)/2

    L = bytearray(MAX_NUM)
    F = bytearray(b'1' * MAX_NUM)
    S = 2
    i = 1
    next = L.find

    for _ in xrange(N-1):
        i = next(b'\x00', i)
        x = i*2+1
        S += x
        L[i::x] = F[i::x]
        #print i, x, L

    return S

print main(10000)


#1 3 5 7 9 11 13 15 17 19 21 23 25 ...
#  *     *        *       *

yapc2012.py

def main(N):
    from math import log
    if N <= 6:
        return sum([2,3,5,7,11,13][:N])

    MAX_NUM = int(N*log(N) + N*log(log(N)) + 1)/2

    L = bytearray(MAX_NUM)
    F = bytearray(b'1' * MAX_NUM)
    S = 2
    i = 1
    next = L.find

    for _ in xrange(N-1):
        i = next(b'\x00', i)
        x = i*2+1
        S += x
        L[i::x] = F[i::x]
        #print i, x, L

    return S

print main(10000)


#1 3 5 7 9 11 13 15 17 19 21 23 25 ...
#  *     *        *       *

yapcx.pyx

from libc.math cimport log
from libc.stdlib cimport malloc, free
from libc.string cimport memset

def primesum(int N):
    cdef int MAX_NUM = int(N*log(N) + N*log(log(N)) + 1)/2
    cdef char* L
    cdef int S, i, p, j, k, _

    if N <= 6:
        return sum([2,3,5,7,11,13][:N])

    L = <char*>malloc(MAX_NUM)
    memset(L, 0, MAX_NUM)

    L[0] = 1
    S = 2
    i = 1

    for _ in range(N-1):
        while L[i]:
            i += 1
        p = i * 2 + 1
        S += p
        j = i
        while j < MAX_NUM:
            L[j] = 1
            j += p

    free(L)
    return S

#if __name__ == '__main__':
#    print primesum(10000)


#1 3 5 7 9 11 13 15 17 19 21 23 25 ...
#  *     *        *       *