[알고리즘] 백준 4134 파이썬 - 다음 소수

 

4134번: 다음 소수

 

문제

정수 n(0 ≤ n ≤ 4*10**9)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

 

 

문제풀이

import sys
input = sys.stdin.readline
#01
def sosu(x):
    if x==0 or x==1:
        return False
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True
#02
for i in range(int(input())):
    x=int(input().rstrip())
    while True:
        if(sosu(x)):
            print(x)
            break
        x+=1

- 소수를 구하는 것이기에 에라토스테네스의 체를 사용할 수도 있지만, 

  문제의 입력 범위가 4*10**9 즉 엄청 큰 수이다. 그렇기에 시간 초과로 문제를 풀 수 없다.

 

- #01 : 소수를 판독하는 함수이다. 소수이면 True, 소수가 아니면 False를 반환한다.

- #02 : for문을 통해 x를 입력받고 while문을 통해 x가 소수이면 바로 출력하고 멈춘다.

           만약 소수가 아니라면 x를 1더해서 x보다 같거나 큰 것 중에 가장 가까운

           소수를 찾아 출력하고 while문을 종료한고 for문을 반복한다.