백준 4134 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

소수 찾는 문제다.

 

근데 시간제한과, 메모리 제한 덕에 에라토스테네스 체를 사용하여도 풀 수 없었다.

 

사실 에라토스테네스 체가 문제가 아니라 내가 문제였을 거다.

 

어쨌든 코드먼저 보자.

 

코드

import sys as s

n = int(s.stdin.readline())

for i in range(n):

    a = int(s.stdin.readline())

    while True:

        if a < 2 :

                print(2)

                break

        for j in range(2,int(a**0.5)+1):

            if a % j == 0:

                a+=1

                break

        else:

            print(a)

            break

이 코드를 이해하기 위해 우리는 한 가지 알아야 할 점이 있다.

 

소수를 구하기 위해 보통 2 ~ 대상 수 -1까지 나눗셈을 진행하며, 나누어지는지 여부를 판단한다.

 

하지만 해당 방법으로 진행할 경우, 대상 수가 커지면 대략 2n만큼 연산의 수가 증가하게 된다.

 

대상 수의 범위가 4억까지이니, 1초 이내에 최적의 컨디션으로 연산을 진행하여도 찾아낼 수 없다.

 

근데 정수론에 대상수**0.5+1 까지만 진행하면 소수 여부를 판별할 수 있단다.

 

각 경우마다 최대 연산수가 20001회를 넘지 않는다.

 

와우

 

배운 점

1. 소수를 판별할 때 2~ 대상수**0.5 - 1까지 나눠봄으로 판별할 수 있다.