Python Wrapper to find all primes from a given interval via sieve of Eratosthenes released as C++ procedure

 We intend to rely on https://github.com/mathbunnyru/python-cpp-extension . We also would to convert lists to sets and vice-versa and utilize method set1.difference(set2) . Sometimes Python tricks make you really excited 

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

and run straight away:-

$ python setup.py install

(.env) [boris@fedora34server python-cpp-extension-delta]$ cat deltaBetween.py

import cpp_python_extension

uplimit,downlimit =0,0

znBig = []

znSmall = []

uplimit = int(input("Input upper bound :"))

downlimit = int(input("Input lower bound :"))

znBig = cpp_python_extension.sieve_of_eratosthenes(uplimit)

znSmall = cpp_python_extension.sieve_of_eratosthenes(downlimit)

setSmall = set(znSmall)

setBig = set(znBig)

deltaSet = setBig.difference(setSmall)

deltaList = list(deltaSet)

deltaList.sort()

print(deltaList)

Python C++ Wrapper for another YandexQ question via sieve of eratosthenes released as C++ procedure

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

and run straight away:-

$ 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()

Solution another YandexQ question via sieve of eratosthenes in Python

 Problem itself 

What is the maximum natural number X satisfies the condition: X - prime AND NOT X> 1000 AND the sum of the digits X ≤ 25 ?

The major target of this approach is performance improvement when looking for the highest prime number less than 10.000.000 with a given sum of decimal digits. In general, the problem  requires  implementation of sieve of Eratosthenes

Python code implementing  sieve of Eratosthenes

[boris@fedora34server YANDEXQ]$ cat delta16.py

def sumDigits(N,k):

    sum = 0

    while (N != 0):

        sum = sum + N % k

        N = N // k

    return sum

def eratosphen(n,a):

   prime = [True for i in range(n + 1)]

   prime[0] = prime[1] = False

   i = 2

   while i * i <= n:

        if prime[i]: 

            j = i * i

            while j <= n:

                prime[j] = False

                j += i

        i += 1

   for i in range(2, n + 1):

         if prime[i]:

                a.append(i)

   return a

def SearchNumber(uplimit,sdg):

   imax = 0

   # Declare list to be submitted to  eratosphen( )

   zn = []

   eratosphen(uplimit,zn)

   # Converting list "zn" into set 

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