Problem
I am trying to solve a challenge in which I have to write a function that takes in two numbers as arguments and returns an array containing numbers between them which are prime and their reverse is also prime in JavaScript. This doesn’t return numbers which are palindrome such as 101.
function backwardsPrime(start, stop) {
let arr = [];
for (let i = start; i <= stop; i++) {
let truth = true;
for (let j = 2; j < i; j++) {
if (i % j === 0) truth = false;
}
if (truth) arr.push(i);
}
return arr.filter(elem => {
let truth = true;
let rev = parseInt(elem.toString().split('').reverse().join(''));
for (let j = 2; j < rev; j++) {
if (rev % j === 0||rev === elem) truth = false;
};
return truth;
});
}
This code works but it is inefficient and takes a long time. So my code isn’t being accepted… So can anyone make this code more efficient along with the explanation of how you did it? I am not experienced with optimizing code myself. This is my first post in code review so please kindly forgive if I had made any mistake or if it’s off-topic.
Solution
Bug?
There may be a bug but this will depend on input range and interpretations.
When given the range 0 to 10 your function returns [0,1,2] all of which do not match the requirements. The first valid number is 13 as it is a prime, reversed 31 a prime, and not a palindrome 13 !== 31.
- 0 and 1 are not primes
- 2 reversed is 2 and thus is a palindrome
I would assume that values under 13 should be ignored.
Style
-
Use const when a variable does not change. For example the variables
arrandrevshould be constants -
Always delimit code blocks (using
{}). Egif (foo) bar = foois better asif (foo) { bar = foo }This will save you hours of bug hunting when you modify code and forget to add the{}if you extend the block. -
The closing
}of aforloop block does not require a semicolon; -
Spaces between operators.
Optimizing
Code review is not really about “How do I…?” so I will only review optimization in the algorithm you have come up with.
-
Break out of loops if the condition you are searching for has been meet. You have two loops (the first finding primes and the second filtering found primes.
Both these loops have an inner loop that will set the semaphore
truthto false on some condition. However when you chage the state oftruthtofalseyou continue looping. You know when you changetruthit will remain so untill the loop is complete so why continue the loop,There are many ways to break out of the loop. See rewrite
-
In JS String manipulation is very slow when compared to Numbers.
The line
let rev = parseInt(elem.toString().split('').reverse().join(''));is on average just under 10 times slower (for random values from1to1e8) than the following functionfunction reverseNumber(num) { var result = 0; while (num) { result = (result *= 10) + (num % 10); num = num * 0.1 | 0; } return result; }Always avoid converting
Numbers toStrings when performance is critical and the task is mathematical in nature -
Avoid known steps. Even when using brute force approaches it pays to use what is know to reduce processing
You know in advance
- that even values can not be prime.
- that. If a
numberis divisible by avaluethen it is also divisible bynumber / value. This means that the maxvalueto check if divisible by is the square root ofnumber - and see hint at bottom of answer.
Thus you can optimize the first loop by starting at an odd value, stepping over even values, and checking divisors up to the square root of the value you are checking.
Rewrite
The rewrite uses your brute force solution with optimizations outlined above.
The rewrite code is 300 times quicker with input 100, 10000. If it can pass the performance requirement I do not know.
The rewrite breaks the task into smaller parts using functions.
function backwardsPrime(start, stop) {
function reverseNumber(num) {
var result = 0;
while (num) {
result = (result *= 10) + (num % 10);
num = num * 0.1 | 0;
}
return result;
}
function isPrime(num) { // num must be odd
var div = 3;
const max = num ** 0.5 + 1;
while (div < max) {
if (num % div === 0) { return false }
div += 1;
}
return true;
}
start = Math.max(start, 13);
var num = start + (start + 1) % 2;
const primes = [];
while (num <= stop) {
isPrime(num) && primes.push(num);
num += 2;
}
return primes.filter(val => {
const rev = reverseNumber(val);
return rev % 2 && rev !== val && isPrime(rev);
});
}
Even faster
The function findPrime (in rewrite above) is a brute force approach and can be replace with any one of many better algorithms.
And a Hint All numbers starting with an even digit (2,4,6,8) can not have a reversed prime. That’s more than half of all odd numbers can quickly be excluded from the need to test if prime.
let arr = [];
This isn’t a generic array, so why not name it primes?
for (let i = start; i <= stop; i++) {
Why are you incrementing by one here? There is exactly one even prime (2). All other even numbers are not prime, as they are divisible by 2 and primes are only divisible by themselves and 1. Try
for (let i = start + (start + 1) % 2; i <= stop; i += 2) {
Now you only have to do half as much work. If you search around on this site, you can see how to also get rid of numbers divisible by 3.
for (let j = 2; j < i; j++) {
There’s a similar problem here. You would be better off checking 2 separately and changing this to
for (let j = 3; j <= i / j; j += 2) {
Note that rather than testing to i, I changed it to something that is effectively j <= Math.sqrt(i). Only I implemented that via simple division. This works because factors come in pairs that multiply to the number. Both factors can’t be larger than the square root because then their product would be larger than the number. So at least one is less than or equal to the square root.
But you’re checking a lot of numbers redundantly even then. For example, if a number is not divisible by 3, then it won’t be divisible by 9, 15, 21, etc. The truth is that if you know the range of numbers, you can do a lot better with a Sieve of Eratosthenes. Then you can mask out the composite numbers, so you don’t have to keep trying them. In this case, you’d use the sieve to find all primes from 2 to stop. Then go through that list from start to stop.
Note that we have a tag for sieve-of-eratosthenes, and you can look at just the questions about Javascript. That should get you at least to the point where you can ask another question if it’s still not fast enough. It might not be. I can think of some more optimizations that you could do. But they will be easier to explain when your code is further along.