Hackerrank problem solving practice | Time Complexity: Primality

Solving problems is one of my life-long sources of happiness. I love logging in to hackerrank every day and practicing coding as part of my routine.

The problem I share solution this time is called “Time Complexity: Primality”. In brief, input of this problem is a positive integer and output is “Prime” if the integer is a Prime otherwise “Not Prime”.

Firstly, based on the constraint that range of the input number is 1 ~ 2 × 10 ^9. That means the time complexity is required to be less than O(N). So we’d better figure out a O(log(N)) or O(square root of N) solution.

Key point of codes is traverse the square root of input number!