ÃÑ ÆäÀÌÁö ¼ö : 3224

Àüü ÇÔ¼ö/¿ë¾î»çÀü
Facebook Joinc ±×·ì   Joinc QA »çÀÌÆ®



joinc´Â Firefox¿Í chrome¿¡¼­ Å×½ºÆ® Çß½À´Ï´Ù. IE¿¡¼­´Â Å×À̺íÀÌ ±úÁö°Å³ª À̹ÌÁö°¡ º¸ÀÌÁö ¾ÊÀ» ¼ö ÀÖ½À´Ï´Ù. ƯÈ÷ ±¸±Û DocsÀ̹ÌÁöÀÇ °æ¿ì ¿¢¹Úó¸®µÉ ¼ö ÀÖ½À´Ï´Ù.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int print_prime(int n)
{
clock_t start;
int* pArray = NULL;
int i, j;

start = clock();

pArray = (int*)malloc( (n+1) * sizeof(int) );

if(pArray == NULL) {
printf("Error: memory allocation failed\n");
return -1;
}

memset(pArray, 0, sizeof(int)*(n+1));

// ¼Ò¼ö °è»ê 0: ¼Ò¼ö 1: ¼Ò¼öX
for(i = 2; i <= n; i++) {
if(pArray[i] == 0) {
j = i * 2;

while(j <= n) { // ÇÑ ¼ö(¼Ò¼ö)ÀÇ ¹è¼ö´Â ¸ðµÎ ¼Ò¼ö°¡ ¾Æ´Ô
pArray[j] = 1;
j += i;
}
}
}

// ¼Ò¼ö Ãâ·Â
printf("2 ~ %d's prime number: \n", n);
for(i = 2; i <= n; i++) {
if(pArray[i] == 0) {
printf("%d ", i);
}
}
printf("\n");

free(pArray);

printf("\ntime: %.3fs\n", (double)(clock() - start) / CLOCKS_PER_SEC );

return 0;
}

int main(int argc, char* argv[])
{
int n;

if(argc < 2) {
printf("Usage: prime integer\n");
return 0;
}

n = atoi(argv[1]);

if(n < 2) {
printf("Error: integer must be greater than 1\n");
return 0;
}

print_prime(n);

return 0;
}
/*
  • test result
  • 100¸¸ : 0.210s
  • 1000¸¸: 2.260s
  • 1¾ï : 27.910s
*/
EmailÀ» ±âÀÔÇϸé, ´ñ±ÛÀÌ ¸ÞÀÏ·Î Àü´ÞµË´Ï´Ù.