int i, k = 3;
I'm simply going to delete this line. In general, it is better to declare variables as close to first use as possible. In this case, inside the loop is possible.
for(i = 2; i <= 2000000;){
For every candidate number from 2 to 2,000,000. But I can tell you immediately that about half of those won't be prime. Consider
outer:
for (int i = 3; i <= 2000000; i += 2) {
Now you won't waste your time checking even numbers for primality. There's only one, so you can just skip along once you include it in the sum (which you already did, good work). I'll explain more about the outer: label later.
if (i % 2 == 0){
i++;
k = 3;
}else{
If we're only checking odd numbers, we don't have to check if they are even. We can just delete this (and don't forget the } at the end).
if (i % k == 0 && i != k){
i++;
k = 3;
}else {
if (i == k) {
sum = (sum + i);
i++;
k = 3;
}else {
k = (k + 2);
}
}
Well, looking at it one way, this is rather clever. You increment different variables based on certain conditions. So one for loop effectively loops over two different variables. But from another perspective, it's wasted cleverness. You're making things more complicated for no real gain. It would be better to simply nest another for loop here. Why? Well, let's look at it:
for (int k = 3; k <= i / k; k += 2) {
if (i % k == 0) {
continue outer;
}
}
sum += i;
So from your twelve lines of code, we drop to seven (eight if we count the blank line, but we usually wouldn't).
One of the seven lines is the outer: label. Basically that allows us to say that we are done with the inner loop and want to skip the rest of the current iteration of the outer loop. We will resume (or continue) immediately before the increment step or immediately after the body of the loop (same thing; different descriptions). Note that we could make it more readable by moving the logic to check if an odd prime into a separate method. But this is more like your existing solution.
This moves all the management of k into the for loop. Now our check if i is not prime is much simpler. And we don't have to consider whether or not we want to increment i. We do that every iteration of the outer loop. Nor do we have to think about whether we increment k. We do that every iteration of the inner loop. Your code wasted cleverness on determining whether you wanted to do those things. But nesting the loops does the same thing without cleverness. As such, it is a simpler, more elegant solution.
We also check fewer values here. Note that your loop checked from 2 to i. But we don't need to check to i. If something is a factor, then there must be a factor that is less than or equal to the square root of i. And k <= i / k is the same as k * k <= i or k <= Math.sqrt(i). It's the preferred check here for a few reasons.
k * k may overflow the int size. i / k won't.- In many systems, both
i % k and i / k will be calculated at the same time. So since you would next check i % k, the i / k is almost free (not quite since if it fails, you don't check i % k).
- It is usually cheaper (in time) to compute
i % k than Math.sqrt(k).
The counter-argument would be that you can calculate Math.sqrt(k) once, prior to the loop and save it in a variable. But as I said, in many systems, you only have to calculate i / k separately once and it will almost always be cheaper than calculating the square root.
Time complexity analysis
Only checking odd numbers won't affect the complexity analysis. But it may still make things faster.
The larger change is likely to be stopping at the square root. The square root of a million is a thousand. Would you prefer to do something a million times or a thousand? Hopefully obvious that the square root is better.
Separation of concerns
As noted elsewhere, it is often better to separate different concerns. In this case, one concern is generating the primes and another is summing them (and it would be reasonable to think of checking primality as a third). This is true, but I ignored it to concentrate on improvements to the way that you are doing things now. However, please do not take this as an endorsement of mixing concerns like this. That is not usually recommended except in specific cases where optimization demands it. This probably isn't one of those cases.
For similar reasons, I stuck with testing by trial division rather than using a sieving algorithm. But that doesn't mean that a sieve wouldn't solve this problem more quickly.
