Powered by:NEFU AB-IN

Link

4520. 质数

• 题意

  给定一个正整数 X，请你在 X 后面添加若干位数字（至少添加一位数字；添加的数不能有前导0），使得结果为质数，在这个前提下所得的结果应尽量小。

• 思路

  打出素数表来，可以看到素数的结尾都是1、3、7、9，所以可以先打出素数表来，然后dfs判断即可

• 代码

  /* * @Author: NEFU AB-IN * @Date: 2022-08-04 10:11:30 * @FilePath: \Acwing\4520\4520.cpp * @LastEditTime: 2022-08-04 11:02:25 */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  const int INF = INT_MAX;
  const int N = 1e5 + 10;
  
  int prime[N], st[N], cnt;
  
  void solve()
  {
        
  
      int n;
      cin >> n;
  
      vector<int> v = {
        1, 3, 7, 9};
  
      function<int(int, int)> dfs = [&](int n, int p) {
        
          int y, x;
          for (int i = 0; i < 4; ++i)
          {
        
              y = 10 * (p - 1) + v[i]; // 尾数
              string t = to_string(n) + to_string(y);
              x = stol(t);
              if (!st[x])
                  return x;
          }
          return dfs(n, p + 1);
      };
  
      cout << dfs(n, 1) << '\n';
  
      return;
  }
  
  signed main()
  {
        
      IOS;
      int T;
      cin >> T;
  
      function<void()> init = [&] {
        
          for (int i = 2; i < N; ++i)
          {
        
              if (!st[i])
              {
        
                  prime[cnt++] = i;
              }
              for (int j = 0; prime[j] < N / i; ++j)
              {
        
                  st[prime[j] * i] = 1;
                  if (i % prime[j] == 0)
                      break;
              }
          }
      };
      init();
      while (T--)
          solve();
      return 0;
  }