(정수론/파이썬) N^2 + 1 형태의 소수 구하기

### 친절한 수론 길라잡이, 11쪽
# N^2 + 1 이 소수인 경우가 무한할까? (N = 1, 2, 3...)

# N^2 + 1 형태의 소수. N = 1, 2, 3...을 대입하여 얻은 N2 + 1 형태의 수를 나열해보면,
# 몇몇 소수가 발견된다. N이 홀수이면 N^2 + 1은 짝수이므로 N=1일 때를 제외하고는 N^2 + 1이
# 소수일 리 없다. N에 짝수를 대입하는 경우만 생각해보자.

# 해당 숫자가 소수인지 판정하는 함수
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 = 2  # 2부터 2씩 증가시켜 대입한다
count = 0  # 소수 등장 횟수

while True:
  num = i ** 2 + 1
  if isPrime(num):
    count += 1
    print(f"{i} ^2 + 1 = {num}     ({count})")
  i += 2   # 홀수에는 관심없고 짝수만 취급한다.

출력:

2 ^2 + 1 = 5     (1)
4 ^2 + 1 = 17     (2)
6 ^2 + 1 = 37     (3)
10 ^2 + 1 = 101     (4)
14 ^2 + 1 = 197     (5)
16 ^2 + 1 = 257     (6)
20 ^2 + 1 = 401     (7)
24 ^2 + 1 = 577     (8)
26 ^2 + 1 = 677     (9)

.......

776740 ^2 + 1 = 603325027601     (42981)
776770 ^2 + 1 = 603371632901     (42982)
776780 ^2 + 1 = 603387168401     (42983)
776786 ^2 + 1 = 603396489797     (42984)