[백준 1929] 소수 구하기 - 자바

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

1929번: 소수 구하기

---

1. 풀이

기존의 소수 구하기를 통해서 입력값에 따라 2부터 하나하나 확인하면 시간초과가 발생하게 된다.

 

소수를 찾는데 O(n)만큼의 시간이 나오고 m만큼의 입력값이 들어오니 O(n^2)만큼의 시간이 들고, 다른 방법을 사용해도 O(n*n^1/2)만큼의 시간 복잡도 나오게 된다.

 

결과적으로 범위의 수에서 소수를 구하는 알고리즘인 '에라토스테네스의 체'를 통해서 구하면 된다.

 

만약 120까지의 소수를 구한다면, 11 * 11 > 120 이므로 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

 

주의할 점 배수를 찾는 루프의 초기값들을 잘 설정해줘야한다.

 

// i*j의 값이 check의 범위를 벗어난다.(check의 범위를 늘려주면 메모리 초과가 난다.)
for(int j = i; i*j <= N; j++)
	check[i*j] = true;
    
// i*i는 int의 범위를 벗어날 수 있으므로 i+i부터 탐색
for(int j = i*i; j <= N; j+=i)
	check[j] = true;

 

---

2. 코드

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int M = sc.nextInt();
        int N = sc.nextInt();

        boolean[] check = new boolean[1000000001];
        // 에라토스테네스의 체
        check[0] = check[1] = true;
        for(int i = 2; i <= N; i++){
            if(check[i] == false){
                if(i >= M)
                    System.out.println(i);
                for(int j = i+i; j <= N; j+=i)
                    check[j] = true;
            }
        }
       sc.close();
    }
}