This post is an immediate follow up for http://lxer.com/module/newswire/view/306255/index.html what will result significant performance boost vs python's version of the sieve of Eratosthenes procedure.
We intend to rely on https://github.com/mathbunnyru/python-cpp-extension . Download and extract tarball on Fedora 34 with "C Development tools" and python-devel installed . Setup python venv in your working directory
$ python3 -m venv .env
$ source .env/bin/activate
$ python setup.py install
(.env) [boris@fedora34server python-cpp-extension-delta]$ ll
total 36
drwxrwxr-x. 5 boris boris 89 Oct 10 09:37 build
drwxrwxr-x. 2 boris boris 90 Oct 10 09:37 cpp_python_extension.egg-info
-rw-rw-r--. 1 boris boris 751 Oct 10 11:57 delta16.py
-rw-rw-r--. 1 boris boris 414 Oct 10 12:01 deltaBetween.py
drwxrwxr-x. 2 boris boris 61 Oct 10 09:37 dist
-rw-rw-r--. 1 boris boris 85 Oct 10 09:18 MyProg.py
-rw-rw-r--. 1 boris boris 1192 Oct 10 09:18 README.md
-rw-rw-r--. 1 boris boris 682 Oct 10 09:18 setup.py
-rw-rw-r--. 1 boris boris 450 Oct 10 09:18 sieve.cpp
-rw-rw-r--. 1 boris boris 140 Oct 10 09:18 sieve.h
-rw-rw-r--. 1 boris boris 1542 Oct 10 09:18 sieve_python_wrapper.cpp
-rw-rw-r--. 1 boris boris 200 Oct 10 09:18 test_benchmark.py
(.env) [boris@fedora34server python-cpp-extension-delta]$
Now update delta16.py from post http://lxer.com/module/newswire/view/306255/index.html
Then update delta16.py as follows
(.env) [boris@fedora34server python-cpp-extension-delta]$ cat delta16.py
import cpp_python_extension
def sumDigits(N,k):
sum = 0
while (N != 0):
sum = sum + N % k
N = N // k
return sum
def SearchNumber(uplimit,sdg):
imax = 0
zn = []
# Here we invoke cpp_python_extension.sieve_of_eratosthenes
# been written in C++ via Python C API which returns python's
# object list containing all prime numbers <= uplimit
zn = cpp_python_extension.sieve_of_eratosthenes(uplimit)
spisok = set(zn)
for i in range(2,uplimit):
# Look for highest prime number <= uplimit
# and summa of digits <= sdg
if (i in spisok) and sumDigits(i,10) <= sdg:
if i > imax:
imax = i
print("Maximum = ",imax)
def main():
uplimit,sdg = 0,0
uplimit = int(input("Input range of scan :"))
sdg = int(input("Input sum of digits :"))
SearchNumber(uplimit,sdg)
if __name__ == "__main__":
main()
No comments:
Post a Comment