[Silver III] 등차수열을 만들어요 - 32298

[문제 위치]

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

[문제 풀이]

소수 판별이 가능한지 그리고 이것을 고려하여 등차수열을 만들 수 있는지 묻는 문제이다.

다만, 이 문제는 범위가 매우 넓다는 점을 유의해야한다.

따라서, 모든 정수에 대하여 반복적으로 소수여부를 파악하는 것은 좋지 못하다.

 

따라서, 제곱을 이용한 일반적 소수 판별을 하되 그것의 배수들은 모두 소수가 아님을 이용하는 에라토스테네스의 체를 구현하여 사전에 소수인 수와 그렇지 않은 수들을 구분해야한다.

 

이후 소수가 아닌 수들을 기준으로 등차수열을 만들다가 소수가 포함되어야 하는 경우가 나올 때 실패를 반환하는 구조를 구현해주었다.

#include <iostream>
#include <vector>

using namespace std;

#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);

const int MAX_VAL = 2000000;
vector<bool> is_prime(MAX_VAL + 1, true);
vector<int> non_primes;

void sieve() {
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= MAX_VAL; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= MAX_VAL; j += i) {
                is_prime[j] = false;
            }
        }
    }
    for (int i = 1; i <= MAX_VAL; ++i) {
        if (!is_prime[i]) {
            non_primes.push_back(i);
        }
    }
}

int main() {
    FASTIO;
    
    sieve();
    
    int N, M;
    cin >> N >> M;
    
    for (int start : non_primes) {
        vector<int> sequence;
        bool valid = true;
        
        for (int i = 0; i < N; ++i) {
            int num = start + i * M;
            if (num > MAX_VAL || is_prime[num]) {
                valid = false;
                break;
            }
            sequence.push_back(num);
        }
        
        if (valid) {
            for (int i = 0; i < N; ++i) {
                cout << sequence[i] << " ";
            }
            cout << "\n";
            return 0;
        }
    }
    
    cout << "-1\n";
    return 0;
}