5. 소수(에라토스테네스 체)

 

문제

---

 

 

 

참고

---

 

에라토스테네스의 체❔

에라토스테네스의 체

 

 

 

코드

---

 

이 문제는 에라토스테네스의 체를 이용해 간단히 풀었다.

public class Solution {
    public static void solution(int a) {
        int[] arry = new int[a + 1];
//0과 1은 소수가 아니므로 0
        arry[0] = arry[1] = 0;
        int cnt = 0;

//2부터 소수를 구하고자 하는 구간의 수를 배열에 담아준다.
        for (int i = 2; i <= a; i++) {
            arry[i] = i;
        }
        for (int i = 2; i < a; i++) {
            if (arry[i] == 0) continue;
//소수의 배수들을 0으로 만들어준다.
            for (int j = i * 2; j <= a; j += i) {
                arry[j] = 0;
            }
        }
//소수의 개수를 cnt++;
        for (int i = 0; i < arry.length; i++) {
            if (arry[i] != 0) cnt++;
        }
        System.out.println(cnt);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        solution(a);
    }
}