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

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

1929번: 소수 구하기

---

---

참고 유형

https://unknownomad.tistory.com/147

[백준] 1978번 : 소수 찾기 - Java

---

구현 방법

• 에라토스테네스의 체 활용

---

풀이

1. Scanner

import java.util.Scanner;

public class Main {
    public static boolean[] prime;
    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        int M = in.nextInt();
        int N = in.nextInt();
		
        prime = new boolean[N + 1];
        get_prime();
				
        for(int i = M; i <= N; i++) {
            if(!prime[i]) { //false = 소수
                System.out.println(i);
            }
        }
    }
 
    //에라토스테네스의 체 알고리즘
    public static void get_prime() {
        //true = 소수 X, false = 소수
        prime[0] = prime[1] = true;
		
        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            if(prime[i]) {
                continue;
            }
            for(int j = i * i; j < prime.length; j += i) { //i의 배수 모두 true
                prime[j] = true;
            }
        }
    }
}

 

2. BufferedReader

import java.util.Scanner;

public class Main {
    public static boolean[] prime;
    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        int M = in.nextInt();
        int N = in.nextInt();
		
        prime = new boolean[N + 1];
        get_prime();
				
        StringBuilder sb = new StringBuilder();
        for(int i = M; i <= N; i++) {
            if(!prime[i]) { //false = 소수 
                sb.append(i).append('\n');
            }
        }
        System.out.println(sb);
    }

    //에라토스테네스의 체 알고리즘
    public static void get_prime() {
        //true = 소수 X, false = 소수
        prime[0] = prime[1] = true;
		
        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            if(prime[i]) {
                continue;
            }
            for(int j = i * i; j < prime.length; j += i) { //i의 배수 모두 true
                prime[j] = true;
            }
        }
    }
}

---

성능

• BufferedReader > Scanner

---

출처 : https://st-lab.tistory.com/84