Number Theory: Primality Test in O(sqrt(n))

Priyanka Yadav — Wed, 25 Mar 2020 03:48:23 +0000

A number is said to be prime if it is divisible by a number other than 1 and itself.
1 is not considered to be a prime number.

Primality Test is to determine whether the input integer is a prime number or not.

For instance,

5: Prime Number
12: Not a prime number
7: Prime Number
14: Not a prime number

For instance, 12 is prime because it is divisible by 2,3 and 6.

Approach 1

bool isPrime(int n) {

  if (n == 1) {
    return false;
  }

  for (int i = 2; i < n; i++) {
    if (n % i == 0) return false;
  }

  return true;
}

In this method, we traverse from 1 to n, hence the time complexity, in this case, is: O(n).

Approach 2: The Better One

Now, consider a pair a*b = n. Here, a and b are the factors of n.
For instance,

n = 12
(a,b) can be (1,12),(2,6),(3,4)

On observing the equation, we can infer that the maximum value of a and b can be the square root of n.

sqrt(n)*sqrt(n) = n

Since, if both of the values go beyond sqrt(n), then a*b would be greater than n.

Also, If a is less than sqrt(n), then b will be greater then sqrt(n).
Similarly, if a is greater than sqrt(n), b will be smaller than sqrt(n).

We can conclude that one of the numbers is <= sqrt(n), and the other one is >= sqrt(n).

And to prove that n is prime, we just need to find one of the numbers - a or b.
If no such number exists, it means that n is not prime.

Hence, to do the primality test, we need not run loop till n, this can be done by running the loop till sqrt(n) itself.

bool isPrime(int n) {

  if (n == 1) {
    return false;
  }

  for (int i = 2; i*i < n; i++) {
    if (n % i == 0) return false;
  }

  return true;
}

Note: Using the libraries such as sqrt() can sometimes give unexpected values. Hence, instead of checking for i < sqrt(n) in the for loop, we check for i*i< n.

The loop runs from 2 to sqrt(n), hence the time complexity would be O(sqrt(n)).

Keep Coding! :)

Internet vs World Wide Web vs Intranet

Priyanka Yadav — Thu, 06 Feb 2020 13:46:56 +0000

If you consider Internet as a highway system, you can consider www as a package delivery system that uses that highway.

Internet

global network of networks or
global data communication system
provides an infrastructure
refers mostly to hardware, networks, computer etc.
can be accessed by anyone, is public
provides unlimited information

World Wide Web (www)

collection of information that is accessed via Internet
repository of common resources that can be accessed via the internet.
a service that operates on top of the Internet ( infrastructure )
can be referred as a software

Internet is a public network, while Intranet is a private network.

Intranet

a private network for information management and sharing among only the members or employees
cannot be accessed by everyone
limited number of users with limited information
owned by private firms
is safe as compared to Internet
Example : IT Department intranet, HR Intranet.