[프로그래머스/C++]Lv.1 - 소수 찾기

문제 링크

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

내 풀이

숫자에 약수가 있는지 체크하면된다.
약수가 있으면 false, 없으면 true를 반환하는 함수를 만들어서 체크하였다.

내 코드

#include <string>
#include <vector>

bool count(int n)
{
    if(n==1)
        return false;
    for(int i = 2; i * i <= n; i++)
    {
        if((n/i) * i == n)
            return false;
    }
    return true;
}

using namespace std;

int solution(int n) {
    int answer = 0;
    
    for(int i = 1; i <= n; i++)
    {
        if(count(i))
            answer++;
    }
    
    return answer;
}

다른 사람의 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool> tmp(n+1, true);

    for (int i=2; i<n+1; i++) {
        if (tmp[i] == true) {
            for (int j=2; i*j<n+1; j++) tmp[i*j] = false;
            answer++;
        }
    }

    return answer;
}

다른 사람의 풀이 해석

vector<bool> 컨테이너를 만든 뒤 n+1 의 크기만큼 true로 초기화한다.
그 후 2부터 n+1까지 범위로 for문을 돌리면서 tmp[i]가 true면 (소수면)
해당 숫자의 모든 배수에 해당하는 인덱스의 값을 false로 바꿔버린다. 그 후 answer++한다.
내가 한 방식보다 훨씬 빠르고 가볍다.