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 
  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;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74