from sys import stdin
def isPrime(n):
'''
參考 http://www.csie.ntnu.edu.tw/~u91029/Prime.html
質數判定
'''
if(n in [2,3,5]): return 1
if(n%2 == 0): return 0
if(n%6 not in [1,5]): return 0
u = n - 1
t = 0
while(u % 2 == 0):
u >>= 1
t += 1
sprp = [2, 7, 61]
for sk in sprp:
a = sk % n
if (a == 0 or a == 1 or a == n-1): continue
x = pow(a, u, n)
if (x == 1 or x == n-1): continue
for i in range(t-1):
x = pow(x, 2, n)
if (x == 1): return 0
if (x == n-1): break
if (x != n-1): return 0
return 1
r = ['非質數', '質數']
for s in stdin:
v = isPrime(int(s))
print(r[v])
2020/03/06
[zerojudge] a007: 判斷質數
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言