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

## '친절한 수론 길라잡이' 96~97쪽
# N^2 + 1 형태의 소수는 무수히 많다.
# 무수히 많은 N에 대해 N^2 + 1이 소수이거나 소수의 곱이라는 사실을 증명하였다.

# 해당 숫자가 소수인지 판정하는 함수
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   # 끝까지 나눠지지 않을 경우, 소수로 판정하고 리턴한다.


MAX_NUM = 1000000000000
count = 0
for i in range(2, MAX_NUM, 2):
  answer = i ** 2 + 1
  if isPrime(answer):  # 만일 소수라면
    count += 1
    print(f"{i} ^2 + 1 = {answer}    {count}")

결과:

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
36 ^2 + 1 = 1297    10
40 ^2 + 1 = 1601    11
54 ^2 + 1 = 2917    12
56 ^2 + 1 = 3137    13
66 ^2 + 1 = 4357    14
74 ^2 + 1 = 5477    15
84 ^2 + 1 = 7057    16
90 ^2 + 1 = 8101    17
94 ^2 + 1 = 8837    18
110 ^2 + 1 = 12101    19
116 ^2 + 1 = 13457    20
120 ^2 + 1 = 14401    21
124 ^2 + 1 = 15377    22
126 ^2 + 1 = 15877    23
130 ^2 + 1 = 16901    24
134 ^2 + 1 = 17957    25
146 ^2 + 1 = 21317    26
150 ^2 + 1 = 22501    27
156 ^2 + 1 = 24337    28
160 ^2 + 1 = 25601    29
170 ^2 + 1 = 28901    30
176 ^2 + 1 = 30977    31
180 ^2 + 1 = 32401    32
184 ^2 + 1 = 33857    33
204 ^2 + 1 = 41617    34
206 ^2 + 1 = 42437    35
210 ^2 + 1 = 44101    36
224 ^2 + 1 = 50177    37
230 ^2 + 1 = 52901    38
236 ^2 + 1 = 55697    39
240 ^2 + 1 = 57601    40
250 ^2 + 1 = 62501    41
256 ^2 + 1 = 65537    42
260 ^2 + 1 = 67601    43
264 ^2 + 1 = 69697    44
270 ^2 + 1 = 72901    45
280 ^2 + 1 = 78401    46
284 ^2 + 1 = 80657    47
300 ^2 + 1 = 90001    48
306 ^2 + 1 = 93637    49
314 ^2 + 1 = 98597    50
326 ^2 + 1 = 106277    51
340 ^2 + 1 = 115601    52
350 ^2 + 1 = 122501    53
384 ^2 + 1 = 147457    54
386 ^2 + 1 = 148997    55
396 ^2 + 1 = 156817    56
400 ^2 + 1 = 160001    57
406 ^2 + 1 = 164837    58
420 ^2 + 1 = 176401    59
430 ^2 + 1 = 184901    60
436 ^2 + 1 = 190097    61
440 ^2 + 1 = 193601    62
444 ^2 + 1 = 197137    63
464 ^2 + 1 = 215297    64
466 ^2 + 1 = 217157    65
470 ^2 + 1 = 220901    66
474 ^2 + 1 = 224677    67
490 ^2 + 1 = 240101    68
496 ^2 + 1 = 246017    69
536 ^2 + 1 = 287297    70
544 ^2 + 1 = 295937    71
556 ^2 + 1 = 309137    72
570 ^2 + 1 = 324901    73
576 ^2 + 1 = 331777    74
584 ^2 + 1 = 341057    75
594 ^2 + 1 = 352837    76
634 ^2 + 1 = 401957    77
636 ^2 + 1 = 404497    78

.........