[프로그래머스] 소수 찾기 level1 (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를 반환

 

 

 

 

 

간단히 for문을 사용하려 했는데 

효율성 문제로 에라토스테네스의 체 를 사용하였다.

 

나의 경우 적용한 것을 간단히 설명 하자면

 

 

---

 

1. 모든 원소를 소수라고 가정한다.

 

2. 어떤 수 의 배수는 소수가 될 수 없으므로 범위안을 돌며 배수는 소수에서 제외시켜준다.

    하지만 가장 작은 수 는 소수가 될수 있다. 

 

    ex) 3 6 9 12 15 의 경우 3은 소수 나머지는 소수가 아니다.

    ex) 예를들어 밑의 코드 j += i 는 i = 2일때, 2의 배수를 제거 하므로 반복문을 돌때 마다 j 의 값을 i만큼(2만큼) 

          더하여 i가 2인 동안은 j는 계속해서 2의 배수가 된다.

 

3.마지막으로 반복문이 끝나고도 소수로 남아있는 것들의 개수를 세어준다.

---

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;



int solution(int n) {
    int answer = 0; 
    int i,j;
    int check[n+1];

    for(i = 2; i <= n; i++) //모든 원소를 소수라고 가정
    {
        check[i] = 1;
    }
    

    for(i = 2; i <= n; i++) // 범위내의 모든 숫자중 배수(소수가 아닌 수)를 지워주기 위한 for문
    {
        if(check[i]==1)
        {
            for(j = 2*i; j <= n; j += i) // 배수를 지워준다.  
            {
                check[j] = 0;
            }
        }
    }

    for(i = 2; i <= n; i++) //check == 1일때는 소수이므로 소수의 개수를 구해준다.
    {
        if(check[i]==1)
        {
            answer++;
        }
    }


    
    return answer;
}

//테스트 실행용

int main(void)
{
    int n;
    cin >> n;
    cout << solution(n);
}