백준 1929: 소수 구하기(JAVA) / 에라토스테네스의 체

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

소수를 판별하는 알고리즘은 여러가지가 있다.

 

숫자 하나에 대하여 소수인지 판단할 때는 해당 숫자의 제곱근까지만 약수인지 아닌지 반복문을 돌리면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다. 특정 수를 나눴을 때 몫은 항상 그 수의 제곱근 이하이기 때문이다.

 

 

하지만 여러 개의 소수를 한꺼번에 판별해야할 경우는 에라토스테네스의 체를 이용한다.

*에라스토스테네스의 체

소수를 판별할 범위만큼 배열을 할당하고 소수가 아니면 하나씩 지워나가는 방법

1. 소수를 판별한 범위 크기 만큼 배열을 할당한다.
2. 2부터 배열의 끝까지 해당  자리의 숫자의 배수인 숫자들은 소수가 아니라고 표시한다. 해당 자리의 수가 이미 소수가 아니라고 판별된 수라면 넘어간다. 
3. 2부터 시작하여 남아있는 수를 모두 출력한다.

 

 

package sv01; 
import java.util.*;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int n, m;

		n=sc.nextInt();
		m=sc.nextInt();
		boolean[] arr = new boolean[m+1];
		/*
		 * i가 소수가 아닌 경우 arr[i]=true
		 * boolean은 초기값이 false임
		 */
		arr[1] = true; //1은 소수가 아님
		
		for(int i=2; i<=m; i++) {
			if(arr[i]==true)
				continue;
			
			for(int j=2*i; j<=m; j+=i)
				arr[j]=true;
		}
		
		for(int i=n; i<=m; i++)
			if(!arr[i])
				sb.append(i+"\n");
		
		System.out.print(sb);
		sc.close();
	}
}