个人描述

这也是一个用空间换时间的方法，速度固然是快，但是你要求多大上限的质数就需要多大上限的数组，这在一定程度上限制的大数的范围。有解决方法？留待以后闲时研究。

应用原理

因式分解定理: 任何一个非质数都可以分解成质数的连乘积

即：合数 n = pkq （p < q)

因此在删除非质数时，如果已知 p 是质数，可以先删除 p2, p3, p4….，接着找出比 p 大的而且没有被删除的数 q，然后删除pq, p2q, p3q…，一直到 pq > n为止。

代码示例：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. #define MAX_COUNT 10000
  5. #define NEXT(x) x = next[x]
  6. #define PREV(x) x = prev[x]
  7. #define REMOVE(x) { next[prev[x]] = next[x]; \
  8.                              prev[next[x]] = prev[x];}
  9. #define INIT(n) { unsigned long i; \
  10.                         for(i = 2; i <= n; i++){ \
  11.                              next[i] = i + 1; \
  12.                              prev[i] = i - 1; \
  13.                       } \
  14.                        prev[2] = next[n] = NULL; \
  15.                       }
  17. int main(int argc, char** argv)
  18. {
  19.     unsigned long num, count;
  20.     unsigned long prime, factor, multi; 
  21.     unsigned long next[MAX_COUNT + 1];
  22.     unsigned long prev[MAX_COUNT - 1];
  24.     printf("%s", "please input the upper num\n");
  25.     scanf("%d", &num);
  27.     INIT(num);
  29.     for(prime = 2; prime * prime <= num; NEXT(prime))
  30.     {
  31.         for(factor = prime; prime * factor <= num; NEXT(factor))
  32.         {
  33.             for(multi = prime * factor; multi <= num; multi *= prime)
  34.             {
  35.                 REMOVE(multi);
  36.             }
  37.         }
  38.     }
  39.     for(prime = 2, count = 0; prime != NULL; NEXT(prime))
  40.     {
  41.          if(count++ % 8 == 0)
  42.          {
  43.               printf("\n");
  44.          }
  45.          printf("%8ld", prime);
  46.      }
  47.      return 0;
  48. }

备注