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

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));

    }

}