Given an array of integers A of size N .
Value of a subset of array A is defined as product of all prime numbers in that subset.
If subset does not have any prime number in it, value of such a subset is 1.
If subset have only one prime number in it, value of such a subset is the prime number itself.
Calculate and return Sum of values of all possible subsets of array A % (10^9 + 7).
Constraints
1 <= N <= 10^5
1 <= A[i] < 2^31
max(A[1], A[2] ,..., A[n]) - min(A[1], A[2] ,..., A[n]) <=10^6
I’m stuck on this ques for a long time now, please help
Link to the original problem ?
Find all primes in array by segmented sieve. When picking a subset of primes, the answer is the product of all primes multiplied with 2 ^ nonPrime. nonPrime is fixed so the task is just finding sum of product of all subset of primes. DP for this.
I’ll give you an easy solution 
For any given set, say :- {a,b,c,d}
The sum of product of all the subsets is given by :–> (a+1).(b+1).(c+1).(d+1)
Now, in your array, replace all non-prime numbers by ‘1’…
If set :- (81,7),
Change it to :—> (1,7).
Now the formula:—> (1+1)*(7+1)=16
Well I did forget that exist. I did too much DP.