Level 2. k진수에서 소수 개수 구하기

Level 2. k진수에서 소수 개수 구하기

 

 

진수 변환, 소수 확인, 파싱이 복합적으로 구성된 문제였다.

 

에라토스테네스의 체 방법으로 소수를 찾았더니, 배열의 크기가 100만을 넘어가게 되어 메모리 초과가 발생했다.

 

매번 같은 계산을 하지 않기 위해 최댓값을 찾아 static으로 선언한 배열에 1번 계산해준 후 사용했다.

 

// 이 풀이는 메모리 초과가 발생한다.
#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>

using namespace std;

string to_base(int n, int num)
{
    deque<char> deq;
    const char numbers[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

    do
        deq.emplace_front(numbers[num % n]);
    while (num /= n);

    return string(deq.begin(), deq.end());
}

bool is_prime(long n)
{
    long last = n / 2;
    static vector<bool> v(n + 1, true);

    if (v[1] == false)
        return v[n];

    v[1] = false;

    for (long i = 2; i <= last; ++i)
        if (v[i])
            for (long j = 2 * i; j <= n; j += i)
                v[j] = false;

    return v[n];
}

int solution(int n, int k)
{
    int answer = 0;
    string s = to_base(k, n);
    
    replace(s.begin(), s.end(), '0', ' ');

    istringstream iss(s);
    vector<long> primes;
    long Max = -1;

    while (iss >> s)
    {
        long num = stol(s);

        Max = max(num, Max);
        primes.emplace_back(num);
    }

    is_prime(Max);

    for (long num : primes)
        answer += is_prime(num);

    return answer;
}

 

소수를 확인할 때 에라토스테네스의 체 방법을 사용하지 않고, 정석적인 방법을 사용해 해결했다.

• sqrt(n)을 넘어가는 수는 n의 약수가 될 수 없기 때문에, 여기까지만 확인해도 된다.

 

#include <iostream>
#include <deque>
#include <algorithm>
#include <sstream>
#include <string>
#include <cmath>

using namespace std;

string to_base(int n, int num)
{
    deque<char> deq;
    const char numbers[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

    do
        deq.emplace_front(numbers[num % n]);
    while (num /= n);

    return string(deq.begin(), deq.end());
}

bool is_prime(long n)
{
    float last = sqrtf(n);

    for (long i = 2; i <= last; ++i)
        if (n % i == 0)
            return false;

    return n != 1;
}

int solution(int n, int k)
{
    int answer = 0;
    string s = to_base(k, n);
    
    replace(s.begin(), s.end(), '0', ' ');

    istringstream iss(s);

    while (iss >> s)
        answer += is_prime(stol(s));

    return answer;
}