DISCRETE MATH In the lectures we discussed an algorithm for

DISCRETE MATH

In the lectures, we discussed an algorithm for primality testing. For testing whether a natural number n is prime, the number of trial divisions needed for this algorithm is of order n^p for some real number p. Determine p and explain your answer. You do not need to give an exact inequality- based proof based on the definition of order. Using reasonable approximations is enough.

Solution

Solution :- Trial division algorithm for primality testing.

For numbers trial division of N by all primes p < N. For any large integer N,

the number of primes less than N is about 2N/log N .

Thus there will be at most CN /logN operations (where C > 0 is a constant),

So p = CN/logN

This is the required answer.

which tells that the running time could be C N/logN.

So this procedure does not run in polynomial time on the input.