fork download
copy 
  1. import sys
  2. import math
  3. import random
  4.  
  5. def luythua(x, n, m):
  6.     if n == 0:
  7.         return 1
  8.     y = luythua(x, n//2, m)
  9.     y = (y * y) % m
  10.     if n % 2 == 1:
  11.         y = (y * x) % m
  12.     return y
  13.  
  14. def MillerTest(d, n):
  15.     a = random.randint(2, n-2)
  16.     x = luythua(a, d, n)
  17.     if(x == 1) or (x == n-1):
  18.         return 1
  19.     while d != n-1:
  20.         x = (x*x) % n
  21.         d *= 2
  22.         if(x == 1):
  23.             return 0
  24.         if(x == n-1):
  25.             return 1
  26.     return 0
  27.  
  28. def isPrime(n, k):
  29.     if(n <= 1) or (n == 4):
  30.         return 0
  31.     if(n <= 3):
  32.         return 1
  33.     d = n-1
  34.     while (d % 2 == 0):
  35.         d //= 2
  36.     for i in range(k):
  37.         if MillerTest(d, n) == 0:
  38.             return 0
  39.     return 1
  40.  
  41. n = int(input())
  42. if isPrime(n, 5) == 1:
  43.     print('YES')
  44. else:
  45.     print('NO')
  46.  
Success #stdin #stdout 0.02s 9992KB
comments (?)
stdin
copy 
27
stdout
copy 
NO
https://ideone.com/j2OQOJ
language:
Python (cpython 2.7.16)
created:
3 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!