15. 소수의 개수
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
#include <stdio.h>
#include <stdlib.h>
int main(void) {
// int N = 0;
// int res = 0;
// scanf("%d", &N);
// for (int i = 2; i <= N; i++) {
// int flag = 1;
// for (int j = 2; j < i; j++) {
// if (i % j == 0) {
// flag = 0;
// break;
// }
// }
// if (flag == 1) {
// res++;
// }
// }
// printf("%d\n", res);
int N = 0;
int res = 0;
scanf("%d", &N);
int * primeNumber = (int*)malloc(sizeof(int) * N);
for(int i = 2; i < N; i++) {
primeNumber[i] = i;
}
for (int i = 2; i <= N; i++) {
if (primeNumber[i] == 0) {
continue;
} else {
for (int j = i + i; j < N; j += i) {
if (j % i == 0) {
primeNumber[j] = 0;
}
}
}
}
for (int i = 0; i < N; i++) {
if (primeNumber[i] > 0) {
res++;
}
}
free(primeNumber);
printf("%d\n", res);
return 0;
}
C
INFO