글 읽기 - [python] 밀러 라빈 소수 판별법 시간 초과

wockd9600 3년 전 0

14%에서 시간초과가 발생합니다.

더 최적화하는 방법이 있을까요

도움 부탁드립니다

import math
import sys
# x^y%m
def powmod(x, y, m):
    r = 1
    while y > 0:
        if y % 2:
            r = (r * x) % m
        y //= 2
        x = x**2 % m
    return r

def miller_rabin(n, a):
    d = (n - 1) // 2
    while (d % 2 == 0):
        if (powmod(a, d, n) == n-1):
            return True
        d //= 2
    tmp = powmod(a, d, n)
    return True if tmp == n-1 or tmp == 1 else False


def isPrime(n):
    if n <= 1:
        return False
    if n <= 100:
        if check[n]:
            return True
        else:
            return False
    for a in alist:
        if not miller_rabin(n, a):
            return False
    return True

check = [True] * 101
for i in range(2, int(math.sqrt(102))+1):
    if check[i]:
        for j in range(i*2, 101, i):
            check[j] = False

t = int(input())
alist = [2, 7, 61]
cnt = 0
for _ in range(t):
    a = int(sys.stdin.readline()) * 2 + 1
    if a % 2 == 1:
        if isPrime(a):
            cnt += 1
print(cnt)

wockd9600 3년 전 1

@jonahan

덕분에 맞았습니다! powmod 안 쓰고 pow 썼더니 메모리 초과 나와서 함수를 한 개 줄였더니 통과되네요

alist에 있는 수는 밀러 라빈으로 판별 안되는 거 알고 있어서 예외처리 했습니다.

진짜 감사합니다!! ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[python] 밀러 라빈 소수 판별법 시간 초과

wockd9600 3년 전 0

wockd9600 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말