프로그래머스 / 연습문제 / 소수 찾기

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

프로그래머스

#include <string>
#include <vector>
 
using namespace std;
 
int solution(int n) {
    int num[1000000];
    int answer = 0;
    //배열에 수 넣기
    for (int i = 2; i <= n; i++)
    {
        num[i] = i;
    }
    for (int i = 2; i <= n; i++)
    {
        //-1일 경우 answer++ 하지 않고 다음 인덱스로 넘어간다.
        if (num[i] == -1)continue; 
         //순서대로 검색하면 자연스럽게 num[i]는 소수이다.
        answer++;
        for (int j = 2; i * j <= n; j++)
        {
            //i(소수)의 배수를 모두 -1 로 바꾸어 for문에 걸리지 않게 한다.
            num[i * j] = -1;
        }
    }
    return answer;
}

에라토스테네스의 체 공식은 다음과 같다.

 

1. 2부터 N까지 모든 수를 쓴다.

 

2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.

 

3. 그 수를 지우고 소수로 저장한다.

 

4. 이제 그 수의 배수를 모두 지운다.

 

해당 공식을 참고하여 코드를 작성했다.

 

 

 

- 획득 점수 = 14점