2-5. 소수의 개수

package 배열1차원2차원.소수의개수2다시5.my;

import java.util.Scanner;

public class Main {

    /**
     * -내 풀이-
     * 소수의 성질을 이용해 풀려고 했지만 이중 for 문이 아니면 안풀려서 해결하지 못함
     *
     * -선생님의 풀이-
     * 에라토스테네스의 체를 이용해 풀면 아주 간단하게 풀린다.
     *
     * cf) 에라토스테네스의 체란?
     * 배열을 만들고 해당 인덱스가 0이면 체크하는 방식이고 체크한 후에 그 인덱스와 인덱스의 배수들을 전부 1로 바꿔줌으로써
     * 해당 인덱스의 배수에 걸렸을 때는 1이기 때문에 체크하지 않는 방식이다.
     *
     * ex) 입력값이 10이면
     * *초기화
     * 2 3 4 5 6 7 8 9 10
     * 0 0 0 0 0 0 0 0 0
     *
     * * i = 2 일때
     * 2 3 4 5 6 7 8 9 10
     * 1 0 1 0 1 0 1 0 1
     * 2와 2의 배수를 1로 바꾸고 1 증가
     *
     * * i = 3 일때
     * 2 3 4 5 6 7 8 9 10
     * 1 1 1 0 1 0 1 1 1
     * 3과 3의 배수를 1로 바꾸고 1 증가
     *
     * ... 이런식으로 계속 나아가는 방식
     *
     * for (int i = 2 ; i <= n ; i++) {
     *     if (ch[i] == 0) {
     *         answer++;
     *         for (int j = i ; j <= n ; j = j + i) {
     *             ch[j] = 1;
     *         }
     *     }
     * }
     */

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int input = kb.nextInt();

        System.out.println(solution(input));
    }

    private static int solution(int input) {
        int answer = 0;
        int[] arr = new int[input + 1];

        for (int i = 2 ; i <= input; i++) {
            if (arr[i] == 0) {
                if (input % i == 0) {
                    arr[i] = 1;
                }
                answer++;
            }
        }

        return answer;
    }
}

 

package 배열1차원2차원.소수의개수2다시5.teacher;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        System.out.println(solution(n));
    }

    private static int solution(int n) {
        int answer = 0;
        int[] ch = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            if (ch[i] == 0) {       // 해당 인덱스 값이 0 이면 카운트를 하나 증가
                answer++;
                for (int j = i ; j <= n ; j = j + i) {  // 이부분이 핵심 j 를 j 의 배수만큼 증가시키면서 for 문을 돈다.
                    ch[j] = 1;
                }
            }
        }

        return answer;
    }
}

 

소수를 수학적으로 접근하면 나는 절대 생각할 수 없었던 문제

 

에라토스테네스의 채를 이용해 푸는 문제 자세한 풀이는 주석 참고