[NYOJ-187] 빠른 검색 소수 - 매거법, 선별법, 표기법
15283 단어 매거
시간 제한:
1000ms | 메모리 제한: 65535KB
난이도:
3
묘사
지금 너에게 정수 N을 하나 줄게. 빨리 2에 찾아내라고...N 이 수 안에 있는 모든 소수.
입력
양의 정수 N (N<=2000000) 을 제시합니다.
그러나 N은 0으로 프로그램을 종료합니다.
테스트 데이터가 100 그룹을 넘지 않음
출력
2~N 범위의 모든 소수를 출력한다.두 수 사이를 빈칸으로 나누다
샘플 입력
5
10
11
0샘플 출력
2 3 5
2 3 5 7
2 3 5 7 11
【분석】
1 // :
2 // , 1 p， p .
3 // :
4 bool isPrime(int n)
5 {
6 if(n < 2) return false;
7
8 for(int i = 2; i < n; ++i)
9 if(n%i == 0) return false;
10 return true;
11 }
12 // O(n) 1 // ,
2 // :
3 bool isPrime(int n)
4 {
5 if(n < 2) return false;
6 if(n == 2) return true;
7 if(n % 2 == 0) return false;
8 for(int i = 3; i < n; i += 2)
9 if(n%i == 0) return false;
10 return true;
11 }
12 // O(n/2), . 1 /
2 // : n , n 1<d<=sqrt(n) d.
3 // : n , n d 1<d<n.
4 // d sqrt(n), n/d 1<n/d<=sqrt(n) .
5 // :
6 bool isPrime(int n)
7 {
8 if(n < 2) return false;
9 if(n == 2) return true;
10 if(n % 2 == 0) return false;
11 for(int i = 3; i*i <= n; i += 2)
12 if(n%i == 0) return false;
13 return true;
14 }
15 // O(sqrt(n)/2), O((n-sqrt(n))/2).체법구소수의 기본 사상은 1부터 시작하여 특정한 범위 내의 정수를 작은 것부터 큰 것까지 순서대로 배열하고 1은 소수가 아니니 먼저 그것을 체질하는 것이다.나머지 수 중 가장 작은 수를 소수로 선택한 다음 배수를 빼라.체가 비어 있을 때까지 차례대로 유추하다.예: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 22 23 24 25 26 27 28 29 30
1 소수가 아니니 빼라.나머지 수 중 2가 가장 작고 소수이며 2의 배수를 빼고 나머지 수는:
3 5 7 9 11 13 15 17 19 21 23 25 27 29
남은 수 중 3이 가장 작고 소수이다. 3의 배수를 빼고 이대로 가면 모든 수가 다 체질될 때까지 구한 소수는 다음과 같다.
2 3 5 7 11 13 17 19 23 29
1 //
2 #include<cstdio>
3 #define MAXN 2000001
4 int a[MAXN],i,j;
5 int main(){
6 int m;
7 //
8 for(i = 2;i <= 2000000;i++){
9 if(a[i]==0)
10 // ， i
11 for(j = i + i;j <= 2000000;j += i)
12 a[j] = 1;
13 }
14 while(scanf("%d",&m) && m!=0){
15 // [2,m]
16 for(i = 2;i <= m;i++){
17 if(a[i] == 0){
18 printf("%d ",i);
19 }
20 }
21 printf("
");
22 }
23 return 0;
24 } 1 //
2 #include<cstdio>
3 #define MAXN 2000001
4 int a[MAXN],i,j;
5 int main(){
6 int m;
7 while(scanf("%d",&m) == 1 && m!=0){
8 //m ，
9 for(i = 2;i <= m;i++)
10 a[i] =i;
11 //m/2
12 for(i = 2;i <= m/2;i++){
13 if(a[i] != 0){
14 for(j=i+i;j <= m;j += i){
15 // i
16 a[j] = 0;
17 }
18 }
19 }
20 for(i = 2;i <= m;i++){
21 if(a[i] != 0) printf("%d
",a[i]);
22 }
23 // printf("
");
24 }
25 return 0;
26 }NYOJ 서버를 타박하는 김에더 썩을 수 있겠어?
좋은 웹페이지 즐겨찾기
