Hackerrank problem -"Another Prime Problem"

Question

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.

• greybeard: When trying to check 9999899999, what information is to be expected from divisors beyond 99999?
• greybeard: Welcome to CodeReview@SE.
• Shardul Birje: @greybeard edited..

Answer 1

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.