[백준 골드 5] 1456 거의 소수

 

 

Git Hub :

https://github.com/kwon1232/CodingTest/tree/main/%EB%B0%B1%EC%A4%80/Gold/1456.%E2%80%85%EA%B1%B0%EC%9D%98%E2%80%85%EC%86%8C%EC%88%98

arr size 정하는 법

제곱의 범위를 생각하면 된다.
x^n 이므로,

제곱 벗기는 법은 루트 씌우기이다.
즉, 루트 x^n의 값 까지가 최대 탐색 수가 maxSize가 된다.

10^14 를 루트를 씌워준 뒤 +1의 값이 최대 배열의 수가 된다.

 

1. 이후 최대 배열의 수 까지 배열을 초기화해준다.

 

2. 초기화 이후에는 배수를 지워주는 반복문을 돌아준다.

 

3. 각각의 소수에 관해 소수를 N제곱한 값이 들어온

maxRange보다 커질 때까지 반복문을 실행해준다.

 

4. 이때 두 번째 반복문을 돌 때, 정답 체크의 조건은,

   1) 현재 소수가 B(RangeMax)보다 크지 않으면서, 

   2) 현재 소수가 A(RangeMin)보다 작아지면 정답이다.

 

따라서 임시 변수를 두어,

처음에는 도는 수를 기준으로 정답 체크를 기준으로 잡아준 뒤,

임시 변수 * 현재 수로 임시 변수를 갱신해준다.

 

유의해야할 것은

받아오는 수의 범위의 최대치가

int나 long으로는 대체하기에는 수의 범위가 크기 때문에

long long 값으로 받아야 한다.

#include <vector>
#include <iostream> 
#include <string>
#include <sstream>
#include <map>
#include <queue>
#include <deque>
#include <algorithm>
#include <stack>
#include <unordered_map>
#include <set>
#include <regex>
#include <tuple>
#include <cmath>
#include <cstddef> 


using namespace std;


long long arr[10000001];

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

    long long rangeMax, rangeMin;

    cin >> rangeMin >> rangeMax;

    int arrSize = sizeof(arr) / sizeof(arr[0]);


    for (int i = 2; i < arrSize; i++)
    {
        arr[i] = i;
    }

    for (int i = 2; i <= sqrt(arrSize); i++)
    {
        if (arr[i] == 0) continue;

        for (int j = i + i; j < arrSize; j = j + i)
        {
            arr[j] = 0;
        }
    }

    int count = 0;

    for (int i = 2; i < arrSize; i++)
    {
        if (arr[i] != 0)
        {
            long long temp = arr[i];

            while ((double)arr[i] <= (double)rangeMax / (double)temp)
            {
                if ((double)arr[i] >= (double)rangeMin / (double)temp)
                {
                    count++;
                }
                temp = temp * arr[i];
            }
        }
    }
    cout << count;
    
    return 0;
}