public
Last active

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

  • Download Gist
README.md
Markdown

10000個の素数の和

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

benchmark.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
#!/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
Python
1 2
from distutils.core import setup, Extension
setup(ext_modules=[Extension('yapcx', ['yapcx.c'])])
homuhomu.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
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
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
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
Cython
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
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 ...
# * * * *

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.