문제
접근
n까지의 모든 소수의 개수를 세는 문제이다.
에라토스테네스의 체를 이용하면 쉽게 소수를 찾을 수 있다.
코드
- C++ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <vector>
using namespace std;
int arr[1000001];
int solution(int n) {
int answer = 0;
for(int i = 2; i<=n;i++){
if(arr[i] != 0)
continue;
answer++;
for(int j = i; j<=n;j+=i){
arr[j] = 1;
}
}
return answer;
}
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
def solution(n):
answer = 0
arr = [0 for _ in range(n+1)]
for i in range(2, n+1):
if arr[i] != 0:
continue
answer+=1
for j in range(i, n+1, i):
arr[j] = 1
return answer