[C++] 백준 1456: 거의 소수

문제

[C++] 백준 1456: 거의 소수 GOLD 5
https://www.acmicpc.net/problem/1456

 

---

 

접근 방법

이 문제는 구간 [A, B] 안에 있는 거의 소수(= 어떤 소수 p에 대해 p², p³, p⁴ … 꼴인 수)의 개수를 세는 문제다.

모든 수를 일일이 나눠보면 범위가 너무 커서 불가능하므로, "소수의 거듭제곱을 만들어서 세는 방식”으로 접근한다.

 

1. √B 까지의 소수 먼저 구하기

• 어떤 거의 소수 p^k가 B 이하라면, 밑이 되는 소수 p는 반드시 p ≤ √B를 만족한다.
• 그래서 먼저 2 ~ √B 범위에 대해 에라토스테네스의 체로 소수를 구한다.

vector<LL> vect;
for (LL i = 0; i <= sqrt(b) + 1; i++)
    vect.push_back(i);

// 소수 구하기
for (LL i = 2; i < vect.size(); i++)
{
    if (vect[i] != 0)
    {
        for (LL j = i * 2; j < vect.size(); j += i)
        {
            if (vect[j] != 0)
                vect[j] = 0;
        }
    }
}

 

2. 각 소수 p에 대해 p², p³, p⁴… 생성해서 카운트

• i가 소수라면 i^2부터 시작해서 계속 i를 곱해 가며 i^3, i^4, …를 만든다.
• 이때 값이 B를 넘어가면 더 볼 필요 없다.
• 만들어진 값이 구간 [A, B] 안에 있으면 카운트한다.

LL cnt = 0;
for (LL i = 2; i < vect.size(); i++)
{
    if (vect[i] != 0)           // i가 소수인 경우
    {
        LL index = i * i;       // p^2부터 시작
        while (index <= b)
        {
            if (a <= index)     // 구간 [a, b] 안이면 카운트
                cnt++;

            if (index > b / i)  // 오버플로우 방지
                break;

            index *= i;         // p^3, p^4, ... 로 증가
        }
    }
}

 

이렇게 하면 소수 개수 × 거듭제곱 개수만큼만 탐색하므로,
브루트포스로 전 범위를 도는 것보다 훨씬 효율적으로 풀 수 있다.

 

구현 시 주의할 점

1. 소수 범위는 √B까지만

• 거의 소수의 형태가 p^k이기 때문에, p^2 ≤ B를 만족하는 가장 큰 p는 √B이다.
• 그래서 벡터 크기를 sqrt(b) + 1까지 잡는 게 핵심이다.

2. long long(LL) 사용

• i^k 형태로 계속 곱해 나갈 때 값이 금방 커지므로,
  int가 아니라 long long(여기서는 typedef long long LL)을 써야 안전하다.

3. 오버플로우 방지 조건

if (index > b / i)
    break;

 

• 다음에 index *= i를 수행할 때,
  이미 index > b / i라면 곱셈 후 index > b가 되어버린다.
• 이 조건으로 곱셈 전에 미리 컷을 걸어주면 오버플로우를 막을 수 있다.
• 이 조건을 추가하지 않으면 틀린다!!!!!!

 

 

---

 

코드

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

typedef long long LL;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	LL a = 0, b = 0;
	cin >> a >> b;

	vector<LL> vect;
	for (LL i = 0; i <= sqrt(b) + 1; i++)
		vect.push_back(i);

	// 소수 구하기
	for (LL i = 2; i < vect.size(); i++)
	{
		if (vect[i] != 0)
		{
			for (LL j = i * 2; j < vect.size(); j += i)
			{
				if (vect[j] != 0)
					vect[j] = 0;
			}
		}
	}

	LL cnt = 0;
	for (LL i = 2; i < vect.size(); i++)
	{
		if (vect[i] != 0)
		{
			LL index = i * i;
			while (index <= b)
			{
				if (a <= index)
					cnt++;

				if (index > b / i)  // 오버플로우 방지 
					break;

				index *= i;
			}
		}
	}
	cout << cnt;

	return 0;
}