[백준][C++]1978번. 소수 찾기

https://www.acmicpc.net/problem/1978

 

소수를 찾는 문제이다. 나는 n이 100이하이고 n의 수도 1000이하라서 반복문을 순회하면서 소수인지 판별했으나

에라토스테네스의 체를 통해 소수를 미리 구해두고 확인하는 방식이 훨씬 효율적이다. 

밑은 에라토스테네스의 체를 설명한 그림이다. 소수를 찾고 그 배수는 모두 소수에서 제외시키는 방식으로 소수가 아닌것을 제외하면 된다.

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 "iostream"
#include "vector"
#include "cmath"

using namespace std;

bool isValue(int n)
{
	if (n == 1) return false;
	
	for (int i = 2; i < n; i++)
	{
		if (n % i == 0) return false;
	}

	return true;
}

vector<int> v;
int main()
{
	int n, cnt = 0;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int j;
		cin >> j;
		v.push_back(j);
	}

	for (int i = 0; i < v.size(); i++)
	{
		if (isValue(v[i])) cnt++;
	}

	cout << cnt << endl;
	return 0;
}

 

시간복잡도를 줄인 버전

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 에라토스테네스의 체로 소수 목록을 생성
vector<bool> sieve(int max) {
    vector<bool> is_prime(max + 1, true);
    is_prime[0] = is_prime[1] = false; // 0과 1은 소수가 아님

    for (int i = 2; i * i <= max; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= max; j += i) {
                is_prime[j] = false;
            }
        }
    }

    return is_prime;
}

int main() {
    int n, count = 0;
    cin >> n;
    
    vector<int> numbers(n);
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
    }

    // 1000까지의 소수를 구하기 위해 에라토스테네스의 체 실행
    vector<bool> is_prime = sieve(1000);

    // 입력된 숫자들에 대해 소수인지 확인
    for (int i = 0; i < n; i++) {
        if (is_prime[numbers[i]]) {
            count++;
        }
    }

    cout << count << endl;
    return 0;
}