fork download
copy 
  1. import sys,random
  2. def miller_rabin_pass(a, s, d, n):
  3.     a_to_power = pow(a, d, n)
  4.     if a_to_power == 1:
  5.         return True
  6.     for i in xrange(s-1):
  7.         if a_to_power == n - 1:
  8.             return True
  9.         a_to_power = (a_to_power * a_to_power) % n
  10.     return a_to_power == n - 1
  11. def miller_rabin(n):
  12.     d = n - 1
  13.     s = 0
  14.     while d % 2 == 0:
  15.         d >>= 1
  16.         s += 1
  17.     for repeat in xrange(20):
  18.         a = 0
  19.         while a == 0:
  20.             a = random.randrange(n)
  21.         if not miller_rabin_pass(a, s, d, n):
  22.             return False
  23.     return True
  24. flag=0
  25. while 1:
  26.     if flag==1:
  27.         break
  28.     a=map(int,raw_input("").strip().split())
  29.     if len(a)!=1:
  30.         continue
  31.     flag=1
  32.     m=a[0]
  33.     while m:
  34.         k=map(int,raw_input("").strip().split())
  35.         if len(k)!=1:
  36.             continue
  37.         b=k[0]-1
  38.         m-=1
  39.         i=0
  40.         while not miller_rabin(b):
  41.             b-=1
  42.         print b
  43.  
Runtime error #stdin #stdout 0.08s 10992KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KQPP9A
language:
Python (cpython 2.7.16)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!