Primality test in Python Here is a working Python implementation of primality test. Is there something that I could change in code to achieve a better running time? For more information about algorithm see this post. 

from sympy import *
from sympy.abc import x

n=int(input("Enter a number : "))

def xmat(r,n):
    return Matrix([[2*x, -1], [1, 0]])*rem(1,x**r-1)*(1%n)

def smallestr(n):
    if n==1 or n%2==0:
        return 0
    else:
        r=3
        while r&lt;1000000:
            u=n%r
            if u==0 and r&lt;n:
                return 0
            elif not(u==0) and not(u==1) and not(u==r-1):
                return r
            else:
                r=nextprime(r)

def myisprime(n):
    r=smallestr(n)
    if r==0:
        return n==2
    else:
        xp=(xmat(r,n)**n)*Matrix([[x],[1]])
        return trunc(xp[1],n)==(rem(x*(1%n),x**r-1))**n


if myisprime(n):
    print("prime")
else:
    print("composite")


You can run this code here.

EDIT

To clarify things, this Python code represents my attempt to translate the following PARI/GP code which is very fast.
Ooooh boy, a prime number finder with the question, "how do I make this faster." It's like asking a bartender what their favorite drink is: it really depends. However, before we get to performance, let's tackle some of the stylistic considerations in this code.


Wrap the actual executing code in a if __name__ == '__main__' block.
Follow standard naming conventions for functions and variables (not to mention spacing).
The algorithm you're implementing is fairly complicated. Add some brief comments and docstrings to explain what's going on.
Either use descriptive names for your variables or add comments/docstrings explaining what they are.
Name your constants. Why r &lt; 1000000? This would be clearer if we had something like MAX_PRIME_VALUE = 1000000, r &lt; MAX_PRIME_VALUE.


Now in terms of performance. Are there ways to make this faster? Yes, of course. If you had a dictionary of all prime numbers &lt;= 1000000, then you could do a simple lookup and be done. The ultimate trade-off between runtime and storage space is to simply pre-compute all the answers to your question. Also, it depends on what hardware/software you have available (pure no-library python? Only sympy? Numpy? Numba? Cython? CUDA?). So in order to answer this question, you really need to ask what your use case is and what trade-offs you're able to make.

For the sake of argument, let's use your code above as our basic requirements. Let's say we have access to sympy and basic Python, but nothing else. As a baseline, let's consider a trivial prime number finder that use nothing but pure Python. We'll just count up from 3 up to sqrt(n): it's naive, it's dead simple to write, and it's actually reasonably fast just because Python is a decent language (and it even has an O(sqrt(N)) runtime, which is not a bad place to start):

def naive_is_prime(n):
    if n == 2:
        return True
    if n &lt; 2 or n % 2 == 0:
        return False

    # Consolidated code thanks to GZ0's comment
    return all(n % i != 0 for i in range(3, int(n ** 0.5 + 1), 2)) 


And a couple benchmarks:

%timeit myisprime(11)
1.23 ms ± 26.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit naive_is_prime(11)
1.11 µs ± 47.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)


Uh oh, that's not a good place to begin, with the naive code giving us a 1000x speedup. Well, maybe that's just because the numbers are so small; maybe the overhead of using sympy will shine when we start considering larger primes. Unfortunately, it slows down rapidly, and waiting for it to compute if tiny numbers are prime takes an unbearable amount of time:

%time myisprime(61)
Wall time: 28.3 s


whereas the naive implementation above continues to be almost instantaneous up until fairly large primes:

%timeit naive_is_prime(2**31 - 1)  # 2147483647
2.7 ms ± 160 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)


I think the moral of the story is that "premature optimization is the root of all evil". I fall into this all the time, and even did so while answering this question (I had a more complicated baseline to show off that performed much worse than that trivial code), and it's very tempting to use a fancy package like sympy to accomplish what's not a very fancy problem. Start simple, then look into some common approaches to the problem (like the Sieve approach) and figure out if they actually help you or not.