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