Notice
Recent Posts
Recent Comments
:: ADVANCE ::
[BitMask] 에라토스테네스의 체 본문
반응형
[BitMask] 에라토스테네스의 체
비트마스크를 이용한 에라토스테네스의 체 구현
에라토스테네스의 체는 빠르게 동작하기 때문에 수행 범위를 늘릴 때 부담이 되는 것은 시간보다는 메모리이다.
체를 구현 할 때 범위 내의 각 정수들의 소수 여부를 저장하기 위해 범위 만큼의 배열 크기를 선언해 두었어야 했는데 비트마스크를 이용하여 이를 줄일 수 있다.
이는 예를 들어 unsigned char로 배열을 잡을 경우 8bit를 사용하여 8개의 정수의 소수 여부를 1 or 0으로 표현, 이를 담은 하나의 정수로 저장하면 된다.
또한 type의 크기 이후 정수를 저장하려면 다음 배열에 다시 그 이후 8개의 정수 소수 여부를 한번에 저장한다.
prime[0] -> 0부터 7까지의 소수 여부 저장 : 10101100 (7 : 소수, 6 : no, 5 : 소수 ... )
prime[1] -> 8부터 15까지의 소수 여부 저장
따라서 하나의 메모리에 8개의 여부를 한번에 저장하기 때문에 평소 사용하던 메모리의 1/8로 줄일 수 있다.
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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | #include <stdio.h> #include <string.h> #define MAX_N 100 int n; // 배열 하나에 총 8개의 정보가 저장됨 // [0] = 000 -> 0부터 7까지 (10000000 7번째) 1byte = 8bit unsigned char prime[(MAX_N + 7) / 8]; void print2(int num) { int sh = 7; int flag = 0; for (; sh >= 0; sh--) { if ((num >> sh) & 1) flag = 1; if (flag) { printf("%d", (num >> sh) & 1); } } } // k가 소수인지 판별 inline bool isPrime(int k) { // 원소가 켜져있는지 판별 // k >> 3 : k / 8과 같음 -> 8개 씩 정보를 저장하기 때문에 // (1 << (k & 7)) -> 하위 7개의 bit만 판단 return prime[k >> 3] & (1 << (k & 7)); } // k가 소수가 아니라고 표시 inline void setComposite(int k) { // 원소 삭제 prime[k >> 3] &= ~(1 << (k & 7)); } void eratosthenes() { memset(prime, 255, sizeof(prime)); setComposite(0); setComposite(1); for (int i = 2; i * i <= n; i++) { if (isPrime(i)) { // i 가 아직 소수이면 for (int j = i * i; j <= n; j += i) { // i의 배수들을 false로 setComposite(j); } } } } void printState(int num) { print2(num); printf("\ti >> 3 : "); print2(num >> 3); printf("\ti & 7 : "); print2(num & 7); printf("\t1 << (i & 7) : "); print2(1 << (num & 7)); printf("\n"); } int main() { int num; scanf("%d", &num); eratosthenes(); for (int i = 1; i <= num; i++) { printf("%d --> \t", i); printState(i); if (isPrime(i)) printf("yes\n"); else printf("no\n"); } return 0; } | 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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | #include <stdio.h> #include <string.h> #define MAX_N 1000 typedef unsigned char type; type prime[(MAX_N + 7) / (sizeof(type) * 8)]; int bitsize = sizeof(type) * 8; int bitinit; int bitSize(int num) { int n = 0; while ((1 << n) <= num) n++; return n - 1; } void init() { bitinit = bitSize(bitsize); } type isPrime(int num) { return prime[num >> bitinit] & (1 << (num & (bitsize - 1))); } void setComposite(int num) { prime[num >> bitinit] &= ~(1 << (num & (bitsize - 1))); } void eratosthenes() { int i, j; memset(prime, ((1 << bitsize) - 1), sizeof(prime)); setComposite(0); setComposite(1); for (i = 2; i * i <= MAX_N; i++) { if (isPrime(i)) { for (j = i * i; j <= MAX_N; j += i) { setComposite(j); } } } } int main() { int n, i; int num; eratosthenes(); scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &num); if (isPrime(num)) printf("yes\n"); else printf("no\n"); } return 0; } | cs |
반응형
'Algorithm > Algorithm' 카테고리의 다른 글
[MST] 크루스칼 알고리즘 (0) | 2016.10.14 |
---|---|
[Bit] bit 개수 세는 함수 (0) | 2016.10.12 |
[STL] vector (0) | 2016.07.04 |
[STL] 어댑터 (0) | 2016.07.02 |
[STL] 알고리즘 (0) | 2016.07.02 |
Comments