CODEWITHSUNDEEP
phpalgorithm
user3319461
user3319461

Reputation:

Execution time exceeded

I am trying to find the sum of all primes below 2000000 and here is my code:

$set = 0;
for($i = 1; $i < 2000000; $i++){
    if(is_prime($i)){
        $set += $i;
    }
}

echo $set;

is_prime is the custom function i created to find whether the number is prime or not. The problem is it is taking too much time to execute. Any way to optimize it?

Upvotes: 0

Views: 51

Answers (2)

Steven Martin
Steven Martin

Reputation: 3282

Tell PHP not to time out using set_time_limit in seconds( 0 means infinite)

 set_time_limit(0);

also your loop in not efficient, a prime other than 2 cannot be even , so you should be stepping up with + 2 and add 2 to the starting $set

$set = 2

for($i = 1; $i < 2000000; $i += 2)

Code:

<?php
set_time_limit(0);

$set = 2;  // 2 is a prime number so must be included in the set

for($i = 1; $i < 2000000; $i += 2){
    if(is_prime($i)){
        $set += $i;
    }
}

echo $set;
?>

Upvotes: 2

MrSmith42
MrSmith42

Reputation: 10151

I think the is_prime($i)-method is the bottleneck.

You can calculate all prime numbers (offline) up to 2000000 by using a Sieve of Eratosthenes to store all primes in 2000000 bits (or if you only store the odd numbers: 1000000) that fits in the RAM and makes is_prime($i) O(1) time.

Upvotes: 0

Related Questions