#! /usr/bin/env python
# -*- coding: utf-8 -*-

#
# Copyleft (c) 2016, 2033
# ------------------------------------------------------------------------
# Author  : scz <cloudsky@gmail.com>
# Create  : 2016-05-17 16:07
# Modify  : 2023-02-28 14:43
# ------------------------------------------------------------------------
# The only thing they can't take from us are our minds. !H
#

#
# 对指定n进行Rabin-Miller素性检测，移植到Python3
#
# python3 is_prime_pub.py 0xe8d6a4affed9d15fc9ce927a0e02b7ff
# python3 is_prime_pub.py 255706750118772464950224223705208269649
#

import sys, signal, random

def is_composite ( n, s=None, t=None, b=None ) :
    n_1 = n - 1
    if s is None or t is None :
        s   = 0
        t   = n_1
        while True :
            q, r    = divmod( t, 2 )
            if 1 == r :
                break
            s      += 1
            t       = q
        #
        # end of while
        #
        assert( n_1 == 2**s * t )
    s_1 = s - 1
    if b is None :
        #
        # 很多实现没有严格限定上界。
        #
        b   = random.randrange( 2, n_1 )
    x   = pow( b, t, n )
    #
    # 很多实现只检查x是否等于1，难道这些人不知道啥叫与正负一同余吗？
    #
    if 1 == x or n_1 == x :
        return False
    for i in range( s_1 ) :
        x   = pow( x, 2, n )
        if 1 == x :
            return True
        if n_1 == x :
            return False
    #
    # end of for
    #
    return True
#
# end of is_composite
#

def rabin_miller_test ( n, s=None, t=None, b=None, rounds=5 ) :
    if n < 2 :
        return False
    if 2 == n :
        return True
    if 0 == n % 2 :
        return False
    n_1 = n - 1
    if s is None or t is None :
        s   = 0
        t   = n_1
        while True :
            q, r    = divmod( t, 2 )
            if 1 == r :
                break
            s      += 1
            t       = q
        assert( n_1 == 2**s * t )
    s_1 = s - 1
    for r in range( rounds ) :
        if b is None :
            xb  = random.randrange( 2, n_1 )
        else :
            xb  = b
        if is_composite( n, s, t, xb ) :
            return False
    return True
#
# end of rabin_miller_test
#

def is_prime ( n, low_prime=[], rounds=5 ) :
    if n < 2 :
        return False
    if 3215031751 == n :
        return False
    if n in low_prime :
        return True
    for p in low_prime :
        if 0 == n % p :
            return False
    n_1 = n - 1
    s   = 0
    t   = n_1
    while True :
        q, r    = divmod( t, 2 )
        if 1 == r :
            break
        s      += 1
        t       = q
    assert( n_1 == 2**s * t )
    if n < 1373653 :
        return( not any( is_composite( n, s, t, b ) for b in ( 2, 3 ) ) )
    if n < 9080191 :
        return( not any( is_composite( n, s, t, b ) for b in ( 31, 73 ) ) )
    if n < 25326001 :
        return( not any( is_composite( n, s, t, b ) for b in ( 2, 3, 5 ) ) )
    if n < 4759123141 :
        return( not any( is_composite( n, s, t, b ) for b in ( 2, 7, 61 ) ) )
    if n < 118670087467 :
        return( not any( is_composite( n, s, t, b ) for b in ( 2, 3, 5, 7 ) ) )
    if n < 1122004669633 :
        return( not any( is_composite( n, s, t, b ) for b in ( 2, 13, 23, 1662803 ) ) )
    if n < 2152302898747 :
        return( not any( is_composite( n, s, t, b ) for b in ( 2, 3, 5, 7, 11 ) ) )
    if n < 3474749660383 :
        return( not any( is_composite( n, s, t, b ) for b in ( 2, 3, 5, 7, 11, 13 ) ) )
    if n < 341550071728321 :
        return( not any( is_composite( n, s, t, b ) for b in ( 2, 3, 5, 7, 11, 13, 17 ) ) )
    if n < 3825123056546413051 :
        return( not any( is_composite( n, s, t, b ) for b in ( 2, 3, 5, 7, 11, 13, 17, 19, 23 ) ) )
    if n < 318665857834031151167461 :
        return( not any( is_composite( n, s, t, b ) for b in ( 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 ) ) )
    if n < 3317044064679887385961981 :
        return( not any( is_composite( n, s, t, b ) for b in ( 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 ) ) )
    if len( low_prime ) >= rounds :
        return( not any( is_composite( n, s, t, b ) for b in low_prime[:rounds] ) )
    else :
        return rabin_miller_test( n, s, t, rounds=rounds )
#
# end of is_prime
#

if '__main__' == __name__ :
    try :
        signal.signal( signal.SIGINT, signal.SIG_DFL )
        n           = int( sys.argv[1], 0 )
        low_prime   = [2,3]
        low_prime  += [x for x in range(5,2047,2) if rabin_miller_test(x,b=2,rounds=1)]
        print( is_prime( n, low_prime, 5 ) )
    except KeyboardInterrupt :
        print( '\nCtrl-C' )