fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <stdio.h>
  3. #include<stdlib.h>
  4. #include<math.h>
  5. #include <time.h>
  6. int main(void)
  7. {
  8. 	clock_t start, end;
  9. 	double result;
  10. 	int m, n; // 시작하는 수와 끝의 수를 입력받는다. 
  11. 	scanf("%d %d", &m, &n);
  12. 	int size = n - m + 1;
  13. 	int* eratosthenes = (int*)malloc(sizeof(int) * size); // m이상 n이하의 수들을 일단 먼저 모두 저장한다. 
  14. 	int centinel = (int)sqrt(n); // n의 제곱근의 배수만 지우면 된다. 
  15. 	int flag = 0;
  16. 	start = clock(); //시간 측정 시작
  17. 	for (int i = m, j = 0; i <= n, j < size; i++, j++)
  18. 	{
  19. 		eratosthenes[j] = i;
  20. 	}
  21. 	for (int i = 2; i <= centinel; i++) // 2의 배수부터, end의 배수까지를 제거한다. 
  22. 	{
  23. 		if ((i % 2 == 0 || i % 3 == 0) && flag > 3) // 2의 배수와 2의 배수인 경우는 이미 제거되었으므로 제거할 필요가 없다. 
  24. 													//변수 flag를 이용해서 2와 3인 경우를 지우는 경우를 배제한다. 
  25. 		{
  26. 			continue;
  27. 		}
  28. 		for (int j = 0; j < size; j++)
  29. 		{
  30. 			if (eratosthenes[j] == 1) // 1은 소수가 아니므로 제거한다. 
  31. 			{
  32. 				eratosthenes[j] = 0;
  33. 			}
  34. 			if (eratosthenes[j] == 0) // 이미 지워진 수인 경우, 지울 필요가 없으므로 continue로 pass 한다. 
  35. 			{
  36. 				continue;
  37. 			}
  38. 			if (eratosthenes[j] % i == 0 && eratosthenes[j] != i) // 2의 배수부터 end 의 배수까지를 제거한다, 이때, 자기 자신은 지우지 않는다.  
  39. 			{
  40. 				eratosthenes[j] = 0;
  41. 			}
  42. 		}
  43. 		flag++;
  44. 	}
  45. 	end = clock(); //시간 측정 끝
  46. 	for (int i = 0; i < size; i++)
  47. 	{
  48. 		if (eratosthenes[i] != 0) // 지워지지 않은 eratosthenes 에 저장된 수들을 출력한다. 
  49. 		{
  50. 			printf("%d\n", eratosthenes[i]);
  51. 		}
  52. 	}
  53. 	result = (double)(end - start);
  54. 	printf("%lf", result);
  55. 	free(eratosthenes);
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 5536KB
comments (?)
stdin
copy 
1 2
stdout
copy 
1
2
1.000000
https://ideone.com/eoISA3
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!