자바(백준) 1929 소수 구하기

풀이 방법

boolean형 visit배열을 전부 true로 초기화시켜 visit의 index가 소수일 경우 값을 true로, 아닐 경우는 false로 바꾸었다. 그래서 마지막에 visit 값이 true인 곳만 출력시켜 답을 구했다. 소수를 판별하는 것은 에라토스테네스의 체 개념을 사용하여 구현했다.

 

사용 개념

에라토스테네스의 체

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        int num1 = Integer.parseInt(st.nextToken());
        int num2 = Integer.parseInt(st.nextToken());
        
        boolean visit[] = new boolean[num2+1];
        Arrays.fill(visit, true);
        visit[0] = false;
        visit[1] = false;
        for(int i = 2; i <= num2; i++){
            if(visit[i] == false) continue;
            
            for(int j = 2 * i; j <= num2; j += i)
                visit[j] = false;
        }
        
        for(int index = num1; index <= num2; index++){
            if(visit[index]) sb.append(index + "\n");
        } 
        System.out.print(sb);
    }
    
}