[Level1]소수의 합(에라토스테네스의 체) [연습문제] C/C++

소수 찾기

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	result
10	4
5	3

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

#define TRUE 1
#define FALSE 0
#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0, Prime_count = 0;
    int isPrime = TRUE;

    int *arry;
    arry = (int*)malloc(sizeof(int)*(n*2));
    for (int i = 2; i < n; i++) // 1,0 거르고
    {
        arry[i] = i;
    }

    for (int i = 2; i <= n ;i++)
    {
    if (arry[i]==FALSE) continue;
        for (int k = i + i;k <= n; k = k + i)
        {
            /*k=4,6,8,10 ... 2의배수
            k=6,9,12,15... 3의배수
            k=8,12,16,20...4의배수
            .......*/
            arry[k] = FALSE; 

        }
       
        if (arry[i]) Prime_count++;     
    }
    answer = Prime_count;
    return answer;
}