[백준] 1929번 소수 구하기

 

문제: M이상  N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

입력:

• 첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어진다.
• M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력: 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

---

 

음 이 문제는 저번주에 풀었던 1979번이랑 비슷한 문제 같다!

그럼 이번에도 sqrt를 사용해야겠다.

 

 

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

public class B1929 {  //소수 구하기
    public static void main(String[] args) throws IOException {

        // 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        //소수 판별
        for(int i = 0; i <= b-a; i++) {
            if(is_prime(a + i)) System.out.println(a + i);
        }
    }

    public static boolean is_prime(int a) {
        if (a == 1) return false;
        else if (a == 2) return true;
        for (int i = 2; i <= Math.sqrt(a); i++)
            if (a % i == 0) return false;
        return true;
    }
}

이렇게 풀어서 맞췄다!

 

근데 더 좋은 방법이 있을까 하여 검색해 보았더니 이 문제는 에라토스테네스의 체를 쓰는 문제라고 한다.

 

이 방법이 더 효율이 좋다고해서 이 방법으로도 풀어봐야겠다.

 

 

JAVA [자바] - 소수 구하는 알고리즘 및 구현 (tistory.com)

JAVA [자바] - 소수 구하는 알고리즘 및 구현

이 글을 참고해서 풀었다!