• API
• FAQ
• Tools
• Archive
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 = prime = 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);
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.

Top