파이썬으로 세 숫자가 인접한 소수인지 확인하는 방법

세 개의 숫자가 주어졌을 때, 이 숫자들이 인접한 소수(adjacent primes)인지 확인해야 하는 경우가 있습니다. 인접한 소수란 두 소수 사이에 다른 소수가 존재하지 않는, 즉 서로 바로 이어지는 소수를 의미합니다.

예를 들어 입력이 nums = [5, 7, 11]이라면, 5 다음 소수는 7이고 7 다음 소수는 11이므로 출력은 True가 됩니다.

문제 해결 접근 방식

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• 세 숫자 중 하나라도 소수가 아니라면 False를 반환합니다.
• x의 다음 소수가 y와 같지 않다면 False를 반환합니다.
• y의 다음 소수가 z와 같지 않다면 False를 반환합니다.
• 모든 조건을 통과하면 True를 반환합니다.

예제 코드

def isPrime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True
    return False

def get_next_prime(num):
    next_prime = num + 1
    while not isPrime(next_prime):
        next_prime += 1
    return next_prime

def solve(x, y, z):
    if isPrime(x) == False or isPrime(y) == False or isPrime(z) == False:
        return False

    next_prime = get_next_prime(x)
    if next_prime != y:
        return False

    if get_next_prime(y) != z:
        return False

    return True

nums = [5, 7, 11]
print(solve(*nums))

입력

[5, 7, 11]

출력

True

코드 설명

• isPrime(num): 2부터 num-1까지 나누어 떨어지는 수가 있는지 검사하여 소수 여부를 판별합니다.
• get_next_prime(num): 주어진 숫자보다 큰 수 중에서 가장 가까운 다음 소수를 찾아 반환합니다.
• solve(x, y, z): 세 숫자가 모두 소수인지 먼저 확인하고, x의 다음 소수가 y이며 y의 다음 소수가 z인지 순차적으로 검증합니다.

이 알고리즘은 시행 나눗셈(trial division) 방식을 사용하기 때문에 숫자가 커질수록 실행 시간이 길어질 수 있습니다. 성능이 중요한 경우 에라토스테네스의 체와 같은 방법으로 소수 판별을 최적화할 수 있습니다.