백준 2581번 소수/ 백준 단계별로 풀어보기 8단계 / 8. 기본 수학 2

백준 8단계 2번 문제 - 2581 소수

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

2581번: 소수

 

 

 

---

8. 기본 수학 2 (2) 백준 2581번 문제 소수

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

m부터 n까지 반복문을 만들고 그 안에서 소수를 구하고 그것끼리 더하게 만든다

 

 

 

---

오답

---

 

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 isPrime = true;
        int sum = 0;
        int min = 0;
        
        for(int i = m; m <= n; i++) {
            for(int j = 2; j <= Math.sqrt(i); j++) {
                if(i % j == 0) {
                    isPrime = false;
                    break;
                }
                if(isPrime && min > i) {min = i;}
                if(isPrime) {sum =+ i;}
            }
        }System.out.println(sum); System.out.println(min);
    }
}

 

이클립스는 오류가 나는지 아예 값이 안 뜨고 백준에서는 시간초과가 떴다

(이제 보니까 -1 나올 경우도 안 넣었다)

 

2를 제외하고 소수는 모두 홀수니까 i % 2 == 0이면 false로 바꾸게끔 해봤지만 그것도 시간초과

(근데 이것도 100까지의 소수라서 아닐 수도 있겠다)

 

 

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 isPrime = true;
        int sum = 0;
        int min = 0;
        
        if(m % 2 == 0) { //m이 짝수
            for(int i = m+1; i <= n; i=i+2) {
                for(int j = 2; j <= Math.sqrt(i); j++) {
                    if(i % j == 0) {
                        isPrime = false;
                        break;
                    }
                    if(isPrime && min > i) {min = i;}
                    if(isPrime) {sum =+ i;}
                }
        }
        }
        
        if(m % 2 != 0) { //m이 홀수
            for(int i = m; i <= n; i=i+2) {
                for(int j = 2; j <= Math.sqrt(i); j++) {
                    if(i % j == 0) {
                        isPrime = false;
                        break;
                    }
                    if(isPrime && min > i) {min = i;}
                    if(isPrime) {sum =+ i;}
                }
        }
        }
        System.out.println(sum); System.out.println(min);
    }
}

 

반복횟수를 줄이기 위해 첫 숫자가 홀수냐 아니냐를 나누고, 시작 숫자를 홀수로 설정한 뒤 +2를 하게 했다

이렇게 하니 시간초과는 사라지고 답이 틀렸다고만 나왔다

 

이클립스에서 돌려보니 드디어 답이 나왔는데 완전 엉뚱한 답이 나옴...~

 

 

 

---

정답 인정 코드

---

 

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

 

이 블로그를 참고했다

 

import java.util.Scanner;
 
public class Main {
 
    public static boolean prime[];
    
    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        
        int M = in.nextInt();
        int N = in.nextInt();
        
        prime = new boolean[N + 1];    // 배열 생성 / 0부터 시작하니 +1
        get_prime();
        
        
        // 소수 합 및 최솟값 
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for(int i = M; i <= N; i++) {
            if(prime[i] == false) {    // false = 소수 
                sum += i;
                if(min == Integer.MAX_VALUE) {    // 첫 소수가 최솟값임  
                    min = i;
                }
            }
        }
        
        if(sum == 0) {    // 합이 0 = 소수가 없다
            System.out.println(-1);
        }
        else {
            System.out.println(sum);
            System.out.println(min);
        }
        
    }
 
    
    // 에라토스테네스 체 알고리즘 
    public static void get_prime() {
        prime[0] = true; // 0은 소수가 아니다
        prime[1] = true; // 1은 소수가 아니다
        
        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            for(int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
        
    }
}

 

왜 boolean을 메인 메소드 위에 선언하는지 등 모르는 부분이 많아서 그냥 외우기로 했다..

구글링해서 이해할 수 있는 풀이가 몇 있긴 했는데 모두 시간초과가 나와서 이걸 외우는 수밖에 없을 것 같다

 

에라토스테네스의 체는 다른 소수문제에서도 유용하게 쓸 수 있을 듯하다

 

 

 

---