Problem description:When we calculate for prime numbers with a sieve method,we delete so many numbers which is not necessary repeatly.For instance,there is a number which consists of 3x7x17x23,and we delete it when we delete the multiples of 3 as we delete the same number when we delete the multiples of 7,17,and 23.Please write a program that will not do these jobs more than once.
Thinking: There is a factorization theorem:every composite number could be decomposed into the multiplication of some primer numbers.Hence,the number can be decomposed in the form of (both of p and q are prime numbers and p < q).Therefore,what we need to remove is:
,
,
...and
,i=1,2,3.....The value of p and q is the numbers which are not removed currently and in a sequence from small to large.It is easy to write the program.
1 #include <stdio.h>
2 #define MAX 1000
3 #define null1 0
4 #define NEXT(x) x=next[x]
5 #define REMOVE(x) { previous[next[x]]=previous[x]; \
6 next[previous[x]]=next[x]; \
7 }
8
9 #define INITIAL(n) { unsigned long i; \
10 for(i=2;i<=n;i++) \
11 previous[i]=i-1,next[i]=i+1; \
12 previous[2]=next[n]=null1; \
13 }
14
15 int main()
16 {
17 unsigned long previous[MAX+1]={0};
18 unsigned long next[MAX+1]={0};
19 unsigned long prime,fact,i,mult;
20 unsigned long n;
21 unsigned long count=0;
22
23 scanf("%lu",&n);
24
25 INITIAL(n); //initial the array
26
27 for(prime=2;prime*prime<=n;NEXT(prime))
28 {
29 for(fact=prime;prime*fact<=n;NEXT(fact))
30 {
31 for(mult=prime*fact;mult<=n;mult*=prime)
32 REMOVE(mult);
33 }
34 }
35 for(i=2;i!=null1;NEXT(i))
36 printf("%lu ",i),count++;
37 printf("\nThe sum of the prime numbers is %lu\n",count);
38 }
Reference material: C语言名题精选百则技巧篇 in Chinese.