(프로그래머스 c++)소수 찾기

소수 찾는 기본적인 문제..!

종종 알고리즘 문제를 풀다보면 나오는 것 같다..!

그래서 풀이 형태를 외워두는 게 나을 것 같다..!

 

전역 변수로 1000001 크기의 bool 형태 배열을 선언해준다.

2부터 n까지 for문을 돌면서 prime[i]가 false이면 소수이고,

소수의 배수는 소수가 아니기 때문에 true로 바꿔준다.

'에라토스테네스의 체' 알고리즘을 사용했다.

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

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

using namespace std;
bool prime[1000001] = {false, };

int solution(int n) {
    int answer = 0;
    
    for(int i = 2; i <= n; i++)
    {
        if(prime[i] == false)
        {
            answer++;
            prime[i] = true;
            for(int j = i; j <= n; j += i)
                prime[j] = true;
        }
    }
    return answer;
}