A prime number is a whole number that is greater than 1, and it can be only divided by 1 or itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17… Please note 1 is not a prime number. Given a number n, you can check whether the number is a prime number by using iteration and recursion.
Table of Content
Iteration
This is an intuitive method. You can check every integer from 1 to any number that is smaller than itself. If you cannot find a factor, the input is a prime number.
Java
|
1 2 3 4 5 6 7 8 9 10 |
//Iteration, Time O(n), Space O(1) public static boolean isPrime (int n) { if (n <= 1) return false; for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 |
//Iteration, Time O(n), Space O(1) function isPrime (n) { if (n <= 1) return false; for (let i = 2; i < n; i++) { if (n % i == 0) return false; } return true; } |
Python
|
1 2 3 4 5 6 7 8 |
#Iteration, Time O(n), Space O(1) def isPrime (n) : if n <= 1: return False for i in range(2, n): if n % i == 0: return False return True |
Doodle
How to improve the time complexity when checking a number is a prime number?
Due to the symmetry of the factors, the for loop only needs to traverse from 2 to sqrt (n). This improves the time complexity from O(n) to O(sqrt(n)).
Java
|
1 2 3 4 5 6 7 8 9 10 |
//Iteration with fewer loops, Time O(sqrt(n)), Space O(1) public static boolean isPrimeBetter(int n) { if (n <= 1) return false; for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) return false; } return true; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 |
//Improve performance by sqrt(), Time O(sqrt(n)), Space O(1) function isPrimeBetter(n) { if (n <= 1) return false; for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) return false; } return true; } |
Python
|
1 2 3 4 5 6 7 8 |
#Improve performance by sqrt(), Time O(sqrt(n)), Space O(1) def isPrimeBetter(n): if n <= 1: return False for i in range(2, int(math.sqrt(n)+1)): if n % i == 0: return False return True |
Doodle
Recursion
You can also apply the square root to recursion to save the checking time. But due to the call stacks, the space complexity will be O(sqrt(n)) too.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Recursion, Time O(sqrt(n)), Space O(sqrt(n)) public static boolean isPrimeRec(int n) { return primeHelper(n, 2); } //recursion helper, Time O(sart(n)), Space O(sqrt(n)) private static boolean primeHelper(int n, int i) { if (n <= 2) return (n == 2) ? true : false; if (n % i == 0) return false; if (i * i > n) return true; return primeHelper(n, i + 1); } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Recursion, Time O(sqrt(n)), Space O(sqrt(n)) function isPrimeRec(n) { return primeHelper(n, 2); } //Recursion helper, Time O(n), Space O(n) function primeHelper(n, i) { if (n <= 2) // Base cases return (n == 2) ? true : false; if (n % i == 0) return false; if (i * i > n) return true; return primeHelper(n, i + 1); } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#Recursion, Time O(sqrt(n)), Space O(sqrt(n)) def isPrimeRec(n) : return primeHelper(n, 2) #recursion helper, Time O(sart(n)), Space O(sqrt(n)) def primeHelper(n, i): if n <= 2: # Base cases return True if n == 2 else False if n % i == 0: return False if i * i > n: return True return primeHelper(n, i + 1) |
Doodle
Download Java, JavaScript and Python code
Prime recursion doodle
Mathematics in software engineering