1  import random
 2  
 3  
 4  def try_comp(a, d, n, s):
 5      if pow(a, d, n) == 1:
 6          return False
 7      for i in range(s):
 8          if pow(a, 2 ** i * d, n) == n - 1:
 9              return False
10      return True
11  
12  
13  def primetest(n, r=15):
14      if n < 3: return n == 2
15      if n % 2 == 0: return False
16      s, d = 0, n - 1
17      while True:
18          quo, rem = divmod(d, 2)
19          if rem == 1:
20              break
21          s, d = s + 1, quo
22  
23      for i in range(r):
24          if try_comp(random.randrange(2, n), d, n, s):
25              return False
26      return True
27  
28  
29  print(primetest(
30      16826274250898468911280407749426542060694768486649616295792750595928899095760198861413145674011622196806001189975331140430984389138737798839798102100501250562384543970148324519320707086782480622768727739619400406298163697633506711667490859272493284358461677857576459592581649298303621108919528607436653031634208416252311924449922771895182310841019584155318547423916714195019363678142800559476884532645915293106647126449661258738488043253150745449466402688849719911594517744984668897073482226741417140010936686564467276499458185350171327208056715254738641774818774823242004784520937289671279357019604426730692283732729))
31  print(primetest(2938475483920938745789028764))