JAVA 백준 1929 소수 구하기 (약수, 배수와 소수 2)

 

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

 

---

문제

1. 첫째 줄에 자연수 M, N 을 공백으로 구분하여 입력 (1 <= M <= N <= 1000000). M 이상 N 이하의 소수가 하나 이상 있는 입력만 주어짐.
2. 한 줄에 하나씩 증가하는 순서대로 소수를 출력.
3. 이전에 소수를 구할 때 썼던 방식 또는 에라토스테네스의 체를 사용하여 구함.

---

 

최종 코드

import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

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());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        br.close();

        for (int i = M; i <= N; i++) {
            BigInteger number = new BigInteger(String.valueOf(i));
            if (number.isProbablePrime(10)) {
                System.out.println(number);
            }
        }
    }
}

 

채점 진짜 오래 걸려서 시간초과 뜰까봐 채점창만 계속 쳐다봤다...
다행이다 시간초과 안 나서 근데 채점이 왜 이렇게 오래 걸릴까...

 

에라토스테네스의 체: 소수의 배수들을 모두 제외하고 남은 것을 구하는 방식.
2의 배수, 3의 배수, 5의 배수 등을 구하고 싶은 범위 내의 숫자들에서 제외하고 남은 것을 출력한다.

 

 

에라토스테네스의 체를 사용한 코드

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

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());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        br.close();

        boolean[] result = new boolean[N + 1]; // 기본 설정 false

        result[0] = true; // 0과 1은 제외
        result[1] = true;

        for (int i = 2; i <= N; i++) {
            if (!result[i]) {
                for (int j = i + i; j <= N; j += i) { //소수의 배수부터 N까지 제외
                    result[j] = true;
                }
            }
        }

        for (int i = M; i <= N; i++) {
            if (!result[i]) {
                System.out.println(i);
            }
        }
    }
}

 

코드는 조금 복잡하지만 시간도 훨씬 덜 걸린다.

 

for (int j = i + i; j <= N; j += i) 이 부분에서 j를 원래는 i * i로 했었는데 계속 런타임 에러 (ArrayIndexOutOfBound)가 나와서 저렇게 수정했더니 잘 돌아갔다.

->  수정 정보