Math11다음소수(4134)

문제

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

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

출력

각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

풀이

• std(기준 값)에 +1 씩 하여 %i 로 나누고 나누어 지지 않으면 곧 다음 소수값이다.

코드

import sys
sys.stdin = open("input.txt","rt")

def input():
    return sys.stdin.readline().rstrip()


N = int(input())

def isPrime(x):
    if x < 2: 
        return False;
    for i in range (2,x):
        if x % i == 0:
           return False;
    return True;

while(N):
    N = N-1
    std = int(input())
    while(not isPrime(std)):
        std += 1
    print(std)

또는

import sys
def input():
    return sys.stdin.readline().rstrip()


N = int(input())

for i in range(N):
    std = int(input())
    while(True):
        for j in range(2,std):
            if std % j == 0:               
                break
        else:
            print(std)
            break
        std += 1     

배운 것

C++로 하면 시간초과 안나는데 Python은 난다..

코멘트