180603.md

수학1-2(소수, 소인수분해, 팩토리얼)

관련 문제들

• https://www.acmicpc.net/problem/2089
• https://www.acmicpc.net/problem/11576
• https://www.acmicpc.net/problem/1978
• https://www.acmicpc.net/problem/1929
• https://www.acmicpc.net/problem/6588
• https://www.acmicpc.net/problem/11653
• https://www.acmicpc.net/problem/10872
• https://www.acmicpc.net/problem/1676
• https://www.acmicpc.net/problem/2004

[issue]에 대한 정리

[#issue1] 1~N 까지의 수에서 모든 소수를 구하는 방법 '에라토스테네스의 체'의 개념

* 어떤 수 C에 대해 소수인지 아닌지 판단하는 데 걸리는 시간: O(루트 C)
    * 2 ~ (루트 C)까지만 확인하면 되기 때문
* 그렇다면 1 ~ 1,000,000까지의 모든 소수를 구하는 데 걸리는 시간?
    * 총 N개의 수 * 각각 소수인지 판단하는 시간복잡도
    * = N * O(루트N) = O(N루트N)
    * 즉, 1,000,000 * 1,000 = 10억 = 10sec
* '에라토스테네스의 체'의 개념
    1. 2부터 N까지의 모든 수를 적는다.
    2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
    3. 그 수를 지우고 소수로 저장한다.
    4. 그 수의 배수를 지운다.
* 예를 들어, 1~100 까지의 수에서 모든 소수를 구해보자
    * 2, 3, 5, 7의 순서로 위의 방법을 적용하면 
    * 11부터는 11*11 = 121(100초과)이기 때문에 더 이상 수행할 필요가 없다.

// '에라토스테네스의 체'를 이용한 start ~ end 범위의 수에서의 소수 구하기
Scanner s = new Scanner(System.in);
int start = s.nextInt();
int end = s.nextInt();

ArrayList<Integer> primeList = new ArrayList<>(); 
boolean[] checkPrime = new boolean[n + 1]; // true : 지워짐, false : 지워지지 않음

for (int i = 2; i <= end; i++) {
    // 지워지지 않은 수는 소수
    if (!checkPrime[i]) {
        primeList.add(i); // 2~end 까지의 소수 저장
        
        // i가 1,000,000 인 경우 i*i는 범위를 넘어가므로 j=i*i -> j=i*2
        // for (int j = i * i; j <= n; j += i){
        for (int j = i * 2; j <= end; j += i) { 
            checkPrime[j] = true; // 지워지지 않은 수의 배수들을 지운다
        }
    }
}

[#issue2] 소인수분해의 개념과 간단한 풀이법

* 소인수분해: 정수 N을 소수의 곱으로 분해하는 것
* 간단한 풀이법 
    * 소수를 구할 필요 없이
    * 2~루트num 까지의 수를 순서대로 반복해서
    * N를 나눌 수 없을 때까지 계속해서 나눈다.

Reference

🏠 Go Home