# [SOLVED] How to Optimise my code that computes the sum of all from less than 2 million

## Issue

I’ve tried this problem from Project Euler where I need to calculate the sum of all primes until two million.

This is the solution I’ve come up with –

``````#include <stdio.h>

int main() {
long sum = 5;  // Already counting 2 and 3 in my sum.
int i = 5;     // Checking from 5
int count =  0;
while (i <= 2000000) {
count = 0;
for (int j = 3; j <= i / 2; j += 2) {
// Checking if i (starting from 5) is divisible from 3
if (i % j == 0) {   // to i/2 and only checking for odd values of j
count = 1;
}
}
if (count == 0) {
sum += i;
}
i += 2;
}
printf("%ld ", sum);
}
``````

It takes around 480 secs to run and I was wondering if there was a better solution or tips to improve my program.

``````________________________________________________________
Executed in  480.95 secs    fish           external
usr time  478.54 secs    0.23 millis  478.54 secs
sys time    1.28 secs    6.78 millis    1.28 secs
``````

## Solution

With two little modifications your code becomes magnitudes faster:

``````#include <stdio.h>
#include <math.h>

int main() {
long long sum = 5;    // we need long long, long might not be enough
// depending on your platform
int i = 5;
int count = 0;
while (i <= 2000000) {
count = 0;

int limit = sqrt(i);                  // determine upper limit once and for all
for (int j = 3; j <= limit; j += 2) { // use upper limit sqrt(i) instead if i/2
if (i % j == 0) {
count = 1;
break;                          // break out from loop as soon
// as number is not prime
}
}
if (count == 0) {
sum += i;
}
i += 2;
}
printf("%lld ", sum);                   // we need %lld for long long
}
``````

All explanations are in the comments.

But there are certainly better and even faster ways to do this.

I ran this on my 10 year old MacPro and for the 20 million first primes it took around 30 seconds.

Answered By – Jabberwocky

Answer Checked By – Mary Flores (BugsFixing Volunteer)