Saturday, October 9, 2021

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































No comments:

Post a Comment