2021은 무엇이 특별할까?

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	1024 MB	2292	1261	1152	54.909%

문제

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

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

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

입력

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

출력

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

제한

• $1 \le N \le 10\,000$ 1≤N≤10000
  
• $N$은 정수이다. N
  

예제 입력 1

2020

예제 출력 1

2021

예제 입력 2

2021

예제 출력 2

2491

---

풀이

n의 제곱근이랑 가장 가까운 작거나 같은 수를 start라고 할 때

start 값 * (start +1) 값 혹은 (start+1) 값 * (start+2) 값 답이 된다.

1. 에라토스테네의 체 알고리즘으로 n보다 작은 소수를 구한다.
   • 에라토스테네의 체 알고리즘 과정
     1. 2부터 n 까지의 모든 자연수를 나열한다.
     2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
     3. 남은 수 중에서 i의 배수를 제거한다. (i는 소수니까 제거 X)
     4. 더 이상 반복할 수 없을 때까지 2,3 과정 반복
2. n의 제곱근 과 같거나 작은 수들 중 가장 큰 수 인덱스를 start로 지정한다.
3. prime_num[start] * prime_num[start +1] 부터 반복문으로 구해서 n보다 크면 멈춘다.

---

코드

import math

n = int(input())
is_prime_num = [True for i in range(n+1)]
prime_num = []
start = 0

if n<4:
    print(6)
else:
		# 에라토스테네의 체 알고리즘
    for i in range(2, int(math.sqrt(n))+1):
        j = 2
        while i*j <= n:
            is_prime_num[i*j] = False
            j+=1
            
    for i in range(2, n+1):
        if is_prime_num[i] == True:
            prime_num.append(i)
            if i <= int(math.sqrt(n)):
                start = i 

		# 답 찾기 (for문은 한 번 아니면 두번 돌고 나온다.)
    for i in range(prime_num.index(start), len(prime_num)-1):
        result = prime_num[i] * prime_num[i+1]
        if result > n:
            print(result)
            break