# '친절한 수론 길라잡이' 연습문제 13.4
# a) N^2 + 2 형태의 소수는 무수히 많을 것이라 생각하는가?
# b) N^2 - 2 형태의 소수는 무수히 많을 것이라 생각하는가?
# c) N^2 + 3N + 2 형태의 소수는 무수히 많을 것이라 생각하는가?
# d) N^2 + 2N + 2 형태의 소수는 무수히 많을 것이라 생각하는가?
# 해당 숫자가 소수인지 판정하는 함수
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 # 끝까지 나눠지지 않을 경우, 소수로 판정하고 리턴한다.
# a) N^2 + 2 형태의 소수는 무수히 많을 것이라 생각하는가?
# N이 짝수이면 N^2도 짝수, +2를 한 것도 짝수이므로 N은 홀수여야 한다.
# 1부터 시작해서 계산값이 소수인지 검사한다.
print("연습문제 a)===============================================")
for num in range(1, 500, 2): # 1부터 시작해서 홀수만 검사한다
res = num ** 2 + 2
if isPrime(res):
print(num, res)
# b) N^2 - 2 형태의 소수는 무수히 많을 것이라 생각하는가?
# N이 2를 제외한 짝수이면 N^2이 짝수가 되어 -2를 한 것도 짝수가 되므로 소수가 아니다.
# 따라서 N을 홀수로만 검사한다.
# 편의상 N을 3부터 넣어서 계산해서 소수인지 확인한다.
print("연습문제 b)----------------------------------------------")
for num in range(3, 500, 2): # 1부터 시작해서 홀수만 검사한다
res = num ** 2 - 2
if isPrime(res):
print(num, res)
# c) N^2 + 3N + 2 형태의 소수는 무수히 많을 것이라 생각하는가?
# N이 홀수면 N^2 (홀) + 3N(홀) + 2 = 짝수가 되어서 소수가 아님
# N이 짝수면 N^2 (짝) + 3N(짝) + 2 = 짝수가 되어서 소수가 아님
# 확인용 코드
print("연습문제 c)*********************************************")
for num in range(1, 500, 1): # 1부터 시작해서 홀짝 다 검사한다
res = num ** 2 + 3 * num + 2
if isPrime(res):
print(num, res)
# d) N^2 + 2N + 2 형태의 소수는 무수히 많을 것이라 생각하는가?
# N이 홀수이면: N^2(홀) + 2N(짝) + 2 = 홀
# N이 짝수이면: N^2(짝) + 2N(짝) + 2 = 짝 (소수 없음)
print("연습문제 d)*********************************************")
for num in range(1, 500, 1): # 1부터 시작해서 홀짝 다 검사한다
res = num ** 2 + 2 * num + 2
if isPrime(res):
print(num, res)실행:
연습문제 a)===============================================
1 3
3 11
9 83
15 227
21 443
33 1091
39 1523
45 2027
57 3251
81 6563
99 9803
105 11027
111 12323
117 13691
123 15131
147 21611
171 29243
219 47963
225 50627
237 56171
243 59051
249 62003
255 65027
273 74531
297 88211
303 91811
309 95483
321 103043
345 119027
351 123203
363 131771
369 136163
375 140627
387 149771
417 173891
423 178931
429 184043
441 194483
447 199811
453 205211
477 227531
연습문제 b)----------------------------------------------
3 7
5 23
7 47
9 79
13 167
15 223
19 359
21 439
27 727
29 839
33 1087
35 1223
37 1367
43 1847
47 2207
49 2399
55 3023
61 3719
63 3967
69 4759
71 5039
75 5623
77 5927
89 7919
93 8647
103 10607
107 11447
117 13687
119 14159
121 14639
127 16127
131 17159
135 18223
139 19319
145 21023
155 24023
161 25919
169 28559
173 29927
177 31327
183 33487
191 36479
205 42023
211 44519
217 47087
223 49727
231 53359
233 54287
237 56167
239 57119
247 61007
253 64007
257 66047
259 67079
265 70223
267 71287
273 74527
279 77839
285 81223
293 85847
299 89399
301 90599
303 91807
309 95479
313 97967
315 99223
323 104327
335 112223
337 113567
341 116279
355 126023
357 127447
359 128879
371 137639
387 149767
391 152879
399 159199
405 164023
415 172223
421 177239
425 180623
429 184039
435 189223
441 194479
443 196247
447 199807
449 201599
467 218087
469 219959
481 231359
489 239119
491 241079
495 245023
497 247007
연습문제 c)*********************************************
연습문제 d)*********************************************
1 5
3 17
5 37
9 101
13 197
15 257
19 401
23 577
25 677
35 1297
39 1601
53 2917
55 3137
65 4357
73 5477
83 7057
89 8101
93 8837
109 12101
115 13457
119 14401
123 15377
125 15877
129 16901
133 17957
145 21317
149 22501
155 24337
159 25601
169 28901
175 30977
179 32401
183 33857
203 41617
205 42437
209 44101
223 50177
229 52901
235 55697
239 57601
249 62501
255 65537
259 67601
263 69697
269 72901
279 78401
283 80657
299 90001
305 93637
313 98597
325 106277
339 115601
349 122501
383 147457
385 148997
395 156817
399 160001
405 164837
419 176401
429 184901
435 190097
439 193601
443 197137
463 215297
465 217157
469 220901
473 224677
489 240101
495 246017