[백준/JAVA] 1929번: 소수 구하기

🔺 문제

1929번: 소수 구하기

 

🔺 코드

- 풀이1) int 배열 활용

import java.util.*;
import java.io.*;
 
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());
        int[] A = new int[N + 1];
        
        // 각 인덱스 값으로 초기화
        for(int i = 2 ; i <= N ; i++) {
            A[i] = i;
        }
        
        for(int i = 2 ; i <= Math.sqrt(N) ; i++) {
            if(A[i] == 0)
                continue;
            
            // 배수 지우기
            for(int j = i + i ; j <= N ; j += i) {
                A[j] = 0;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = M ; i <= N ; i++) {
            if(A[i] != 0) {
                sb.append(A[i]).append("\n");
            } 
        }
        System.out.println(sb);
    }
}

 

 

 

- 풀이2) boolean 배열 활용

import java.util.*;
import java.io.*;
 
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());
        boolean[] isPrime = new boolean[N + 1];
        Arrays.fill(isPrime, true);
        
        isPrime[0] = isPrime[1] = false;
        
        // 배수 지우기
        for(int i = 2 ; i <= Math.sqrt(N) ; i++) {
            // 이미 체크된 배열이면, 다음 반복문으로 skip
            if(!isPrime[i])
                continue;    
            for(int j = i * i ; j <= N ; j += i)
                isPrime[j] = false;
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = M ; i<= N ; i++) {
            if(isPrime[i]) {
                sb.append(i + "\n");
            } 
        }
        System.out.println(sb);
    }
}

 

✅ 해결 아이디어
✔ 소수 찾기 - 에라토스테네스의 체

 

💥 유의사항

⇨ 배수 지우는 부분 - 2번째 for문의 증감식 부분 j += i

⇨ i * i 미만의 변수는 이미 지워졌으므로 신경 안 씀.

 

---

🔺 다른 풀이들

백준 1929번 자바 문제 답/해설(소수 구하기 문제)

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

---

💬 느낀 점

오랜만에 보는 에라토스테네스의 체 반갑

 

1회독	2회독	3회독	4회독	5회독
V	6/12	6/20

 

(+6/12 2회독)

으아 오랜만에 혼자서 짜려니 또 까먹는다

이 망각의 곡선아,,,,ㅠ

import java.util.*;
import java.io.*;
 
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()," ");
        StringBuilder sb = new StringBuilder();
        
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for(int i = 2 ; i <= n ; i++) {
            if(isPrime[i]) {
                for(int j = i + i ; j <= n ; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        for(int i = m ; i <= n ; i++) {
            if(isPrime[i]) sb.append(i).append("\n");
        }
        System.out.println(sb);
    }
}

 

(+6/20 3회독)

boolean 배열로 소수 판별 배열을 만들었다.

import java.util.*;
import java.io.*;
 
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(), " ");
        StringBuilder sb = new StringBuilder();
        
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        
        boolean[] A = new boolean[N + 1];
        Arrays.fill(A, true);
        A[0] = A[1] = false;
        
        for(int i = 2 ; i <= (int)Math.sqrt(N) ; i++) {
            for(int j = i * i ; j <= N ; j += i) {
                A[j] = false;
            }
        }
        
        for(int i = M ; i <= N ; i++) {
            if(A[i]) {
                sb.append(i).append("\n");
            }
        }
        System.out.println(sb);
    }
}

---

(참고)

✔ 에라토스테네스의 체 (boolean ver.)

[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java)

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