[BOJ, 백준] 4233 가짜소수 Python

import sys
import random
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def power(x, y, p):
    res = 1
    x = x % p
    while y > 0:
        if y & 1:
            res = (res * x) % p
        y = y >> 1
        x = (x * x) % p
    return res

def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

def miller_rabin(n, a):
    r = 0
    d = n - 1
    while d % 2 == 0:
        r += 1
        d = d // 2

    x = power(a, d, n)
    if x == 1 or x == n - 1:
        return True

    for i in range(r - 1):
        x = power(x, 2, n)
        if x == n - 1:
            return True
    return False


def is_prime(n):
    alist = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
    if n == 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    for a in alist:
        if n == a:
            return True
        if not miller_rabin(n, a):
            return False
    return True


def pollardRho(n):
    if is_prime(n):
        return n
    if n == 1:
        return 1
    if n % 2 == 0:
        return 2
    x = random.randrange(2, n)
    y = x
    c = random.randrange(1, n)
    d = 1
    while d == 1:
        x = ((x ** 2 % n) + c + n) % n
        y = ((y ** 2 % n) + c + n) % n
        y = ((y ** 2 % n) + c + n) % n
        d = gcd(abs(x - y), n)
        if d == n:
            return pollardRho(n)
    if is_prime(d):
        return d
    else:
        return pollardRho(d)

def jud_prime(p): #단순히 소수 측정만 하는 것
    divisor_prime = []
    while p > 1:
        divisor = pollardRho(p)
        divisor_prime.append(divisor)
        p //= divisor

    if len(divisor_prime) == 1: #소수인 경우
        return True
    else:
        return False

def f(a, n, p):
    if n == 1:
        return a % p
    if n % 2 == 0:
        return (f(a, n // 2, p) ** 2) % p
    else:
        return (a * (f(a,n // 2, p) ** 2)) % p

def solution(p, a):
    # p가 소수라면, 문제의 조건을 만족하지 않으므로, no를 반환
    if jud_prime(p) == True:
        return 'no'

    # p가 소수가 아니라면?
    if f(a, p, p) == a:
        return 'yes'
    else:
        return 'no'

while True:
    p, a = map(int,input().split())
    if p == 0 and a == 0:
        break

    print(solution(p, a))

 

 

폴라드- 로 / 밀러 - 라빈을 활용한 소인수분해 및 소수 판정

그리고 분할정복을 활용한 코드