본문 바로가기

공부/백준\BeakJoon

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

반응형

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

 

24039번: 2021은 무엇이 특별할까?

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

www.acmicpc.net

 

문제

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

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

 

 

소수란? 1과 자기자신 이외의 수로 나눠지지 않는 1보다 큰 양의 정수

 

 

왜 틀렸었나?

소수는 1부터가 아니다. 2부터이다..!
1을 넣었으면 2 x 3 = 6 을 출력해야 되는데, 1 x 2 = 2 를 출력해 버린 것이었다.

 

list = [1, 2, 3] # 소수 리스트
=> list = [2, 3] # 소수 리스트

으로 수정

 

 

코드

1. 처음 리스트에 소수의 값 2와 3을 넣어준다. list = [2, 3]

 

2. 전과 전전의 소수값을 곱해주고, 입력값보다 큰지 작은지 비교해준다.

 

2.1. 입력값보다 크다면 출력

 

2.2. 입력값보다 작을 시에, 다음 소수를 구해서 리스트에 넣어주고 2를 반복한다.

 

 

list = [2, 3] # 소수 리스트

def is_prime(N):
  while(True):
    N = N + 1
    for i in range(2, N):
      if(N%i==0):
        break
    i = i + 1
    if(i == N):
      return N

num = int(input())

index = 2
while(1):
  prev = list[index-1] * list[index-2]
  if(prev <= num):
    list.append(is_prime(list[-1]))
    index += 1
  else:
     print(prev)
     break

 

 

조금 더 최적화된 코드

소수를 판별하는 방법 중에서, 에라토스테네스의 체를 사용하는 방법 말고 제곱근을 기준으로 하는 방법이 있다.

 

왜? 소수인지 판별할 자연수의 제곱근을 기준으로 그 숫자의 약수들의 곱셈은 대칭적으로 곱셈이 일어나기 때문에 소수판별 시 그 자연수의 제곱근 이하의 수까지만 검사를 하여 검사할 데이터를 줄일 수 있다.

EX) 24를 기준으로 할때,
2 x 12
3 x 8
4 x 6
-- √24 x √24 --
6 x 4
8 x 3
12 x 2

 

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

 

https://clolee.tistory.com/41

 

 

반응형