Question

A number is prime if it can be divided exactly only by 1 and itself. Here is an algorithm for checking if an input number is prime:

function out = isprime(m)

            for j:=2 to m-1

            if mod(m,j) ==0 then

            return “input is not a prime”

            endif

            endfor

            return ”input is a prime”

Let n denote the size of the input m, i.e. the number of bits in the binary expression for m. What is the running time of the algorithm as a function of n? (that is, give the running time in the form O(f(n)) for the appropriate function f). Can you suggest an asymptotically faster algorithm?

Answer 1

Solution for the problem is given below, please comment if any doubts:

Complexity of the given algorithm:

Here the prime number checking algorithm takes the input ‘m’ and check for prime number.

The “for” loop needs to runs from whole “2” to “m-1” in worst case, that is if the number is prime the algorithm needs to check each and every number from “2” to “m-1”, here “n” denotes the input size in binary. For “m” number the number of bits, n= floor(log₂(m))+1

(n-1)= floor(log₂(m))

m = (2^n-1), in average case

Now the complexity is in order of O(m), in the function of n, it is O(2^n-1)

Asymptotically faster algorithm:

• In the given algorithm the for loop checks from “2” to “m-1”, but theories said that we need to check only up to square root of (m).
• Thus the given algorithm can be modified by replacing “for j:=2 to m-1” with “for j:=2 to square_root(m)”.
• The complexity will be reduced from O(m) to O(√m).
• In terms of n, O(2^(n-1)/2)