[백준/BOJ] 4233번 - 가짜 소수 (Python)

문제링크

https://www.acmicpc.net/problem/4233

4233번: 가짜소수

1. 핵심

1) 10억 이상 소수 판정 

- 에라토스테네스의 체로는 10억 이상의 소수 판정 불가능

- 소수 판정 하는 방법: 제곱근까지 나눠서 확인하기

2) 비트연산을 활용한 거듭제곱

2. 코드(Python)

# https://www.acmicpc.net/problem/4233
# 소수 구하기
def isPrime(n):
    for i in range(2, int(n**0.5)):
        if n % i == 0:
            return False
    return True

# 비트연산 & 제곱
def power(a, p):
    mod = p
    ret = 1
    while p:
        if p & 1 == 1:
            ret *= a
            ret %= mod
        p >>= 1
        a **= 2
        a %= mod
    ret %= mod
    return ret


while True:
    p, a = map(int, input().split())
    if p == 0 and a == 0:
        break
    if not isPrime(p) and power(a, p) == a:
        print("yes")
    else:
        print("no")