SHARE
TWEET

prime subset product

Farid_Mia59 Nov 16th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // C++ implementation of the approach
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int power(int a, int b, int mod)
  6. {
  7.     int aa = 1;
  8.     while(b)
  9.     {
  10.         if(b & 1)
  11.         {
  12.             aa = aa * a;
  13.             aa %= mod;
  14.         }
  15.         a = a * a;
  16.         a %= mod;
  17.         b /= 2;
  18.     }
  19.     return aa;
  20. }
  21.  
  22. // Function to return the prime subset
  23. // product of the given array
  24. int product(int A[], int n)
  25. {
  26.  
  27.     // Create Sieve to check whether a
  28.     // number is prime or not
  29.     int N = 100010;
  30.     int mod = 1000000007;
  31.     vector<int> prime(N, 1);
  32.     prime[0] = prime[1] = 0;
  33.     int i = 2;
  34.     while (i * i < N)
  35.     {
  36.         if (prime[i])
  37.             for (int j = 2 * i;
  38.                     j <= N;j += i)
  39.                 prime[j] = 0;
  40.  
  41.         i += 1;
  42.     }
  43.  
  44.     // Length of the array
  45.     // Calculating 2^(n-1) % mod
  46.     int t = power(2, n - 1, mod - 1);
  47.  
  48.     int ans = 1;
  49.  
  50.     for (int j = 0; j < n; j++)
  51.     {
  52.         int i = A[j];
  53.  
  54.         // If element is prime then add
  55.         // its contribution in the result
  56.         if( prime[i])
  57.         {
  58.             ans *= power(i, t, mod);
  59.             ans %= mod;
  60.         }
  61.     }
  62.     return ans;
  63. }
  64.  
  65. // Driver code
  66. int main()
  67. {
  68.     int A[] = {3, 7};
  69.  
  70.     int n = sizeof(A) / sizeof(A[0]);
  71.     cin>>n;
  72.  
  73.     cout<<product(A, n);
  74. }
  75.  
  76. // This code is contributed by Mohit Kumar
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top