import java.util.*;
class Main {
public int solution(int n){
// 소수점의 개수
int cnt = 0;
// n과 맞추기 위해선 +1
int[] ch = new int[n+1];
// 소수는 2부터 시작이라서 i = 2
for(int i = 2; i <= n; i++){
// ch[i] = 0이면 소수이므로 cnt + 1
if(ch[i] == 0){
cnt++;
현재 소수 i의 배수를 찾기 위한 반복문
for(int j = i; j <= n; j = j+i){
// ch[j] = 1이면 소수가 아니다, j는 i의 배수임으로 소수가 아님
ch[j] = 1;
}
}
}
return cnt;
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
System.out.println(T.solution(n));
}
}
import java.util.*;
class Main {
public int solution(int n){
int cnt = 0;
int[] ch = new int[n+1];
for(int i = 2; i <= n; i++){
if(ch[i] == 0){
cnt++;
for(int j = i; j <= n; j = j+i){
ch[j] = 1;
}
}
}
return cnt;
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
System.out.println(T.solution(n));
}
}
'코딩테스트 > 기초' 카테고리의 다른 글
19. 점수계산 (0) | 2024.12.10 |
---|---|
18. 뒤집은 소수 (1) | 2024.12.10 |
16. 피보나치 수열 (0) | 2024.12.08 |
15. 가위 바위 보 (0) | 2024.12.08 |
14. 보이는 학생 (0) | 2024.12.08 |