2
\$\begingroup\$

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.

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

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.