projecteuler中问题10的混淆解决方案

Question

我解决了问题 10 in project euler (但我的解决方案花了 2000 秒)，所以我试图找到更快的解决方案。我找到了这个(执行时间 0.1 秒)，但我不明白这个解决方案，我需要帮助。

#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
#define HIGHEST 2000000

char Prime[HIGHEST / 2];

int main(int argc, char** argv)
{
   unsigned int i, j;
   unsigned long long sum = 2;
   unsigned int total = 0;

   /* Set entire array to true (prime) */
   memset(Prime, 1, sizeof(char)*HIGHEST / 2);
   /* except for 1 */
   Prime[0] = 0;

   for(i = 3; i < HIGHEST; i += 2) {
      if(Prime[i / 2] == 1) {
         sum += (unsigned long long)i;
         total++;
      }
      for(j = (i+i+i)/2; j < HIGHEST/2; j += i) {
         Prime[j] = 0;
      }
   }
   printf("Sum: %llu (%d prime numbers)\n", sum, total);
   return 0;
}

Answer 1

解决方案是埃拉托色尼筛法的一个有点奇怪的版本。看起来作者试图通过对循环计数器 i 做一些偷偷摸摸的技巧来过早地进行优化。

我建议您在纸上完成循环的前几次迭代，以了解代码的作用。