[정수론/파이썬] 3^n - 1이 소수가 되는 n 찾기

# '친절한 수론 길라잡이' 연습문제 14.3.a

# "(n>=2 이면) 3^n - 1은 항상 짝수이므로 소수가 될 수 없다. # 하지만, (3^n-1)/2가 소수인 
# 경우는 종종 있다. 예를 들어, (3^3 - 1)/2 = 13은 소수이다.
# a) (3^n - 1)/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   # 끝까지 나눠지지 않을 경우, 소수로 판정하고 리턴한다.


for i in range(2, 60):
  ans = (3**i)//2
  if isPrime(ans):
    print("----------", i, ans)
  else:
    print(f"{i}, {ans}는 소수가 아닙니다.")

# 자연수의 제곱수 구하기
count = 0
for i in range(1, 100000000000):
  count += 1
  print(i, i**2, "(", count, ")")

결과:

2, 4는 소수가 아닙니다.
---------- 3 13
4, 40는 소수가 아닙니다.
5, 121는 소수가 아닙니다.
6, 364는 소수가 아닙니다.
---------- 7 1093
8, 3280는 소수가 아닙니다.
9, 9841는 소수가 아닙니다.
10, 29524는 소수가 아닙니다.
11, 88573는 소수가 아닙니다.
12, 265720는 소수가 아닙니다.
---------- 13 797161
14, 2391484는 소수가 아닙니다.
15, 7174453는 소수가 아닙니다.
16, 21523360는 소수가 아닙니다.
17, 64570081는 소수가 아닙니다.
18, 193710244는 소수가 아닙니다.
19, 581130733는 소수가 아닙니다.
20, 1743392200는 소수가 아닙니다.
21, 5230176601는 소수가 아닙니다.
22, 15690529804는 소수가 아닙니다.
23, 47071589413는 소수가 아닙니다.
24, 141214768240는 소수가 아닙니다.
25, 423644304721는 소수가 아닙니다.
26, 1270932914164는 소수가 아닙니다.
27, 3812798742493는 소수가 아닙니다.
28, 11438396227480는 소수가 아닙니다.
29, 34315188682441는 소수가 아닙니다.
30, 102945566047324는 소수가 아닙니다.
31, 308836698141973는 소수가 아닙니다.
32, 926510094425920는 소수가 아닙니다.
33, 2779530283277761는 소수가 아닙니다.
34, 8338590849833284는 소수가 아닙니다.
35, 25015772549499853는 소수가 아닙니다.
36, 75047317648499560는 소수가 아닙니다.
37, 225141952945498681는 소수가 아닙니다.
38, 675425858836496044는 소수가 아닙니다.
39, 2026277576509488133는 소수가 아닙니다.
40, 6078832729528464400는 소수가 아닙니다.
41, 18236498188585393201는 소수가 아닙니다.
42, 54709494565756179604는 소수가 아닙니다.
43, 164128483697268538813는 소수가 아닙니다.
44, 492385451091805616440는 소수가 아닙니다.
45, 1477156353275416849321는 소수가 아닙니다.
46, 4431469059826250547964는 소수가 아닙니다.
47, 13294407179478751643893는 소수가 아닙니다.
48, 39883221538436254931680는 소수가 아닙니다.
49, 119649664615308764795041는 소수가 아닙니다.
50, 358948993845926294385124는 소수가 아닙니다.
51, 1076846981537778883155373는 소수가 아닙니다.
52, 3230540944613336649466120는 소수가 아닙니다.
53, 9691622833840009948398361는 소수가 아닙니다.
54, 29074868501520029845195084는 소수가 아닙니다.
55, 87224605504560089535585253는 소수가 아닙니다.
56, 261673816513680268606755760는 소수가 아닙니다.
57, 785021449541040805820267281는 소수가 아닙니다.
58, 2355064348623122417460801844는 소수가 아닙니다.

...