fork download
copy 
  1. //----------//
  2. // FairoozR //
  3. //----------//
  4.  
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7.  
  8. #define ll long long
  9. #define fast_in_out  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  10. #define ln "\n"
  11.  
  12. const double EPS = (double) 1e-9;
  13. const double pi = acos(-1);
  14. const int mod = 1000000007;
  15. const int N = (int) 1e5;
  16. const int M = (int) 1e2;
  17. int arr[M + 1];
  18. bool isPrime[N + 1];
  19. vector <int> primes;
  20.  
  21. void sieve()
  22. {
  23.     for(int i = 0; i <= N; i++)
  24.     {
  25.         isPrime[i] = true;
  26.     }
  27.     isPrime[0] = isPrime[1] = false;
  28.     for(int i = 0; i * i <= N; i++)
  29.     {
  30.         if(isPrime[i])
  31.         {
  32.             for(int j = i * i; j <= N; j += i)
  33.             {
  34.                 isPrime[j] = false;
  35.             }
  36.         }
  37.     }
  38.     for(int i = 0; i <= N; i++)
  39.     {
  40.         if(isPrime[i])
  41.         {
  42.             primes.push_back(i);
  43.         }
  44.     }
  45. }
  46.  
  47. int prime_count(int n)
  48. {
  49.     int cnt = 0, s = primes.size();
  50.     for(int i = 0; i < s; i++)
  51.     {
  52.         int  p = primes[i];
  53.         if((ll) p * p > n)
  54.         {
  55.             break;
  56.         }
  57.         if(n % p == 0)
  58.         {
  59.             cnt++;
  60.             while(n % p == 0)
  61.             {
  62.                 n /= p;
  63.             }
  64.         }
  65.     }
  66.     if(n > 1)
  67.     {
  68.         cnt++;
  69.     }
  70.     return cnt;
  71. }
  72.  
  73.  
  74. int find_largest_subset(int n, int k)
  75. {
  76.     int mx = 0;
  77.     for(int i = 0; i < n; i++)
  78.     {
  79.         int cnt = 0;
  80.         for(int j = 0; j < n; j++)
  81.         {
  82.             int temp = arr[i] - arr[j] ;
  83.             if(temp >= 0 && temp <= k)
  84.             {
  85.                 cnt++;
  86.             }
  87.         }
  88.         mx = max(mx, cnt);
  89.     }
  90.     return mx;
  91. }
  92.  
  93.  
  94. int main()
  95. {
  96.     fast_in_out;
  97.     sieve();
  98.     int test;
  99.     cin >> test;
  100.     for(int t = 1; t <= test; t++)
  101.     {
  102.         cout << "Case " << t << ":" << ln;
  103.         int n, k;
  104.         cin >> n >> k;
  105.         for(int i = 0; i < n; i++)
  106.         {
  107.             int x;
  108.             cin >> x;
  109.             arr[i] = prime_count(x);
  110.         }
  111.         for(int i = 1; i <= k; i++)
  112.         {
  113.             cout << find_largest_subset(n, i) << ln;
  114.         }
  115.     }
  116.     return 0;
  117. }
  118.  
  119.  
  120.  
Success #stdin #stdout 0.01s 5500KB
comments (?)
stdin
copy 
2
10 2
2310
4
6
3
35
90
45
55
210
21
2 3
420
4
stdout
copy 
Case 1:
7
8
Case 2:
1
1
2
https://ideone.com/ZYZ7hH
language:
C++ (gcc 8.3)
created:
326 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!