자바 알고리즘 문제 풀이 Array Q05_소수(에라토스테네스 체)

설명

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

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

입력

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

출력

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

 

예시 입력1	예시 출력
20	8

 

코드

해설 코드

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

 

 

풀이 및 정리 

에라토스테네스 체 란?
=> 특정범위 내에서 모든 소수를 찾을 때 가장 효율적인 알고리즘, 소수가 되는 수의 배수를 지우면 소수만 남는다.

예를 들어 20을 입력받으면 1부터 20까지의 숫자중 소수를 구해야하는데 에라토스테네스 체를 사용한다면 2부터 소수인지 판단하고 2의 배수를 지운다.(2,4,6,8,10,12,14,16,18...)
3을 판단할 때도 소수인지 판단하고 3의 배수를 모두 지운다.(3,6,9,12,15,18...) 
4를 비교할 때도 마찬가지로 4의 배수를 지운다.(4,8,12,16,20....)
범위 내에 있는 숫자들을 모두 비교 하고나면 소수만 남게 된다!

=> 2, 3, 5, 7, 11, 13, 17, 19  /  8개