fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll pair<long long, long long>
  4. #define fi first
  5. #define se second
  6. const long long inf = 1e18;
  7. const int maxn = 10 + 1e3;
  8. const int maxs = 5e6 + 10;
  9. const int ma = 5e6;
  10. long long a[maxn], b[maxn], luu[maxn], n;
  11. bool dd[maxs], f[maxs];
  12. int cso[5] = { 1, 3, 5, 7, 9 };
  13. void sangnt() {
  14.     for (int i = 2; i <= sqrt(ma); i++)
  15.         if (!dd[i])
  16.             for (int j = i * i; j <= ma; j += i) dd[j] = 1;
  17. }
  18. void sangnttd() {
  19.     long long d1 = 0, d2 = 0;
  20.     for (int i = 2; i <= 9; i++)
  21.         if (!dd[i])
  22.             d1++, d2++, a[d1] = i, b[d2] = i;
  23.     for (int t = 1; t <= 6; t++) {
  24.         long long d3 = 0;
  25.         for (int i = 1; i <= d1; i++)
  26.             for (int j = 0; j <= 4; j++) {
  27.                 long long so = a[i] * 10 + cso[j];
  28.                 if (so > ma)
  29.                     continue;
  30.                 if (!dd[so]) {
  31.                     d3++;
  32.                     luu[d3] = so;
  33.                 }
  34.             }
  35.         for (int i = d2 + 1; i <= d2 + d3; i++) b[i] = luu[i - d2];
  36.         d2 += d3;
  37.         d1 = d3;
  38.         for (int i = 1; i <= d1; i++) a[i] = luu[i];
  39.     }
  40.     f[0] = 1;
  41.     for (int i = 1; i <= d2; i++)
  42.         for (int j = ma; j >= b[i]; j--)
  43.             if (f[j - b[i]] != 0)
  44.                 f[j] = 1;
  45. }
  46. int main() {
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(NULL);
  49.     cout.tie(NULL);
  50.     //	freopen(".INP","r",stdin);
  51.     //	freopen(".OUT","w",stdout);
  52.     cin >> n;
  53.     sangnt();
  54.     sangnttd();
  55.     for (int i = 1; i <= n; i++)
  56.         if (f[i])
  57.             cout << i << " ";
  58. }
Success #stdin #stdout 0.26s 13280KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/UnAZvD
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!