[BOJ/백준] 약수, 배수와 소수_ 2581번

1. 문제 번호 2581번

 

 

 

 

 

---

 

 

 

 

 

2. 문제 풀이

 

 

한줄 평가

•   여전히 배열을 핸들링 하는 것은 까다롭다.
•   에라토스테네스의 이중 for문을 자유롭게 사용할 정도로 익숙해져야 한다.
    ( 꼭 1978번이랑 동일하게 갈 필요는 없다는 말이다. )
  
  • 처음 for문은 2부터 4의 배수부터 시작
  • 두번째 for문은 범위를 지정한다. 60~100까지  

 

 

 

문제를 먼저 정확히 파악

 

•  

 

 

 

나의 문제풀이 방식 및 순서

 

 * 나의 다양한 학습이 우선이기 때문에 다양한 방법을 생각 *

 

 

   또.. 2시간 짜리 헛고생을 지독하게 했다.

1. 두가지 수를 입력받는다. 60~100, 1~5
2. 배열 0~(N-M)까지 만든다. (0인덱스를 Value = 60이라고 가정)
3. Math.max(i * i, ((M + i - 1) / i) * i);  
4. isPrime[j - M] = false;  로 (60-60)가 0인덱스를 말하니깐 초기화 해준다.
   
   

 

 

 

 

 

 

---

3. 소스 인증

 

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
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()); //최대값

        primeNumberSieve(M, N);
    }
    public static void primeNumberSieve(int M, int N){
        // +1 을 해주는 이유는?? >>10 - 5 = 5 그러면 0 = 5 , 1 = 6 , 2 = 7 , 3 = 8 , 4 = 9 가 되면서 5 = 10 이 빠지게 된다
        int length = N - M + 1; // 10 - 5 = 5 인데  5~10까지는 6개의 숫자
        boolean [] isPrime = new boolean[length];
        Arrays.fill(isPrime, true); //소수를 모두 true 로 초기화
        
        // Setting non-prime for 0 and 1 explicitly
        if (M == 0) isPrime[0] = false; // 0은 소수가 아니다
        if (M == 1) isPrime[1 - M] = false; // 1은 소수가 아니다


		//i*i를 하는 이유는 이미 작은 소수에서 제곱근들은 다 삭제가 되어버리기 때문에
        //아래 2 문장이 가장 중요한 에라토스테네스의 채
        for(int i = 2; i * i < N; i++){ 
            int start = Math.max(i * i, ((M + i - 1) / i ) * i); 
            /*
                i = 2 일때 60보다 큰 숫자이면서 2의 배수는 60 부터
                i = 3 일때 60보다 큰 숫자이면서 3의 배수는 60 부터
                i = 7 일때 60보다 큰 숫자이면서 7의 배수는 63 부터
            */


            /* j = j + i 로 배수 시작 */
            for(int j = start; j <= N; j += i){ //소수 2부터 시작하는게 아니라 4부터 시작하게 만든다.
                isPrime[j - M] = false; //소수인 것들은 제거
            }
        }

        boolean isPrimeFound = false; //최소 소수를 찾기 위한 변수
        int minValue = Integer.MAX_VALUE; //최소 소수를 찾기 위한 변수, 0으로 두면 초기값을 유지하기 때문에 헷갈린다.
        
        int sumIsPrime = 0; //소수의 합

        for(int i = 0; i < length; i++ ){
            if(isPrime[i]){
                sumIsPrime += M + i;

                if(!isPrimeFound){ //최소 소수값을 찾기 위한 변수
                    isPrimeFound = true;
                    minValue = M + i;
                }
            }
        }

        if(isPrimeFound){
            System.out.println(sumIsPrime);
            System.out.println(minValue);
        } else {
            System.out.println(-1);
        }
        
    }
}

 

 

 

- 실패 소스코드 -

 

 

 

 

 

 

 

---

4.추가 개념

 

 

에라토스테네스의 체

• 개념 : 여러개의 소수를 한 꺼번에 판별하고자 할 때 사용

 

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        System.out.println(isPrimeNumber(57));
    }
    static boolean isPrimeNumber(int i){
        for(int j = 2; j < i; j++){
            if( i % j == 0 ) return false;
        }
        return true;
    }
}

 

소수를 판별하기 위해 제일 간단하게 생각할 수 있는 소수 판별 알고리즘이다. 다만 for문을 2부터 n-1까지 모두 순차적으로 돌아야 하기 때문에  O(N)의 시간 복잡도를 가져 비효율 적이다. (앞선 알고리즘을 전부다 이렇게 풀었기 때문에 이제는 동영상 강의를 들어야 할 것 같다고 생각이 듬)

사실은  \(O(N\tfrac{1}{2})\)로 해결할 수 있다.

 소수는 1,2,3,5,7,11 과 같이 "1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수' 이다.

 

모든 약수는 대칭형태이다.

예를 들어 A가 12 일 때 A = 2×6, 3×4, 4×3, 6×2인데 √12 = 3.46 정도가 되므로 2~3까지만 확인 해보면 된다.

아래와 같이 참조하여 \(O(N\tfrac{1}{2})\) 로 계산이 가능하다.

 

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        System.out.println(isPrimeNumber(97));
    }
    static boolean isPrimeNumber(int i){
        int end = (int)Math.sqrt(i);
        for(int j = 2; j <= end; j++){
            if( i % j == 0 ) return false;
        }
        return true;
    }
}

 

 

그렇다면 왜 에라토스테네스의 체를 배우는가?

이유는 여러 개의 소수를 한꺼번에 판별하고자 할때 사용하기 위해서 사용한다.

 

1.  시작부터 끝까지 배열을 만든다. (2~N까지)
2.  먼저 2의 배수를 지우며 본인은 Skip한다.
3.  3의 배수를 지우며 본인은 Skip한다.
4.  5의 배수를 지우며 보인은 Skip한다. (이미 4는 지웠기 때문에 건너뛴다.)

 

 

---

5. 참조 블로그

---

 

불편함을 느끼실 경우 연락 주시면 곧 바로 삭제하도록 하겠습니다.

 

---