[Level 1] 소수 찾기 (C++/Python)

C++)

#include <string>
#include <vector>
#include <cmath>
using namespace std;

bool visited[1000003];

int solution(int n) {
    int answer = 0;
    
    for(int i=2; i<=sqrt(n); i++){
        if(!visited[i]){
            for(int j=i*i; j<=n; j+=i){
                visited[j]=true;
            } 
        }
    }
    
    for(int i=2; i<=n; i++){
        if(!visited[i])
            answer++;
    }

    return answer;
}

 

 

 

Python)

def solution(n):
    arr = [False] * 1000001
    
    for i in range(2, int(n**0.5) + 1):
        if arr[i]:
            continue
            
        for j in range(i*i, n + 1, i):
            if not arr[j]:
                arr[j] = True
    
    return len([i for i in range(2, n + 1) if not arr[i]])

 

 

* 에라토스테네스의 체 설명 : https://donggoolosori.github.io/2020/10/16/eratos/