백준 1124 c++ "언더프라임" -PlusUltraCode-

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

 

[필자 사고]

에스테라토스의 채를 이용하여 푸는 문제다.

다만 해당 채를 구한다음 언더프라임 수를 구할 때 무작정 모든 경우의 수를 생각해서 나누면 문제가 생긴다.

```

  for (int i = 2; i <= MAX; i++) {
      int n = i;
      for (int k = 2; k <= sqrt(n); k++) {
          while (n % k == 0) {
              resultCount[i]++;
              n /= k;
          }
      }
      if (n > 1) resultCount[i]++;
  }

```

여기서 안쪽 for문에서 정해진 n을 나눌수 있는 수들을 정할때 sqrt(n)을 통해 반복문 횟수를 줄여줘야지

시간 초과를 면할 수 있다. 

 

sqrt()할수 있는 이유는 자연수를 소인수 분해하는 수들은 반드시 sqrt()를 넘지 않는다는 법칙 때문이다.

100을 예로보자면 

100의 소인수 숫자들은 반드시 10보다 작거나 같다. 

100 = 2*5*2*5 

 

아래는 자세한 코드해설이다.

[코드 해설]

Input() 함수

• 사용자로부터 두 정수 A, B를 입력받는다.
• isPrime이라는 불리언 배열을 초기화하여 0부터 MAX까지의 범위에서 소수를 미리 판별한다.
• 에라토스테네스의 체 알고리즘을 사용해 isPrime[i]가 true일 때, 그 배수들을 모두 false로 바꿔 소수가 아님을 표시한다.
• 이를 통해 특정 수가 소수인지 빠르게 판단할 수 있는 사전 정보가 준비된다.

---

Game_Start() 함수

1. resultCount 배열을 초기화하여 각 수가 갖는 **소인수의 총 개수(중복 포함)**를 저장한다.
   • 예를 들어 12는 2x2x3 이므로 개수는 3이다.
2. 각 정수 i에 대해 다음을 수행한다.
   • n = i라고 두고, 2부터 sqrt(n)까지의 수로 나누어떨어질 때마다 소인수 개수를 세고 n을 나눈다.
   • 이 과정을 반복하면 중복된 소인수도 포함해 정확히 몇 번 나눠졌는지 알 수 있다.
   • 소인수 분해가 끝난 후 n이 1보다 크면, 이는 마지막에 남은 소수이므로 개수를 1 더한다.
3. A부터 B까지의 모든 수를 탐색하며, 해당 수의 소인수 개수가 소수인지 확인한다.
   • 이때 resultCount[i]가 소수이면 언더프라임으로 간주하여 result를 증가시킨다.
4. 최종적으로 언더프라임의 개수를 출력한다.

---

main() 함수

• 위의 두 함수인 Input()과 Game_Start()를 순차적으로 호출하여 프로그램을 실행시킨다.
• 입력 → 소수 및 소인수 분석 → 언더프라임 개수 출력 흐름을 담당한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#define MAX 100000
using namespace std;

int A, B;
vector<bool> isPrime;
vector<int> resultCount;

void Input() {
    cin >> A >> B;
    isPrime.resize(MAX + 1, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 2; i<=sqrt(MAX); i++) {
        if (!isPrime[i]) continue;
        for (int k = i * i; k <= MAX; k += i) {
            isPrime[k] = false;
        }
    }
}

void Game_Start() {
    resultCount.resize(MAX + 1, 0);

    for (int i = 2; i <= MAX; i++) {
        int n = i;
        for (int k = 2; k <= sqrt(n); k++) {
            while (n % k == 0) {
                resultCount[i]++;
                n /= k;
            }
        }
        if (n > 1) resultCount[i]++;
    }

    int result = 0;
    for (int i = A; i <= B; i++) {
        if (isPrime[resultCount[i]]) result++;
    }

    cout << result;
}

int main(void) {
    Input();
    Game_Start();
    return 0;
}