radoan1202's blog

calculate prime
By radoan1202, history, 2 hours ago, In English

void prime() { cs[0] = cs[1] = 1;

for (int i = 4; i < n; i += 2) cs[i] = 1;

for (int i = 3; i * i <= n; i += 2)
{
    if (cs[i] == 1)continue;

    for (int j = i * i; j <= n; j += (i + i))
       cs[j] = 1;
}

}

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

If you want to make this code a bit more simplistic, move the top line of code into the nested for-loop.

for (int i = 2; i * i <= n; i++)
{
    if (cs[i] == 1) continue;

    for (int j = i * i; j <= n; j += (i + i)) cs[j] = 1;
}

That way, you don't need to eliminate evens manually. I get the purpose of keeping the even case out is to make the nested loop cover only N/2 iterations, but the evens will get kicked out immediately from the cs[i] = 1 case. So, really it is the same time but 1 line shorter and quite neater.

→ Reply