자바로 백준 1929 풀기

풀이)

소수를 구하는 방식 중 에라스토테네스의 체는 시간 복잡도가 O(Nlog(logN)) 이다.
최대한 시간을 줄이기 위해 출력에서 StringBuilder을 사용했다.
A % B 에서 A가 0인 경우 continue, B가 0인 경우 continue해주면 시간이 절약된다.
1~M 사이의 소수를 구하기 위해 숫자들을 2~M제곱근 해주면 된다.
M 이하의 숫자들은 모두 1~M제곱근의 약수를 갖기 때문이다.

내 코드)

// 백준 온라인 저지 1929번

import java.io.*;
import java.util.*;

public class Main{
	public static void main(String[]args) throws IOException{
		
		// 입력. 
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		// 배열 만들기
		int arr[] = new int[M+1];
		for(int i=1;i<=M;i++) {
			arr[i] = i;
		}
		// 출력할 때 시간 줄일라고..
		StringBuilder sb = new StringBuilder();
		//에라토스테네스의 체 사용하기
		int k = (int)Math.sqrt(M);
		for(int i=2;i<=k;i++) {
			if(arr[i]==0)
				continue;
			for(int j=i+1;j<=M;j++) {
				if(arr[j]==0) continue;
				else {
					if(arr[j]%arr[i]==0) {
						arr[j]=0;
					}
				}
			}
		}
		arr[1]=0;
		// 답 출력.
		for(int i=N;i<=M;i++) {
			if(arr[i]!=0) {
				sb.append(arr[i]+"\n");
			}
		}
		System.out.println(sb);
		
	}
}