Given a number n find the prime number closest to it with maximum even digits

Question

I have a challenge to find the prime number closest to any given integer n that has the maximum number of even digits. The code below works and passes all the sample tests. But it times out when the numbers grow too large. Can anyone suggest how I may optimize it?

from collections import defaultdict


def is_prime(n):
    first, i = 1, 2
        if n <= first:
            return False
    while i <= (n**0.5):
        if n % i == 0:
            return False
        i += first
    return True


def highest_prime(n):
    dd = defaultdict(int)
    nums = [str(x) for x in reversed(range(n)) if is_prime(x)]
    is_even = (lambda x: x % 2 == 0)
    for outer in nums:
        for inner in outer:
            if is_even(int(inner)):
                dd[outer] += 1
    return max(dd, key=lambda x: dd[x])


if __name__ == "__main__":
    print(highest_prime(1000))
    print(highest_prime(1210))
    print(highest_prime(10000))

test 1 expected value is 887
test 2 expected value is 1201
test 3 expected value is 8887

Edit: Per the suggestions, since the maximum count of prime digits in a number will always be one less than the total number of digits, I have kept only those numbers whose length is the same as the given integer N. But it still isn't fast enough. For the primality check I used the selected answer at isPrime Function for Python Language

def highest_prime(n):
    nums = list(range(n))
    temp = []
    for x in range(len(nums)):
        if len(str(nums[x])) == len(str(nums[-1])):
            if is_prime(nums[x]):
                temp.append(str(nums[x]))
    is_even = (lambda x: x % 2 == 0)
    dd = defaultdict(int)
    for outer in temp[::-1]:
        for inner in outer:
            if is_even(int(inner)):
                dd[outer] += 1
    return max(dd, key=lambda x: dd[x])

Any other suggestions? Thanks!

Answer 1

there are very clever ways for testing if a number is prime (or at least clever ways that are correct up to a very large N) but in this case when you compute all the prime numbers up to a certain number you can use the previous prime numbers and only check for them as factors:

def get_primes_list(n):
    if n < 2:
        return []
    primes = [2]
    for i in range(3,n+1):
        sqroot = i**0.5
        for p in primes:
            if i%p == 0:
                break
            if p > sqroot:
                primes.append(i)
                break
    return primes

if you're looking for anything more efficient than this (since this method is still resource consuming and will still take a long time when you get to the tens of millions) your best bet is to find an existing implementation of an efficient primality test like the Rabin-Miller primality test that was mentioned

Answer 2

There are two major areas of optimization, that you should consider.

The first is ensuring that our prime number checking is decent. Taking a smart bruteforce approach from Source, You essentially only need to check 6n - 1 and 6n + 1 for all n starting from 1 upto the square root of a number to figure out if it is prime or not. (Because 6n + 2, 6n + 4 are even, and 6n + 3 is divisible by 3). I have added explanations in the is_prime(n) function below.

The second that really makes a difference, is ensuring that you always keep track of "the best possible outcome for even digits". The idea is simple: A prime number of n digits can at-most have n-1 even digits, with the exception of the prime number 2. With that in mind, we only really need to ensure we find the "best case" possible, and instead of accumulating all prime numbers upto a given number n, we just find the highest prime number that fits our best case, going from big to small. So, I have highest_prime_optimized(n) with comments. I initially planned to compare the times of this with the original function, but once the original function ran over a minute i decided to kill it. This one should beat the tests.

import time

def is_prime(n):
    #base cases handling
    if n == 2 or n == 3: return True #handles 2, 3
    if n < 2 or n%2 == 0: return False #handles 1 and even numbers
    if n < 9: return True #since 1, 2, 3, 4, 6 and 8 are handled, this leaves 5 and 7.
    if n%3 == 0: return False #handles multiples of 3
    r = int(n**0.5) #only check upto square root
    f = 5 #start from 5
    while f <= r:
        #print ('\t', f)
        if n%f == 0: return False #essentially checks 6n - 1 for all n.
        if n%(f+2) == 0: return False #essentially checks 6n + 1 for all n.
        f +=6 #incrementing by 6.
    return True

def max_even_digits_in_prime(n):
    return (len(str(n)) - 1) or 1 

def count_of_even_digits(n):
    count = 0
    for i in str(n):
        count+= (int(i) % 2 == 0)
    return count

def highest_prime_optimized(n):
    best_case = (0, 0) #keeps track of highest best case number seen[1], and its count of even digits[0]
    for x in range(n, 1, -1): #iterate in the reverse direction
        #print(x)
        if is_prime(x): #proceed for prime numbers
            even_digits = count_of_even_digits(x)
            max_even_digits = max_even_digits_in_prime(x)
            if best_case[0] < even_digits: #update best number seen so far
                best_case = (even_digits, x)
            if max_even_digits == best_case[0]: #best case answer, your work is done. No need to look for more numbers.
                print(best_case)
                return (best_case[1])

if __name__ == "__main__":
    print(highest_prime_optimized(1000))
    print(highest_prime_optimized(1210))
    print(highest_prime_optimized(10000))
    start = time.time() 
    result = highest_prime_optimized(5000000)
    print(result, time.time() - start)
    #Output: 4888889 0.5920031070709229

Answer 3

Use "Sieve of Eratosthenes" algorithm, which generates the prime numbers less than N.

Hope this might resolve your issue.

It's Time complexity : O(n*log(log(n)))

Reference: https://www.geeksforgeeks.org/sieve-of-eratosthenes/