Define a function that takes one integer argument and returns logical value true or false depending on if the integer is a prime.
Per Wikipedia, a prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.
You can not assume that the integer will be only positive. You may be given negative numbers as well (or 0).
NOTE on performance: There are no fancy optimizations required, but still the most trivial solutions might time out. Numbers go up to 2^31 (or similar, depends on language version). Looping all the way up to n, or n/2, will be too slow.
Input: integer
Output: boolean based on whether or not input is prime
Edge Cases:
- Account for negative numbers
- Account for 0
Assumption: input is always an integer
Criteria: num is prime IF greater than 1 && there are no positive divisors other than 1 and num
Initial Pseudocode:
IF num is greater than 1 => perform the following:
- divide num by every number less than its value
- IF result is a positive number that is neither 1 nor num and is without a remainder, return false out of function (num is not prime)
- ELSE IF => when down to lowest value closest to 1 => return true out of function (num is prime)
ELSE => return false out of function
All solutions passed sample test suite provided by Codewars
function isPrime(num) {
if (num > 1) {
for (let i = num - 1; i >= 0; i--) {
if (num % i === 0 && i !== num && i !== 1) {
return false
} else if (i === 1) {
return true
}
}
} else {
return false
}
}
Runtime for tests: 283 ms (yikes, definitely timed out!)
Refactor needed due to timeout. Given this function is using a for loop to decrement by 1 from very large numbers (determined by tests), it takes an incredibly long time to run this code against the test suite.
Considering what I know about division, the input divided by 1 will lead to a quotient that is equal to the input itself. The next possible number to divide by is 2. At this point, I realized there was never a need to decrement by 1 from the num - 1 as i, instead, I could cut that runtime in half by reducing the size of the loop by 50%. This is done with the following change to the initial value of i in the for loop below.
function isPrime(num) {
if (num > 1) {
for (let i = Math.floor(num / 2); i >= 1; i--) {
if (num % i === 0 && i !== num && i !== 1) {
return false
} else if (i === 1) {
return true
}
}
} else {
return false
}
}
Runtime for tests: 139 ms (still timed out by server, but progress has been made!)
Given the still-excessive runtime of 139 ms, I decided it was time to switch up my approach. For my third attempt at the solution, I aimed to create an array that contained any necessary divisors for the input. This array needed to have a fixed length because looping through it could not lead to a timeout from the server. As I refactored my solution to fit this need, I acknowledged that the test suite was more likely to fail some unit tests when inputs were very large, leading to false positives (non-prime numbers were determined prime).
function isPrime(num) {
if (num > 1) {
const divisors = [2, 3, 4, 5, 6, 7, 8, 9, 10]
let output;
divisors.forEach((digit, i) => {
if (num % digit === 0 && num !== digit) {
output = false
} else if (i === divisors.length - 1 && output === undefined) {
output = true
}
})
return output
} else {
return false
}
}
Runtime for tests: 7 ms (hooray! - failing tests with giant integer inputs, though)
The Big O complexity for these algorithms would be O(n) considering the for loop in the first and second attempts, and the forEach in the third attempt. It is often stated that Big O should not be considered for small problems like these, but where else can you start focusing on Big O if you are not yet working on a company's production code?
My focus on Big O and performance for this challenge has allowed me to further optimize my solutions and strategize for the worst case scenario. My third attempt has a significantly better runtime, but fails to account for the edge case of very large numbers. Any and all ideas for Attempt 4 are welcome!