fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5. #include <deque>
  6. #include <cmath>
  7. #include <set>
  8. #include <unordered_map>
  9. #include <iomanip>
  10. #include <climits>
  11.  
  12. using namespace std;
  13.  
  14. #define all(v) ((v).begin()), ((v).end())
  15. #define sz(v) ((int)((v).size()))
  16. #define clr(v, d) memset(v, d, sizeof(v))
  17. #define rep(i, v) for (int i = 0; i < sz(v); ++i)
  18. #define lp(i, n) for (int i = 0; i < (int)(n); ++i)
  19. #define lpi(i, j, n) for (int i = (j); i < (int)(n); ++i)
  20. #define lpd(i, j, n) for (int i = (j); i >= (int)(n); --i)
  21. typedef long long ll;
  22.  
  23. void fast_io()
  24. {
  25.     ios_base::sync_with_stdio(false);
  26.     cin.tie(nullptr);
  27.     cout.tie(nullptr);
  28. #ifndef ONLINE_JUDGE
  29.     freopen("input.txt", "r", stdin);
  30.     freopen("output.txt", "w", stdout);
  31. #endif
  32. }
  33. void sieve(bool is_prime[], int n){
  34.     is_prime[0] = false, is_prime[1] = false;
  35.     lpi(i, 2, n+1){
  36.         is_prime[i] = true;
  37.     }
  38.     for (int i = 2; i*i <= n; i++){
  39.         if (is_prime[i]){
  40.             for (int j = i*i; j <= n; j+=i){
  41.                 is_prime[j] = false;
  42.             }
  43.         }
  44.     }
  45. }
  46.  
  47. int main()
  48. {
  49.     fast_io();
  50.     int t;
  51.     cin >> t;
  52.  
  53.     lpi(x, 1, t + 1)
  54.     {
  55.         int n, k;
  56.         cin >> n >> k;
  57.         int almost_primes = 0;
  58.  
  59.         bool is_prime[++n];
  60.         sieve(is_prime, n);
  61.  
  62.         int primes[k];
  63.         lp(i, k)
  64.         {
  65.             cin >> primes[i];
  66.         }
  67.  
  68.         lpi(i, 2, n)
  69.         {
  70.             if (is_prime[i]) continue;
  71.  
  72.             int counter = 0;
  73.             lp(j, k)
  74.             {
  75.                 if (i % primes[j])
  76.                 {
  77.                     counter++;
  78.                 }
  79.             }
  80.             if (counter == k)
  81.                 almost_primes++;
  82.         }
  83.         cout << "Case " << x << ": " << almost_primes << endl;
  84.     }
  85. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
2
7 3
2 3 5
49 3
2 3 5
stdout
copy 
Case 1: 0
Case 2: 1
https://ideone.com/nyvfTg
language:
C++ (gcc 8.3)
created:
6 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!