Участник:Morgachev/PRMFN

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/PRMFN/

1) Вариант не проходящий проверку по времени (python3). Основная идея - Перебираем все числа из простых цифр сверху вниз, для каждого из них проверяем, является ли оно простым. По времени укладывается до N = 10**9 на моем ноутбуке.

K2V = {
    0: 2,
    1: 3,
    2: 5,
    3: 7
}
 
 
def decrease(x):
    """
    Decrease x by 1 in 4-base positional numeral system.
    """
    if x == 0:
        return 0
 
    p = 0
    res = 0
    while True:
        last = x % 10
        x = x // 10
        if last == 0:
            last = 3
            res += last * 10 ** p
            p += 1
            continue
 
        last = last - 1
 
        return x * 10 ** (p + 1) + last * 10 ** p + res
 
 
def to_friendly(x):
    p = 0
    res = 0
    while x > 0:
        last = x % 10
        x = x // 10
        last = K2V[last]
        res += last * 10 ** p
        p += 1
 
    return res
 
 
def friendly_n_generator(N):
    x = 10 ** (len(str(N))-1)
    while x > 0:
        x = decrease(x)
        yield to_friendly(x)
 
 
def is_prime(x):
    if x <= 1 or x % 2 == 0:
        return False
    for i in range(3, x // 2 + 1, 2):
        if x % i == 0:
            return False
 
    return True
 
 
def find_biggest_prime(n):
    it = friendly_n_generator(n)
    for i in it:
        if is_prime(i):
            return i
 
 
T = int(input())
N = [int(input()) for _ in range(T)]
 
for n in N:
    print(find_biggest_prime(n))
 


StasFomin 23:35, 16 декабря 2020 (MSK): Ну это первая задача, что я у вас проверяю, так что дам баллы, но цель именно пройти по времени — проблема именно сделать более оптимальный алгоритм, асимптотически  — я пытался PYPY скомпилированной запускать — тоже не прошел TL