Joinc Wiki: sqrt를 이용한 소수구하기

Facebook Joinc 그룹 Joinc QA 사이트

joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다.

#include <stdio.h> 
#include <math.h> 
#include <time.h> 
 
#define MAX 1000000 
int main(void) { 
    int i,j; 
    int flag; 
    int limit; 
    int loop_count; 
    int count; 
    clock_t stime, etime; 
 
    stime = clock(); 
    flag = 1; 
    count = 0; 
    loop_count = 0; 
    for ( i = 2; i <= MAX; i++ ) 
    { 
      if ( i == 2 || (i & 1) == 1 ) 
      { 
        limit = (int)sqrt(i); 
        for ( j = 2; j <= limit; j++ ) 
        { 
          loop_count++; 
          if ( i % j == 0 ) 
          { 
            flag = 0; 
            break; 
          } 
        } 
        if ( flag != 0 ) 
        { 
          //printf("%d\n",i); 
          count++; 
        } 
        flag = 1; 
      } 
    } 
 
    etime = clock(); 
    printf("loop count = %d total prime number = %d\n",loop_count,count); 
    printf("Time : %.3fs\n",(double)(etime - stime)/CLOCKS_PER_SEC); 
    return 0; 
}

테스트 결과

$ ./prime 
loop count = 67240405 total prime number = 78498 
Time : 1.080s