參考:
http://www.cnblogs.com/coeus/articles/1541722.html原理:
1. 任何一個(gè)合數(shù)都可以表示成一個(gè)質(zhì)數(shù)和一個(gè)數(shù)的乘積
2. 假設(shè)A是一個(gè)合數(shù)，且A = x * y，這里x也是一個(gè)合數(shù)，那么有:
A = x * y; (假設(shè)y質(zhì)數(shù)，x合數(shù))
x = a * b; (假設(shè)a是質(zhì)數(shù)，且a < x)
-> A = a * b * y = a * Z (Z = b * y)
即一個(gè)合數(shù)(x)與一個(gè)質(zhì)數(shù)(y)的乘積可以表示成一個(gè)更大的合數(shù)(Z)與一個(gè)更小的質(zhì)數(shù)(a)的乘積
這也是理解代碼中 if(i%primes[j] == 0)break;的關(guān)鍵
例如: 如果i = 8; 那么由于i%2 == 0; 因此對(duì)于i=8就只需要檢查primes[1]即可，因?yàn)閷?duì)于大于primes[1]的質(zhì)數(shù)，像3，有:
8*3 = 2*4*3 = 12*2
也就是說(shuō)24(8*3=24)并不需要在8時(shí)檢查，在12時(shí)才檢查
代碼:
1 /*
2 * Problem:
3 * given an upper bound like U(integer), print all the primes between 0-U
4 *
5 * Points:
6 * this's a O(n) algorithm, amazing
7 */
8 #include<stdio.h>
9 #include<stdlib.h>
10 #include<string.h>
11 #define MAX_N 250000
12 int N, hash[MAX_N];
13 int pcount, primes[MAX_N];
14
15 void
16 linear_selection()
17 {
18 int i, j;
19 primes[pcount++] = 1;
20 for(i=2; i<=N; i++) {
21 if(!hash[i])
22 primes[pcount++] = i;
23 for(j=1; j<pcount && i*primes[j]<=N; j++) {
24 hash[i*primes[j]] = 1;
25 if(i%primes[j] == 0)
26 break;
27 }
28 }
29 }
30
31 int
32 main(int argc, char **argv)
33 {
34 int i;
35 while(1) {
36 printf("Enter the upper boundary: ");
37 scanf("%d", &N);
38 if(!N)
39 break;
40 memset(hash, 0, sizeof(hash));
41 pcount = 0;
42 linear_selection();
43 for(i=0; i<pcount; i++)
44 printf("%d\n", primes[i]);
45 }
46 }