[백준] 1929번 : 소수 구하기

1929번: 소수 구하기

---

[소수 판별]

소수를 판별하는 간단한 알고리즘은 특정 숫자 x에 대해 2 ~ x의 제곱근까지 나머지연산을 해보며 결과값이 0이면 소수가 아니라고 판별한다.

 

자바의 경우 출력이 많을 수 있으므로 System.out.println()을 이용한다면 메모리와 시간을 많이 잡아먹는다. 따라서 StringBuilder를 이용했다. 혹시 메모제이션으로 할 수도 있지 않을까 했지만 굳이 필요는 없었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static boolean isPrime(int x){
        if(x == 1) return false;

        for(int i=2; i<=Math.sqrt(x); i++)
            if(x % i == 0)
                return false;

        return true;
    }

    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 n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        for(int i=n; i<=m; i++)
            if(isPrime(i))
                sb.append(i).append('\n');

        System.out.println(sb.toString());
    }
}