How do i improve the complexity of this randomized primality testing algorithm?

Question

I wrote the following program which returns 1 if a number is prime and 0 if it is composite. Though there's a possibility of falsely identifying a composite as prime .I want suggestions on improving(decreasing) the time complexity for the following algorithm.

int compute(int n)
{
    int x;
    for(int i = 1; i < 100 * sqrt(n); i++)
    {
        x = rand() % ((int)sqrt(n) + 1);
        if(x != 0 && x != 1 && x!=n)
        {
            if(n % x == 0)
            return 0;
        }
    }
    return 1;
}

Answer 1

You might want to take a look at the Miller-Rabin primality test. In this test you use a series of "witness" values and perform some calculations. Each witness calculation gives a result of "composite" or "possibly prime". If you use k witnesses and they all give "possibly prime" results, the probability that the number is actually composite is 1/4^k.

The runtime is O(k log^3 n), which is a substantial improvement over your O(sqrt(n)) algorithm.