[백준/JAVA] 1929 : 소수 구하기 ( 기본 수학 2 *소수 )

문제

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

입력

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

출력

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

 

예제입력	예제출력
3 16	3 5 7 11 13

 

⭕ 풀이

 

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int num = Integer.parseInt(st.nextToken());
        boolean[] isPrime = new boolean[num + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i <= num; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= num; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    
        StringBuilder sb = new StringBuilder();
        for (int i = start; i <= num; i++) {
            if (isPrime[i]) {
                sb.append(i).append("\n");
            }
        }
        System.out.println(sb.toString());
    }
}

 

for (int i = 2; i * i <= num; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= num; j += i) {
            isPrime[j] = false;
        }
    }
}

✅ 이전의 2581 : 소수찾기 문제에서 다른분의 풀이를 참고했었던적이 있는데 

이번문제에서 다시한번 이 방식을 참고해보았다.

i가 2일때 2를 제외한 2의배수를 모두  false로 만들고

i가 3이되고 3을 제외한 3의배수를 모두 false,,,,

4는 i가 2일때 지워졌으므로 패스하고

i가 5가되면 5의배수를 모두 false 로 만드는식으로 진행한다.

 

이역시 이전문제풀이에서 봤던개념인데

임의의 자연수가 있다면 해당 자연수를 num이라고 생각하고

x와 y를 곱한수가 num이라고 한다면 x와 y중 하나는 num의제곱근보다 작거나 같다는 얘기가된다.

따라서 i <= Math.sqrt(num) 이나 i * i <= num 이나 같은얘기가된다.

num이 81이라고 예를들면

i*i <= 81 인조건에 i는 9까지 반복하게된다.

1 * 81

3 * 27

9 * 9

27 * 3

81 * 1

이렇게 되므로 결국 i*i가 num보다 작거나 같을때 까지 

i를 제외한 i의 배수들은 모두 지워줄 수 있다는 말이다.

 

이렇게 지우고 아직 true인 값들은 9까지의 배수에 속하지않았다는것이므로 모두 소수가된다.

이렇게 boolean배열을 다시 반복하며 true인 인덱스들을 출력하면된다.

 

 

https://st-lab.tistory.com/81

소수의 이해를 돕기 좋은 포스팅이다!

 

 

 

-출처

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