실력키우기 > 수학 응용 > 소수(1740)

Question

문제 링크

Solving

'에라토스테네스의 체' 에 대해 공부해봅시다. 소수를 더 쉽고 빠르게 구할 수 있습니다.

Code

Colored By Color Scripter™

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

#include <stdio.h> #include <math.h> #pragma warning(disable:4996)   int m, cnt = 1, sum, min, sosu[1000000], nInput, i = 1;   int main() {     FILE *fin = fopen("input.txt", "r");     FILE *fout = fopen("output.txt", "w");          fscanf(fin, "%d\n%d", &nInput, &m);     min = m;     for (int i = 0; i <= m; i++)         sosu[i] = 1;       int Limit = sqrt(m * 1.0);     for (int i = 2; i <= Limit; i++)     {         if (sosu[i] == 1)         {             for (int j = 2 * i; j <= m; j++)             {                 if (j%i == 0)                     sosu[j] = 0;             }         }     }     sosu[1] = 0;     for (int i = nInput; i <= m; i++)     {         if (sosu[i] == 1)         {             min = (min < i) ? min : i;             sum += i;         }     }     if (!sum)     {         fprintf(fout, "-1\n");         return 0;     }     fprintf(fout, "%d\n%d\n", sum, min); }