반응형
문제 : https://www.acmicpc.net/problem/24039
문제
연속한 두 소수의 곱으로 이루어져 있으면 특별한 수라 부른다고 약속한다.
주어진 수 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 의 제곱근 만큼만 반복문을 돌게 하여 연산 횟수를 줄인다.
반응형
'공부 > 백준\BeakJoon' 카테고리의 다른 글
[BEAKJOON] 백준 10845번 : 큐 (0) | 2023.06.16 |
---|---|
[BEAKJOON] 백준 1406번 : 에디터 (0) | 2023.06.11 |
[BEAKJOON] 백준 1874번 : 스택 수열 (0) | 2023.06.03 |
[BEAKJOON] 백준 9012번 : 괄호 (0) | 2023.05.23 |
[BEAKJOON] 백준 1016번 : 제곱 ㄴㄴ 수 (0) | 2022.02.26 |