Given a non-negative integer n check if it is a prime number
Prime numbers are positive numbers greater than 1 that are divisible only by 1 and the number itself.
Examples of prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23
Example 1:
Input: n = 31 Output: true
Example 2:
Input: n = 6 Output: false Explanation: 6 is divisible by 2 and 3.
Note:
Your algorithm should run in O(n) time and use O(1) space.
Hints:
Prime numbers are only divisible by the number 1 or itself. Let's reformulate this definition a little bit:
A number
n is prime if and only if there is no such number d such that 1 < d < n and d is a divisor of n.
Is this new definition more helpful?
We should iterate through each number
d from 2 to n - 1 and check if d is a divisor of n.If we find such a number, we can conclude that
n is not prime and return false right away:
for each d : 2 -> n - 1:
if d is divisor of n:
return false
d is divisor of n (or n is a multiple of d) if and only if
n % d == 0:
for each d : 2 -> n - 1:
if n % d == 0:
return false
return true
return true line of code, we know that we haven't found a divisor, so it's safe to say n is prime.
We have a for loop that performs exactly
n - 2 iterations, thus the Time Complexity is O(n).The only extra space we use is the iterator variable
i inside the loop, thus the Extra Space used is O(1).
Walkthroughs of the solution. Try the steps first, then watch to compare approaches.
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check