알고리즘/알고리즘(c++)
소수구하기
byeol2ing
2018. 5. 1. 23:09
반응형
- 소수 판별법
. 소수(Prime Number)란?
1과 자기자신 이외에는 나누어 떨어지는 정수가 없는 양의정수
1. 2~N-1까지의 정수로 나누어 보는 방법 - O(N)
2. 2~Sqrt(N)까지의 정수로 나누어 보는 방법 O(N^1/2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | #include<stdio.h> #include<math.h> int is_prime(int n) { int i; for(i=2;i<n;i++){ if(n%i == 0){ return false; } } return true; } int is_prime2(int n) { int i,sqrn; sqrn=(int)sqrt(n); for(i=2; i<=sqrn; i++){ if(n%i==0){ return false; } } return true; } | cs |
- 에라토스테네스의 체
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include<stdio.h> #include<stdlib.h> #include<string.h> int main(int argc, char*argv[]) { if(argc<2){ printf("Usage : prime2[integer]\n"); return 0; } int n=atoi(argv[1]); if(n<2){ printf("Error : n must be greater than 1\n"); return 0; } int *parray; parray = new int [n+1]; if(parray==0){ printf("Error : memory allocation failed\n"); return 0; } memset(parray,0,sizeof(int)*(n+1)); int i,j; for(i=2; i<=n; i++){ if(parray[i]==1) continue; j=i; while((j+=i)<=n){ parray[j]=1; } } for(i=2;i<=n;i++){ if(parray[i]==0) printf("%d",i); } printf("\n"); delete[]parray; return 0; } | cs |
실행결과
반응형