問題#
解法#
簡単な一つの篩法
一つの数が取れないなら、その倍数も必ず取れない
ある数が取れるかどうかを見るには、暴力的に解決すればよい
ただし、各数について事前に答えを処理する必要がある
詳細はコードを見てください
コード#
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
bool f[N];
int nxt[N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
for(int i = 1;i < N;i++)
{
if(f[i])
{
continue;
}
bool fl = 0;
int x = i;
while(x)
{
if(x % 10 == 7)
{
fl = 1;
break;
}
x /= 10;
}
if(fl)
{
for(int k = i;k < N;k += i)
{
f[k] = 1;
}
}
}
int ls = 0;
for(int i = 1;i < N;i++)
{
if(!f[i])
{
for(int k = ls + 1;k <= i;k++)
{
nxt[k] = i;
}
ls = i;
}
}
// for(int i = 1;i <= 100;i++)
// cout << nxt[i] << " ";
// cout << f[19] << endl;
int T, x;
cin >> T;
while( T -- )
{
cin >> x;
if(f[x]) cout << -1 << "\n";
else
cout << nxt[x + 1] << "\n";
}
return 0;
}