NYOJ 187 빠 른 검색 소수 (타 표)

3339 단어 소수
주소
사고방식: 일반적인 방법 은 시간 을 초과 하고 시 계 를 친다.알고리즘 분석: 소수 표 치기;
 1 #include<stdio.h>

 2 int a[2000001];

 3 int main()

 4 {

 5     int i,j,n;

 6     for(i=2;i<=2000000;i++)

 7     {

 8         if(!a[i])  //     

 9         for(j=i+i;j<=2000000;j+=i)  //         

10         a[j]=1;  //  

11     }

12     while(scanf("%d",&n),n)

13     {

14         printf("2");

15         for(i=3;i<=n;i++)

16         if(!a[i])

17         printf(" %d",i);

18         printf("
"); 19 } 20 return 0; 21 } 22

좋은 웹페이지 즐겨찾기