[프로그래머스] 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.(1은 소수가 아닙니다.)

제한 조건
n은 2이상 1000000이하의 자연수입니다.

 

문제 설명은 쉽지만 해결하기 위해 많은 시간이 들어갔다. 단순히 모든 경우의 수를 탐색할 경우 n의 값이 높아질때 효율성이 떨어져 실패가 되는 경우가 많았다. 

 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    vector<bool> outNumber(n+1,false);
    
    for(int i=2; i*i<=n;i++)
    {
        for(int j =1; j<=n;j++)
        {
            int count = i*j;
            
            if(count/i==1)
            {
                continue;
            }
            
            if(count>n)
            {
                break;
            }
            
             outNumber[count]=true;         
        }
    }
    
    for(int i=2;i<outNumber.size();i++)
    {
        if(false==outNumber[i])
        {
           answer++;
        }
    }
    
    return answer;
}

 

1. i의 제곱을 이용해 i*i가 n보다 높을수 없다는 전제로 for문의 탐색 조건을 줄였다.

2. 기존에 vector에 소수가 아닌수를 전부 추가해 해당 길이만큼 빼는 방법을 이용했지만, 문제는 소수가 아닌 수를 추가할 때 find()함수를 이용하다 보니 검사를 할 때마다 메모리 사용량이 커 문제가 되었다.

3.  vector<bool> outNumber(n+1,false); 배열을 초기화 할때 미리 모든 경우의 수를 넣어두고, i의 배수들(소수가 아닌수)을 bool 타입으로 담아두고 있다가 마지막에 소수인 수를 다시 검사한다.