Linear Sieve Method for Prime Numbers

2195 단어 method
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("
The sum of the prime numbers is %lu
",count);

38  }

Reference material: C 언어 명제 베스트 100 테크닉 편 in Chinese.
js 클립보드 로 복사, 모든 브 라 우 저 호 환
CTF - 텀 블 러. - WEB 의 비밀 을 찾 아 주세요.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage