[프로그래머스/level1/c++] 소수찾기

문제 :

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

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

 

제한 조건 :

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

입출력 예 :

n	result
10	4
5	3

 

코드 :

에라토스테네스의 체를 이용함

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    bool arr[1000001];
    arr[0]=true,arr[1]=true;
    for(int i=2;i<=n;i++){
        if(arr[i])  continue;
        else{
        answer++;
        for(int j=i*2;j<=n;j+=i)    arr[j]=true;
        }
    }
    return answer;
}

 

도움이 된 글 :

coding-factory.tistory.com/600

[Algorithm] 에라토스테네스의 체 - 소수 구하기 (범위)