Участник:Taranov srg/Prime fredly — различия между версиями

Текущая версия на 14:32, 28 декабря 2020

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

Python3

В коде коллеги https://discopal.ispras.ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Morgachev/PRMFN, который не проходил по времени был долгий тест на простоту с перебором множителей, я использовал тест ферма и кроме того у него была некорректная функция итерации по "дружественным числам", это попортило мне крови, в итоге я почти полностью переписал его код, в некотором смысле это полноценное решение задачи.

А нельзя ли зачесть эту задачу в вероятностные алгоритмы, так как основной алгоритм (тест Ферма) вероятностный?

StasFomin 14:32, 28 декабря 2020 (MSK): Это конечно хак, ибо задача проще, чем задача PRIME, для которой да, полиномиальный детерминированных нашли, но он 5 или 6 степень... Т.е. ожидается простой детерминированный, но вы увидели, как можно обмануть заказчика вероятностным с малой ошибкой, что полезно. Ну ладно, пусть будет в вероятностных.

K2V = {
    '0': '2',
    '1': '3',
    '2': '5',
    '3': '7'
}
 
import numpy as np
a_set = np.random.randint(low=2, high=560, size=50)
 
 
def transcript_number(x):
    if x < 2:
        return ''
    digits = list(map(int,list(str(x))))
    new_digits = ''
    counter = 0
    for i in range(len(digits)):
        if digits[i] > 7:
            return new_digits + '3'*(len(digits)-i)
        elif digits[i] == 7:
            new_digits += '3'
        elif digits[i] == 6:
            return new_digits + '2' + '3'*(len(digits)-i-1)
        elif digits[i] == 5:
            new_digits += '2'
        elif digits[i] == 4:
            return new_digits + '1' + '3'*(len(digits)-i-1)
        elif digits[i] == 3:
            new_digits += '1'
        elif digits[i] == 2:
            new_digits += '0'
        else:
            if i == 0:
                return '3'*(len(digits)-i-1)
            return transcript_number(int(str(x)[:i])-1) + '3'*(len(digits)-i)
    return new_digits
 
 
def four_base_decrease(n):
    return (str(int('1' + n) - 1).replace('9', '3'))[1:]
 
 
def four_base_increase(n):
    digits = np.array(list(n))
    l_n = digits.shape[0]
    for i in range(l_n):
        d = int(digits[-i-1]) + 1
        if d == 4:
            digits[-i-1] = '0'
        else:
            digits[-i-1] = str(d)
            return ''.join(list(digits))
    return '0' + '0'*l_n    
 
 
def to_friendly(x):
    return int(''.join([K2V[i] for i in list(x)]))
 
 
def is_prime(x):
    if x <= 1 or x % 2 == 0:
        return False
    for i in range(3, int(x//2)+1, 2):
        if x % i == 0:
            return False
    return True
 
 
def prime_check_via_ferma(n):
    for a in a_set:
        if pow(int(a), n-1, n) != 1:
            return False
    return True
 
 
def find_biggest_prime(n):
    cont = True
    if n == 2:
        return n
    x = transcript_number(n)
    while True:
        i = to_friendly(x)
        if i % 2 and i % 3 and i % 5 and i % 7 and i % 11 and i % 13 and i % 17:
            if i > 560:
                if prime_check_via_ferma(i):
                    return i
            else:
                if is_prime(i):
                    return i
        else:
            if is_prime(i):
                return i
        x = four_base_decrease(x)
 
 
T = int(input())
N = [int(input()) for _ in range(T)]
for i, n in enumerate(N):
    print('Case %d: %d' % (i+1,find_biggest_prime(n)))