[BOJ] 백준 24039번 : 2021은 무엇이 특별할까?

Good Bye, BOJ 2021! A번   -  2021은 무엇이 특별할까?

 

문제 : https://www.acmicpc.net/problem/24039

 

 

문제

연속한 두 소수의 곱으로 이루어져 있으면 특별한 수라 부른다고 약속한다.

주어진 수 N보다 큰 특별한 수 중 가장 작은 수를 구한다.

 

 

 

코드

 

약수는 대칭으로 존재하기 때문에 특정수의 제곱근값보다 작은 수의 범위에서 약수가 존재하지 않으면 제곱근값보다 큰 범위의 수에서도 약수가 존재하지 않는다. 

이 점을 활용하여 소수 판별 함수 is_prime_num() 의 경우 소수 여부를 판단할 숫자가 num일 때 num의 제곱근 만큼만 반복문을 돌게 하여 연산횟수를 줄인다.

 

 2부터 차례로 증가시키며 소수인 수를 구해 소수이면 리스트에 저장한다.

소수를 2개 찾았을 때 이 두 수는 연속적인 소수이므로 두 소수를 곱해 N보다 큰 특별한 수인지 비교한다.

맞으면 출력하고 아니면 두 소수 중 0번째 인덱스에 해당하는 먼저 구한 소수를 제거하고 새로운 소수를 찾아 N보다 큰 특별한 수 인지 검사한다.

 

import math
import sys

input = sys.stdin.readline

n = int(input())


def is_prime_num(num):
    if num == 0 or num == 1:
        return False
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True


p_num = []
i = 2
while True:
	if len(p_num) == 2:
		if p_num[0] * p_num[1] > n:
			print(p_num[0] * p_num[1])
			break
		else:
			p_num.pop(0)
	if is_prime_num(i):
		p_num.append(i)
	i += 1