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).


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
1 Like

I’m stuck on this ques for a long time now, please help

1 Like

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.

1 Like

I’ll give you an easy solution :slight_smile:

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 :slight_smile:


Well I did forget that exist. I did too much DP.

1 Like