강한 소수(Strong Prime)란?
어떤 수 n이 주어졌을 때, 이 수가 강한 소수(Strong Prime)인지 확인해야 합니다. 강한 소수란 자신보다 바로 앞에 있는 소수와 바로 뒤에 있는 소수, 즉 인접한 두 소수의 평균보다 큰 소수를 의미합니다.
예를 들어 입력값이 num = 37이라면 결과는 True입니다. 37에 가장 가까운 소수는 31과 41이며, 이들의 평균은 (31 + 41) / 2 = 36입니다. 37은 36보다 크므로 37은 강한 소수에 해당합니다.
문제 해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- num이 소수가 아니거나 num이 2라면 False를 반환합니다. (2는 양쪽에 인접한 소수가 존재하지 않기 때문입니다.)
- last := num - 1, next := num + 1로 초기화합니다.
- next가 소수가 아닌 동안 next를 1씩 증가시켜 다음 소수를 찾습니다.
- last가 소수가 아닌 동안 last를 1씩 감소시켜 이전 소수를 찾습니다.
- avg := (last + next) / 2로 인접한 두 소수의 평균을 계산합니다.
- num이 avg보다 크면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
예제 코드
다음 구현을 통해 더 잘 이해할 수 있습니다.
def isPrime(num):
if num > 1:
for i in range(2, num):
if num % i == 0:
return False
return True
return False
def solve(num):
if isPrime(num) == False or num == 2:
return False
last = num - 1
next = num + 1
while isPrime(next) == False:
next += 1
while isPrime(last) == False:
last -= 1
avg = (last + next) / 2
if num > avg:
return True
return False
num = 37
print(solve(num))
코드 설명
- isPrime(num): 2부터 num-1까지의 수로 나누어 나머지가 0이 되는지 확인하는 방식으로 소수 여부를 판별합니다.
- solve(num): 먼저 num이 소수인지 검사한 후, 위쪽과 아래쪽 방향으로 각각 가장 가까운 소수를 탐색합니다. 그런 다음 두 소수의 평균과 num을 비교하여 강한 소수 여부를 결정합니다.
입력
37
출력
True