15. 소수의 개수

#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;
}