[BAEKJOON] 2581번 소수 구하기 (소수 합, 최소 소수 값)

 

 

 

문제
: 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾기

 

■ 1. 문제 분석 

(1) 문제 설명

* 개념 : 소수는 1과 자신만을 약수로 가지는 수
* 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

 

 

(2) 입출력 예시

▶ 입력 예시

:첫째 줄에 M, 둘째 줄에 N이 주어진다

60
100

 

▶  출력 예시

: 첫째 줄에 소수의 합

: 둘째 줄에 찾은 소수 중 최솟값 출력

: 소수가 없을 경우는 첫째 줄에 -1 출력

60
100

 

---

 

 

■ 2. 문제  풀이

(1) 방법 1  " 2부터 N-1 까지의 자연수로 N을 나눠본다. "

 

이 방법은 너무 간단하지만 N 이하의 모든 수를 검사하므로 시간복잡도는 O(N) 이다.

for(int i = 2; i < num; i++) {
    if(num % i == 0) {
        System.out.println("소수 아님");
        return false;
    }

      System.out.println(num + "은 소수");
      return true; 
}

 

 

우리가 소수를 판별할 때는, 주어진 수 num이 소수인지 확인하기 위해 위의 방법처럼 num-1까지의 모든 수로 나누어보는 것이 일반적이다.   하지만 이 방법은 비효율적이므로 반복 범위를 최적화 해보도록 한다.  

 

 

(2) 방법 2  " 2부터  √N 이하의 자연수로 N을 나눠본다. "

 

《 N은 p*q 로 표현할 수 있는데, 여기서 p,q 는  √N 보다 작거나 이상 이다.》

 √N 은 N의 제곱근( ex. √25 = 5 ) 을 말한다.

 

예시를 들어보면,  N = 16이라 할때,  p,q 중 한 개는 4(= √16)  이하이고, 반대는 4(= √16) 이상이 된다. 

 

<p>  x  <q>

 1    ×  16 

 2    ×  8   

 4    ×  4   

 8    × 2    

 16  ×  1    

 

즉 제곱근 이하까지만 검사하면된다. 왜냐면 제곱근 이상의 수들은 이미 제곱근 이하의 수들로 나눠지는 걸로 확인 할 수 있기 때문이다.

p,q 중 한 쪽(제곱근 이하)에서 나눠졌다면, 다른 한쪽도 나눠진다는 것이기 때문에 다른 한 쪽(제곱근 이상)까지 반복분을 돌 필요가 없다.

=> 16이 2로 나눠진것을 알았다면, 당연히 8로도 나눠진다는 것이기 때문에!  √16의 제곱근인 2부터 4까지만 검사하면된다. 

 

 

코드로 작성해보자!

 

▶ 2-1. N의 제곱근 계산: N 의 제곱근 이하인 동안 반복하여 소수를 판별한다. 

- Math.sqrt(): JAVA에서 제공하는 제곱근 계산 함수.

- i가  number 의 제곱근 이하인 동안 반복한다. 직관적이지만, 제곱근을 매번 계산해야 하므로 약간의 오버헤드가 있을 수 있다.

 

// n이 소수가 아니라면, 반드시 n=a×b 형태로 나타낼 수 있고, 
// 이 때 a와 b 중 적어도 하나는 √N 이하의 값일 것이기 떄문에 √N 이하의 범위 구한다.

for (int i = 2; i <= Math.sqrt(num); i++) {
    if (num % i == 0) {
        System.out.print("소수가 아닙니다");
        return;
    }
}
System.out.print("소수입니다");

 

 

▶ 2-2. i의 제곱이 N  이하인 동안 반복하여 소수를 판별한다.

- i*i 가 num 의 제곱근일 때 까지만 반복문을 돈다.

for (int i = 2; i * i <= num; i++) {
    if (num % i == 0) {
        return false; // num이 i의 배수면 소수가 아니므로 false
    }
}
return true;

 

 

 

 

아래는 if(num % i == 0) 으로 소수를 판별하는게 아니라 에라토스테네스의 체를 이용하여 소수를 판별하는 알고리즘이다.

 

(3) 방법 3  " 에라토스테네스의 체 " (위키)

 

출처::위키백과

 

1. 2부터 N까지의 모든 수를 나열한다. (ex. 2~120)

2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)

2-1. 자기 자신을 제외한 2의 배수를 모두 지운다.

3. 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)

3-1. 자기 자신을 제외한 3의 배수를 모두 지운다.

4. 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)

4-1. 자기 자신을 제외한 5의 배수를 모두 지운다.

5. 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)

5-1. 자기 자신을 제외한 7의 배수를 모두 지운다.

6. 위의 과정을 반복하면 모든 소수가 남는다. (보라색)

 

 

 

 

 

 

 

에라토스테네스의 체를 JAVA 코드로 구현해보자. 

public class Eratos {
    public static void main(String[] args) {
        // ArrayList로 구현
        ArrayList<Boolean> primeList;

        // 사용자로부터의 콘솔 입력
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        // n <= 1 일 때 종료
        if(n <= 1) return;

        // n+1만큼 할당
        primeList = new ArrayList<Boolean>(n+1);
        // 0번째와 1번째를 소수 아님으로 처리
        primeList.add(false);
        primeList.add(false);
        // 2~ n까지 소수로 설정
        for(int i=2; i<=n; i++ ) {
            primeList.add(i, true);
        }

        // 2부터  ~ i*i <= n
        for(int i=2; (i*i)<=n; i++){
      
            if(primeList.get(i)){
              // i의 배수를 지운다.
              // j 의 초기값 i*i 이유: i 보다 작은 수들은 이전 단계에서 지워졌기 때문
              // ex. i=3 일때, 3*2는 i=2 에서 지워졌다.
                for(int j = i*i; j<=n; j+=i) { // j는 i씩 증가한다. (i=3이면 9, 12, 15..)
                    // 소수가 아닌 수 표시
                    primeList.set(j, false);
                }

            }
        }

// 출력
        StringBuffer sb = new StringBuffer();
        sb.append("{");
        for(int i=0; i<=n; i++){
            if(primeList.get(i) == true){
                sb.append(i);
                sb.append(",");
            }
        }
        sb.setCharAt(sb.length()-1, '}');

        System.out.println(sb.toString());

    }
}

public class Eratos {
    public static void main(String[] args) {
        // ArrayList로 구현
        ArrayList<Boolean> primeList;

        // 사용자로부터의 콘솔 입력
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        // n <= 1 일 때 종료
        if(n <= 1) return;

        // n+1만큼 할당
        primeList = new ArrayList<Boolean>(n+1);
        // 0번째와 1번째를 소수 아님으로 처리
        primeList.add(false);
        primeList.add(false);
        // 2~ n까지 소수로 설정
        for(int i=2; i<=n; i++ ) {
            primeList.add(i, true);
        }

        // 2부터  ~ i*i <= n
        for(int i=2; (i*i)<=n; i++){
      
            if(primeList.get(i)){
              // i의 배수를 지운다.
              // j 의 초기값 i*i 이유: i 보다 작은 수들은 이전 단계에서 지워졌기 때문
              // ex. i=3 일때, 3*2는 i=2 에서 지워졌다.
                for(int j = i*i; j<=n; j+=i) { // j는 i씩 증가한다. (i=3이면 9, 12, 15..)
                    // 소수가 아닌 수 표시
                    primeList.set(j, false);
                }

            }
        }

// 출력
        StringBuffer sb = new StringBuffer();
        sb.append("{");
        for(int i=0; i<=n; i++){
            if(primeList.get(i) == true){
                sb.append(i);
                sb.append(",");
            }
        }
        sb.setCharAt(sb.length()-1, '}');

        System.out.println(sb.toString());

    }
}

 

 

 

 

 

 

그러면 이제 반복범위 최적화방법과 에라토스테네스의 체 알고리즘을 사용하여 문제를 풀어보자!

 

public class Decimal_2581 {


   	public void solution1() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

         // M 이상 N 이하의 자연수 중 소수 찾기
        prime[] = findPrimesInRange(N);
        
  		// 소수의 합과 최솟값 계산
        int sum = 0;
        int min = Integer.MAX_VALUE;
        
        for(int i = M; i <= N; i++) {
            if(prime[i]) {	
                sum += i;
                if(i < min) {
                    min = i;
                }
            }
        }

        if(sum == 0) {	// 소수가 없다면
            System.out.println(-1);
        }
        else {
            System.out.println(sum);
            System.out.println(min);
        }
    }


    // 에라토스테네스 체 알고리즘
	public static boolean[] findPrimesInRange(int N) {
      // 초기에 모든 값은 true로 설정되며, 0과 1은 소수가 아니므로 false로 설정
     	boolean[] isPrime = new boolean[N + 1];
        Arrays.fill(isPrime, true);
        // 0과 1은 소수가 아님
    	isPrime[0] = isPrime[1] = false; 
        
        // 에라토스테네스의 체 알고리즘: 소수일때 true
        for(int i = 2; i <= Math.sqrt(N); i++) {
            if(prime[i]) {
                for(int j = i * i; j <= N; j += i) {
                	prime[j] = false;
            	}
            }
        }
        return isPrime;
    }
}

 

 

 

 

 

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

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

https://loosie.tistory.com/267

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