글 읽기 - 시간초과... 도와주세요!

sohnryang 4년 전 0

위키피디아에 나온 대로 구현했는데, 시간 초과가 뜹니다. 제가 작은 수를 넣어보았더니, 2^n 꼴의 수를 넣으면 무한루프에 걸립니다. 어떻게 수정해야 할까요?

폴라드 로 알고리즘을 돌려서 나온 인수가 소수면 소인수 리스트에 추가하고, 아니면 다시 폴라드 로 알고리즘을 돌렸습니다.

"""
Baekjoon Online Judge #4149
https://www.acmicpc.net/problem/4149
"""
from collections import deque
from math import gcd
from random import choice, randrange

small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

def poly1(x, n):
    return (x ** 2 + 1) % n

def poly2(x, n):
    return (x ** 2 - 1) % n

def pollard_rho(n):
    d = 1
    x = randrange(1, n + 1)
    y = randrange(1, n + 1)
    poly = choice([poly1, poly2])
    while d == 1:
        x = poly(x, n)
        y = poly(poly(y, n), n)
        d = gcd(abs(x - y), n)
    return d

def miller_rabin(n, k):
    if n < 2:
        return False
    for p in small_primes:
        if n < p * p:
            return True
        if n % p == 0:
            return False
    r, d = 0, n - 1
    while r % 2 == 0:
        r += 1
        d //= 2
    for _ in range(k):
        a = randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def factorize(n):
    composites = deque([n])
    factors = []
    while composites:
        composite = composites.popleft()
        if composite == 1:
            continue
        elif miller_rabin(composite, 10):
            factors.append(composite)
        else:
            f = pollard_rho(composite)
            composites.append(f)
            composites.append(composite // f)
    factors.sort()
    return factors

N = int(input())
factors = factorize(N)
for factor in factors:
    print(factor)

sohnryang 4년 전 1

슬랙에 같은 내용으로 질문했는데 답변받았습니다.

@cki86201님, @koosaga님, @jh05013님 감사드립니다.

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

문제

문제

출처

ICPC

시간초과... 도와주세요!

sohnryang 4년 전 0

sohnryang 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말