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

문제📝

풀이💡

• 본 문제는 시간 제한으로 인해서 이중 for문으로만 해결해서는 안되고 에라토스테네스의 체를 사용해야 한다.
• 두 번째 숫자+1 크기의 boolean 배열을 만든다.
• 이중 for문 구조로 n의 배수를 true로 저장한다.
• true가 되지 않는 false는 소수가 된다.

코드💻

// 백준 Silver3 - 1929(소수 구하기)
// 문제링크: https://www.acmicpc.net/problem/1929

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        int num1 = sc.nextInt();   // 첫 번째 숫자 입력
        int num2 = sc.nextInt();   // 두 번째 숫자 입력
        boolean flag[] = new boolean[num2+1];
        flag[0] = flag[1] = true;  // 0과 1은 소수에서 제외
        
        // 에라토스테네스의 체 사용
        for(int i=2; i<=num2; i++) {
        	if(flag[i] == false) {
        		if(i>=num1)
        			System.out.println(i);
        		for(int j= i+i; j<=num2; j+=i)
        			flag[j] = true;
        	}
        }
    }
}

결과😎

느낀점👨‍💻

처음에 단순히 이중 for문으로만 계속해서 풀었는데 틀려서 검색을 통해서 에라토스테네스의 체를 사용해야만 문제를 해결할 수 있다 하여서 해결할 수 있었다.

Sinbmil의 알고리즘 문제 코드

-> https://github.com/Sinbmil/Algorithm-Study