Find the closest prime number under a certain integer ```n``` that has the maximum possible amount of even digits.

For ```n = 1000```, the highest prime under ```1000``` is ```887```, having two even digits (8 twice)

Naming ```f()```, the function that gives that prime, the above case and others will be like the following below.
```
f(1000) ---> 887 (even digits: 8, 8)

f(1210) ---> 1201 (even digits: 2, 0)

f(10000) ---> 8887

f(500) ---> 487

f(487) ---> 467
``` 
Features of the random tests:
```
Number of tests = 28
1000 <= n <= 5000000
```

Enjoy it!!

Difficulty: EASY
Tags: Number theory

Data structures

Mathematics

String algorithms
Skill types: Data structures

Starter code:
def f(n):
	

Solutions:
from bisect import bisect_left as bisect
n = 5000000
(sieve, PED, PED_DATA) = ([0] * ((n >> 1) + 1), [], [])
for i in range(3, n + 1, 2):
	if not sieve[i >> 1]:
		for j in range(i ** 2 >> 1, n + 1 >> 1, i):
			sieve[j] = 1
		s = str(i)
		nEveD = sum((s.count(d) for d in '02468'))
		if nEveD:
			PED.append(i)
			PED_DATA.append((nEveD, len(s) - 1))

def f(n):
	idx = bisect(PED, n) - 1
	(m, (nEveD, l)) = (PED[idx], PED_DATA[idx])
	for c in range(idx):
		(mc, (nEveDc, lc)) = (PED[idx - c], PED_DATA[idx - c])
		if nEveDc > nEveD:
			(m, nEveD) = (mc, nEveDc)
		if lc < nEveD:
			break
	return m


def is_prime(n):
	if n == 2 or n == 3:
		return True
	if n < 2 or n % 2 == 0:
		return False
	if n < 9:
		return True
	if n % 3 == 0:
		return False
	r = int(n ** 0.5)
	f = 5
	while f <= r:
		if n % f == 0:
			return False
		if n % (f + 2) == 0:
			return False
		f += 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 f(n):
	best_case = (0, 0)
	for x in range(n - 1, 1, -1):
		if is_prime(x):
			even_digits = count_of_even_digits(x)
			max_even_digits = max_even_digits_in_prime(x)
			if best_case[0] < even_digits:
				best_case = (even_digits, x)
			if max_even_digits == best_case[0]:
				print(best_case)
				return best_case[1]


import itertools
compress = itertools.compress
from bisect import bisect_right, bisect_left

def prime(n):
	if n < 2:
		return []
	r = [False, True] * (n // 2) + [True]
	(r[1], r[2]) = (False, True)
	for i in range(3, int(1 + n ** 0.5), 2):
		if r[i]:
			r[i * i::2 * i] = [False] * int((n + 2 * i - 1 - i * i) / (2 * i))
	r = list(compress(list(range(len(r))), r))
	if r[-1] % 2 == 0:
		r.pop()
	return r
primes = prime(5 * 10 ** 6)

def even(n):
	even_count = 0
	while n > 0:
		rem = n % 10
		if not rem % 2:
			even_count += 1
		n //= 10
	return even_count

def f(n):
	n -= 1
	upper_bound = bisect_right(primes, n)
	best = -1
	bestCount = 0
	for i in reversed(list(range(0, upper_bound))):
		if len(str(primes[i])) <= bestCount:
			break
		count = even(primes[i])
		if bestCount < count:
			best = primes[i]
			bestCount = count
		elif bestCount == count:
			if primes[i] > best:
				best = primes[i]
				bestCount = count
	return best


import math

def check(nr):
	lim = int(nr ** 0.5)
	x = 0
	if nr == 2 or nr == 3:
		return True
	if nr % 2 == 0 or nr <= 1:
		return False
	if nr < 9:
		return True
	if nr % 3 == 0:
		return False
	i = 5
	while i <= lim:
		if nr % i == 0:
			return False
		if nr % (i + 2) == 0:
			return False
		i += 6
	return True

def biggest(nr):
	return len(str(nr)) - 1 or 1

def count_even(nr):
	r = 0
	for i in str(nr):
		r += int(i) % 2 == 0
	return r

def f(n):
	nr = n - 1
	res = 0
	cmax = (0, 0)
	while nr > 0:
		if check(nr):
			e = count_even(nr)
			b = biggest(nr)
			if e > cmax[0]:
				cmax = (e, nr)
			if b == cmax[0]:
				return cmax[1]
		nr -= 1


isprime = lambda x: next((0 for i in range(3, int(x ** 0.5) + 1, 2) if not x % i), 1)

def f(n):
	limit = len(str(n)) - 1 - (str(n)[0] == '1')
	return next((i for i in range(n - [1, 2][n & 1], 1, -2) if isprime(i) and sum([not int(k) & 1 for k in str(i)]) == limit))


evenDigits = ['0', '2', '4', '6', '8']

def primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]

def evenDigitCount(n):
	count = 0
	for c in str(n):
		if c in evenDigits:
			count += 1
	return count

def f(n):
	allPrimes = primes(n)
	p = allPrimes[0]
	mostEvenDigits = evenDigitCount(p)
	for prime in allPrimes:
		thisPrimesEvenDigits = evenDigitCount(prime)
		if thisPrimesEvenDigits >= mostEvenDigits:
			p = prime
			mostEvenDigits = thisPrimesEvenDigits
	return p


def f(n):
	n = n - 1 if n % 2 == 0 else n - 2
	for i in range(n, 1, -2):
		if len(str(i)) <= sum((1 for j in str(i) if int(j) % 2 == 0)) + 1 + int(str(i)[0] == '1'):
			z = True
			for j in range(2, int(i ** 0.5) + 1):
				if i % j == 0:
					z = False
					break
			if z:
				return i