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

에라토스테네스의 체 ( 위키 )

 

프로그래머스 Level 1 소수 찾기 문제 효율성을 통과하기 위해서 알아보았다.

 

코드는 다음과 같다.

 

import java.util.Scanner;

public class Player {

	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in); 
		
		int n = scan.nextInt(); // 2부터서 n 사이에 있는 소수의 개수를 구하기
		
		boolean[] list = new boolean[n+1]; // 배열의 크기는 n+1
		
		list[0]=list[1]=false; // 0과 1은 소수가 아니므로 false
		
		for (int i = 2 ; i<=n ; i++) { // 2부터서 n까지 의 배열에 모두 true값을 넣어준다
			list[i]=true;
		}
		
		for (int i = 2 ; (i*i)<=n ; i++) { // 처음 2는 소수, i*i이 n보다 크지 않으면 된다.
			if (list[i]==true) {
			}
				for (int j = i*i; j<=n; j+=i) { // 소수의 배수에 false를 대입하는 과정
					list[j]=false;
				}
			}
		int answer=0;
		for(int i =0 ; i<=n; i++) {
			if(list[i]==true) {
				answer+=1;
			}
		}
		System.out.println(answer);
	}
}

 

효율성 테스트에 통과했다.

 

ArrayList를 이용하여 구현할 수도 있다.