# Hackerrank problem -"Another Prime Problem"

I came across this issue in the problem titled: Another Prime Problem. Here's my solution with JavaScript which passed test case-1, but for other test cases it led to timeout.

function processData(input) {
input=input.split('\n');
input.shift();
for(var i=0;i<input.length;i++){
values(input[i]);
}
}
function values(num){
var sum=0;
num=num.split(' ');
for(var i=num[0];i<=num[1];i++){
for(var j=2;j<=i;j++){
if(i%j==0 && isprime(j)){
sum+=j;
}
}
}
console.log(sum)
}
function isprime(val){
let flag=1;
for(var i=2;i<val;i++){
if(val%i==0){
flag=0;
}
}
if(flag==1){
return true;
}
else{
return false;
}
}


What's the issue in this code that leads to timeout?

The above program has a very bad time complexity, I guess due to multiple loops and functions, but not being much experienced with algorithms this is only solution I can think of right now. Any help would be appreciated.

Additional info:

Problem statement in a nutshell: find the sum of prime factors of each number in the range [X,Y].

Input Format: The first line contains T denoting the total number of testcases. First line of each testcase contains two integers X and Y.

Constraints: 1 ≤ T ≤ 10000 2 ≤ X ≤ Y ≤ 10^5

Output Format: Sum of prime factors of each number in the range [X, Y].

Currently my code calculates the sum of primes (i know this cause I'm able to pass first test case) but the remainder of test cases lead to Timeout.

• When trying to check 9999899999, what information is to be expected from divisors beyond 99999? May 4, 2020 at 15:01
• Welcome to CodeReview@SE. May 4, 2020 at 15:44
• @greybeard edited.. May 4, 2020 at 15:45

## 1 Answer

An immediate problem is that is_prime() is expensive, and you call it too many times. Prepare a sufficiently large list of primes in advance (and use a sieve for that).

This will give you a certain performance boost, but I am positive it will not be enough to avoid timeouts. The real problem is with the algorithm: you try to factorize the numbers, and the factorization is hard.

Instead of bruteforcing, do the math homework: how many numbers in the range have a prime $$\p\$$ as a factor? Hint: if there are N of them, they'd contribute N * p to the answer.