백준 4134번(silver 4) : 다음 소수 (소수 판명:에라토스테네스의 체)

 

4134번: 다음 소수

---

 

 내가 작성한 코드 - 시간초과 

import sys
input = sys.stdin.readline

n = int(input().rstrip())
prime_nums= [int(input().rstrip()) for _ in range(n)]

for i in range(0, n):
    check = prime_nums[i]
    for j in range(2, check):
        if check % j == 0:
            check += 1
    print(check)

 

 

 새로 알게 된 것 - 에라토스테네스의 체 

 

소수임을 알아내기 위해 2부터 n-1 까지 나눌 필요 없고, 2부터 n의 제곱근 인지 확인해주면 된다.

 

예를 들어, n이 16이라면 16의 제곱근은 4인데, 16의 약수는 1, 2, 4, 8, 16 으로 제곱근인 4를 기준으로 대칭을 이룬다.

대칭인 2와 8을 보면, 16이 2로 나누어떨어지므로 16이 8로 나누어떨어진다는 것 또한 당연한 사실이다. 따라서 굳이 8을 나눌 필요는 없다.

따라서 2부터 4까지만 구하면 된다.

본래 2부터 15까지 구해야했던 것과는 확실히 비교 횟수가 줄었고, 이를 활용하여 코드를 작성하면 시간 초과가 일어나지 않을 것이다.

 

 

 풀이 참고하여 다시 작성한 코드 

import sys
import math

input = sys.stdin.readline

# 소수 판명하는 함수 정의
def is_primenum(n):
    for i in range(2, math.trunc(math.sqrt(n)+1)):
        if n % i == 0: # 소수가 아니면
            return False
    # for 문이 끝났는데도 나누었는데 나머지가 모두 0이 아니었다면 
    # = 소수
    return True

# 테스트 케이스의 개수 입력
n = int(input().rstrip())

# n줄에 하나씩 입력되는 테스트 케이스를 리스트로 저장
prime_num = [int(input().rstrip()) for _ in range(n)]

for i in range(n):
    while True: # 소수 판명이 나온다면 끝내는 while 문
        # 입력된 수가 0 혹은 1 이면 이 두 수보다 큰 수 중 작은 소수는 2뿐이다.
        if prime_num[i] == 0 or prime_num[i] == 1:
            print(2)
            break
        # 2 이상인 수가 입력된다면
        if is_primenum(prime_num[i]): # True 반환 -> 즉, 소수라면
            print(prime_num[i])
            break
        else: # False 반환 -> 소수가 아니라면
            prime_num[i] += 1 # 그 다음 수를 살펴보기