[Silver V] 2021은 무엇이 특별할까? - 24039 (python)

문제 링크

성능 요약

메모리: 31120 KB, 시간: 44 ms

분류

수학, 정수론, 소수 판정, 에라토스테네스의 체

 

문제 설명

백준 온라인 저지의 송년대회 Good Bye BOJ, 2021!의 개최일은 2021년 12월 31일이다. 원이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2021이 무언가 특별하다는 사실을 깨달았다.

그렇다. 2021은 연속한 두 소수 43과 47의 곱이다. 다음에 이런년도가 오려면 무려 470년 뒤인 2491년이 되어야 한다. 원이는 어떤 수가 연속한 두 소수의 곱으로 이루어져 있으면 특별한 수라 부르기로 하였다.

주어진 수보다 큰 특별한 수 중 가장 작은 수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 주어진 수 N𝑁이 주어진다.

출력

첫 번째 줄에 N𝑁보다 큰 특별한 수 중 가장 작은 수를 출력하여라.

 

 

코드

 

 

# 소수 구하기
n=10000
a = [False, False] + [True]*(n-1)
primes = []

for i in range(2, n+1):
    if a[i]:
        primes.append(i)
        for j in range(2*i, n+1, i):
            a[j] = False

N = int(input())

# 연속되는 수를 곱한 값이 N보다 클 경우
for i in range(len(primes)-1):
    num = primes[i]*primes[i+1]
    if N < num:
        print(num)
        break