C소스 - 소수구하기

2015.03.18. 19:46

알고리즘 숙제라서 짜봤는데 필요하신분 사용하세요~

'에라토스테네스의 체' 란 알고리즘을 이용했습니다.

다른 소스들을 보면 그냥 최대 수만큼 배열을 잡는데...

저는 수 하나를 1bit로 잡았습니다. 어짜피 소수냐 아니냐만 구별하면 되니까요.

이렇게 하면 메모리 용량을 8배 적게 사용합니다.

물론 bit을 계산하는 부분에서 약간의 오버헤드가 있긴 합니다...ㅎ

그래도 1억 까지의 소스를 계산하는데 2.5초정도가 걸리고 약 12MB의 메모리를 차지합니다.

뭐 이정도면 괜찮은 거죠~ㅋ

그런데 1억까지의 소수를 출력하는데만 몇분은 걸릴거 같네요..ㅎ

#include <stdio.h> #include <stdlib.h> #include <string.h> int mygetbit(unsigned char *pPrimeNumber, int index) { int i = index >> 3; // index / 8; int j = index & 0x07; // index % 8; unsigned char bitmask = 1 << j; return (pPrimeNumber[i]&bitmask) ? 1 : 0; } void mysetbit(unsigned char *pPrimeNumber, int index, int value) { int i = index >> 3; // index / 8; 와 같음 int j = index & 0x07; // index % 8; 와 같음 unsigned char bitmask = 1 << j; if(value) { pPrimeNumber[i] = pPrimeNumber[i] | ( bitmask); }else{ pPrimeNumber[i] = pPrimeNumber[i] & (~bitmask); } } int main(void) { int maxnum = 0; int i, j; int arrsize; unsigned char *pPrimeNumber; printf("최대 수 : "); scanf("%d", &maxnum); if(maxnum < 2) { printf("2이상의 숫자이어야 합니다.\n"); return 1; } i = maxnum + 1; arrsize = i / 8 + ((i%8) ? 1 : 0); pPrimeNumber = (unsigned char *)malloc(arrsize); memset(pPrimeNumber, 0xFF, arrsize); // 일단 모든 수들을 소수로 가정 for(i=2;(i*i)<=maxnum;i++) { if(mygetbit(pPrimeNumber, i)) { for(j=i*i; j<=maxnum; j+=i) mysetbit(pPrimeNumber, j, 0); } } printf("찾은 소수들 : "); for(i=2;i<=maxnum;i++) { if(mygetbit(pPrimeNumber, i)) printf("%d ", i); } printf("\n"); free(pPrimeNumber); return 0; }

by Jichan.

참고로... 해설입니다. 덧글 주신 분이 sqrt로 limit을 잡고 +2 을 하는 방법이 있다고 말하셔서 조금 해석을 붙이겠습니다~ㅎ

48번째 라인에 (i*i)<=maxnum 이라고 한 부분은 원래 i<=sqrt(maxnum) 이런식으로 되어있었습니다.

사람도 그렇듯이..ㅎ 컴퓨터도 소수점 계산과 루트계산을 힘들어 합니다.. 그래서 시간이 오래걸리죠.

그래서 양변에 제곱을 해줍니다. (수학이랑 비슷하죠?ㅎㅎ)

(i^2)<=(sqrt(maxnum)*sqrt(maxnum))

(i*i)<=maxnum 이렇게요~

그리고 j=i*i; j<=maxnum; j+=i 이부분...

왜 j=i*2 부터 시작하지 않았냐고 생각할수도 있습니다.

(i*2 으로 해도 결과는 같습니다)

하지만 i*2으로 하면 불필요한 연산을 하게 됩니다.

왜냐구요? i*(i-1) 까지는 이미 처리를 했으니까요~

결과값

최대 수 : 1000 찾은 소수들 : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997