[프로그래머스] 1단계 - 소수 찾기

문제 설명

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

프로그래머스

n까지의 소수의 개수 구하기

 

문제 풀이법

소수를 찾는 문제들은 그냥 for문을 냅다 돌려버리면 찾을 수는 있지만 시간 초과가 나기 때문에 에라토스테네스의 체를 이용하면 시간초과 없이 효율적으로 풀 수 있다

 

에라토스테네스의 체란?

소수는 1과 자기자신만으로만 나눠지는 수이기 때문에, 어떤 숫자의 배수일 수는 없다

따라서 for문을 돌면서 배수인 수를 제거하면서 소수만 남겨두는 방법이다 

 

• 우선 1부터 n번째 수까지 배열을 선언한다
• 2부터 시작하여 n번째 수까지 for문을 돌린다
  • for문을 돌리면서 i를 제외한 i번째의 배수를 제거한다
  • ex) i = 2이면 2를 제외한 4부터 n까지 2의 배수를 제거
  • ex) i = 3이면 3을 제외한 6부터 n까지 3의 배수를 제거
  • ex) i = 4이면, 이미 i = 2일때 제거되었기 때문에 바로 i = 5로 넘어감

 

 

소스 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool> v(n + 1, true);
    
    for (int i = 2; i <= n; i++)
    {
        if (v[i] == true)
        {
            for (int j = i + i; j <= n; j += i)
                v[j] = false;
        }
    }
    
    for (int i = 2; i <= n; i++)
    {
        if (v[i] == true)
            answer++;
    }
    return answer;
}