[알고리즘/java] 에라스토테네스의 체 - int형 배열

728x90

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력한다.

 

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

 

반응형

 

배열의 크기를 N+1 크기로 선언한다.

 

그런 다음, for문을 2부터 순회하는데,

 

arr[i]가 0이면, j를 i만큼 계속 값을 더해서 arr[j]의 값을 1로 초기화한다.

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Main  m = new Main();
		Scanner sc = new Scanner(System.in);
		System.out.println(m.solution(sc.nextInt()));
	}
	
	public static int solution(int num) {
		int answer = 0;
		int[] arr = new int[num + 1];
		
		for (int i = 2; i <= num; i++) {
			if(arr[i] == 0) {
				answer++;
				for (int j = i; j <= num; j+=i) arr[j] = 1;
			}
		}
		
		return answer;
	}
}