[Inflearn] 소수

인프런의 자바(Java)알고리즘 문제풀이 입문:코딩테스트 대비 강좌의 강의를 보고 문제 해설을 작성해보았습니다.

 

섹션2. Array(1,2차원 배열)의 5. 소수 강의편 입니다.

 

설명

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

 

입력

첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

 

출력

첫 줄에 소수의 개수를 출력합니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 소수 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		solution(num);
	}
	public static void solution(int n) {
		int cnt = 0;
		int[] arr = new int[n+1];
		for(int i=2; i<=n; i++) {
			if(arr[i] == 0) { //소수
				cnt++;
				for(int j=i; j<=n; j=j+i) {
					arr[j] = 1;
				}
			}
		}
		
		System.out.println(cnt);
	}
}

>> 해설

 

먼저 배열을 선언하면 배열엔 0으로 초기화 되어 있다.

이 상태에서 2부터 n까지 반복하면서 arr[인덱스] 가 0일 경우에는 소수이므로 cnt값을 1 증가시킨다.

그리고 다음 for문은 해당 i의 배수인 것의 arr[인덱스] 값을 1로 변경한다.

그래서 j는 i부터 j는 n까지 i씩 증가하면서(j+i) arr[인덱스]의 값을 0-> 1로 변경한다.