fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define int long long
  5. #define db double
  6. #define pii pair<int,int>
  7. #define endl "\n"
  8.  
  9. using namespace std;
  10.  
  11. void solve()
  12. {
  13.     int n; cin >> n;
  14.     vector<int> color(n + 1, 0);
  15.     color[1] = 1;
  16.  
  17.     for (int i = 2; i <= n; i++)
  18.     {
  19.         if (color[i] == 0)
  20.             color[i] = 2;
  21.  
  22.         for (int j = 2 * i; j <= n; j += i)
  23.             if (color[j] < color[i] + 1)
  24.                 color[j] = color[i] + 1;
  25.     }
  26.  
  27.     cout << *max_element(color.begin(), color.end()) << endl;
  28.     for (int i = 1; i <= n; i++)
  29.         cout << color[i] << " ";
  30.     cout << endl;
  31. }
  32.  
  33. int32_t main()
  34. {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(nullptr);
  37.     cout.tie(nullptr);
  38.  
  39.     int T; cin >> T;
  40.     while (T--)
  41.         solve();
  42.  
  43.     return 0;
  44. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
2
3
4
stdout
copy 
2
1 2 2 
3
1 2 2 3
https://ideone.com/Lc2gel
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

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!