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.