[프로그래머스] 소수 찾기

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

프로그래머스

해당 문제는 효율성을 깐깐하게 보기 때문에 에라토스체네스의 체 알고리즘을 사용하지 않으면 대부분 TLE 처리된다.

 

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;


int solution(int n) {
    int answer = 0; 
    vector<int> arr(n+1, 0);
    fastio;

    for (int i = 2; i <= n; i++)
    {
        if (arr[i] != 0) continue;
        for (int j = i + i; j <= n; j += i) arr[j] = 1;
    }
    for (int i = 2; i <= n; i++)
        if (arr[i] == 0) answer++;

    return answer;
}