(정수론/파이썬) 쌍둥이 소수 구하기

### 쌍둥이 소수를 최대한 구해보기
# '친절한 수론 길라잡이' 11쪽 참고
# 쌍둥이 소수: 소수의 목록엔 인접한 홀수 2개가 모두 소수인 경우가 있다... 
# 쌍둥이 소수는 무수히 많을까? 다시 말해, p + 2도 역시 소수인 소수 p가 무수히 많을까?
# 현재는 이 질문에 대한 답은 아무도 모른다.

# 어떤 수가 소수인지 판단. 그 수를 그 수의 루트까지 나눠봐서 나눠지면 소수, 
# 아니면 소수가 아니다.
# 소수이면 1, 아니면 0을 반환
def isPrime(num):
  root_val = round(num ** 0.5) # 제곱근 값을 구한다
  for i in range(2, root_val+1): # 제곱근값+1 까지만 약수를 조사해도 충분하다
    if num % i == 0:  # 중간에 나눠지면 소수가 아니다
      return False
  return True   # 끝까지 나눠지지 않을 경우, 소수로 판정하고 리턴한다.

i = 5  # 현재 수
prev_prime = 3 # 이전에 등장한 소수
count = 0  # 쌍둥이 소수 등장 횟수 
while True: 
  if isPrime(i): # 현재 수가 소수라면
    if i - prev_prime == 2: # 이전의 소수(홀수)가 인접한 소수(홀수)라면
      count += 1
      print(f"({prev_prime}, {i})    {count}")
    prev_prime = i
  i += 2  # 짝수에 대해서는 굳이 소수 여부 조사를 할 필요가 없음. 홀수에 대해서만 조사함

출력:

 

(3, 5)    1
(5, 7)    2
(11, 13)    3
(17, 19)    4
(29, 31)    5
(41, 43)    6
(59, 61)    7
(71, 73)    8
(101, 103)    9
(107, 109)    10
(137, 139)    11
(149, 151)    12
(179, 181)    13
(191, 193)    14
(197, 199)    15

........
(63718931, 63718933)    295748
(63719099, 63719101)    295749
(63719189, 63719191)    295750
(63719309, 63719311)    295751