[백준/JAVA] 2581번: 소수

🔺 문제

2581번: 소수

 

🔺 코드

- 방법1

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));
		
        int m = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        int sum = 0;
        int min = 0;
		
        List<Integer> list = new ArrayList<>();
		
        for(int i = Math.min(m,n) ; i <= Math.max(m,n) ; i++) {
            boolean isPrime = true;

            if(i == 1) isPrime = false;

            for(int j = 2 ; j <= Math.sqrt(i) ; j++) {
                if(i % j == 0) {    // 소수가 아닌 경우
                    isPrime = false;
                    break;
                }
            }

            // 소수인 경우		    
            if(isPrime) {
                sum += i;
                list.add(i);		        
            }
        }

        if(list.size() != 0) {
            System.out.println(sum);
            System.out.println(list.get(0));		    
        }
        else {
            System.out.println(-1);
        }
    }
}

✅ 해결 아이디어
- 리스트를 생성해 여기에 소수를 넣고, 합까지 더한다.
- 최솟값은 리스트의 0번째 원소니까 list.get(0)해서 출력

에라토스테네스의 체 구현할 생각하다가 앗 그럼 최솟값이랑 합 계산은 어떻게 하지? 생각해보다가 일단 이렇게 해보았다...

시간 복잡도가 좋지는 않은...

 

 

- 방법2) 에라토스테네스의 체 사용

import java.util.*;
import java.io.*;
 
public class Main {
    public static final int MAX = 10001;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
        
        List<Integer> list = new ArrayList<>();
        int total = 0;
        int min = 0;
        
        // 에라토스테네스의 체
        boolean[] isPrime = new boolean[MAX];
        for(int i = 2 ; i <= N ; i++) {
            isPrime[i] = true;
        }
        
        for(int i = 2 ; i <= Math.sqrt(MAX) ; i++) {
            for(int j = i * i ; j < MAX ; j += i) {
                if(!isPrime[j]) continue;
                isPrime[j] = false;
            }
        }
        
        // 소수들의 합 구하기
        for(int i = M ; i <= N ; i++) {
            if(isPrime[i]) {
               total += i;
               list.add(i);
            }
        }
        
        if(list.size() == 0) {
            System.out.println("-1");
        }
        else {
            System.out.println(total);
            System.out.println(list.get(0));            
        }
    }
}

---

🔺 다른 풀이들

[백준] 2581번 : 소수 - JAVA [자바]

에라토스테네스의 체를 사용해서 풀어주셨다!👍👍