Python으로 쌍둥이 소수(Twin Prime)를 생성하는 방법

쌍둥이 소수(twin primes)란 서로의 차이가 정확히 2인 두 소수로 이루어진 쌍을 말합니다. 가장 작은 쌍둥이 소수로는 {3, 5}, {5, 7}, {11, 13}, {17, 19} 등이 있습니다.

Python에서는 for 루프를 돌면서 각 숫자가 소수인지 검사하는 방식으로 손쉽게 쌍둥이 소수를 생성할 수 있습니다.

구현 예제

def is_prime(n):
   for i in range(2, n):
      if n % i == 0:
         return False
   return True

def generate_twins(start, end):
   for i in range(start, end):
      j = i + 2
      if(is_prime(i) and is_prime(j)):
         print("{:d} and {:d}".format(i, j))

generate_twins(2, 100)

코드 설명

is_prime(n) 함수는 2부터 n-1까지의 숫자로 n을 나누어 보고, 나머지가 0이 되는 경우가 하나라도 있으면 False(소수가 아님)를 반환합니다. 끝까지 나누어떨어지는 수가 없다면 True(소수)를 반환합니다.

generate_twins(start, end) 함수는 start부터 end-1까지 반복하면서 i와 i+2가 모두 소수인지 확인합니다. 두 조건을 동시에 만족하면 해당 쌍을 화면에 출력합니다.

실행 결과

위 코드를 실행하면 다음과 같은 출력이 나옵니다.

3 and 5
5 and 7
11 and 13
17 and 19
29 and 31
41 and 43
59 and 61
71 and 73

참고 사항

위 예제의 소수 판별 방식은 단순 시행 나눗셈(trial division)으로, 범위가 커지면 성능이 떨어질 수 있습니다. 더 큰 범위를 다룰 때는 에라토스테네스의 체(Sieve of Eratosthenes)처럼 효율적인 알고리즘을 사용하는 것이 좋습니다.