소수찾기 (에라토스테네스의 채)

문제

나의풀이

import java.util.*;

class Main {
	public int solution(int n) {
			int answer = 0;
			int[] ch = new int[n+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;
					}
				}
			}
			return answer;
		}
		    
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		System.out.print(T.solution(n));
	}
	
}

풀이방법

n+1까지의 동적 배열을 생성해주면 ch = [0,0,0,0,0,0,....]이런 배열이 생성되는데, for문을 통해 2부터 탐색을 시작해서 ch[i]가 0이라면 카운트가 1증가하고,
i의 배수 즉, ch[j] (j=j+i 를 하게되면 배수들만 선택할 수 있다.)를 1로 만들어주면
그 이후로 1은 그냥 지나치게 되므로 배수를 제외시킬수있다.

핵심키워드

for문을 int i =0; i<n; i++ 이런식으로만 써와서 활용법을 잘 몰랐는데...
시작점을 j=i로 지정하고 증가율도 j=j+i 이런식으로 하면 i의 배수들만 골라서 탐색하는 방법을 알아둬야겠다!