Count of subarrays whose products don’t have any repeating prime factor

Revision en1, by wish_me, 2017-09-19 10:23:20

Given an array of integers. Find the total number of subarrays whose product of all elements doesn’t contain repeating prime

factor in prime decomposition of resulting number.

Input: 2 3 9

Output: 3

Explanation:

Total sub-array are:-

{2}, {3}, {9}, {2, 3}, {3, 9}, {2, 3, 9}

Subarray which violets the property are:-

{9} -> {3 * 3}, Since 3 is a repeating prime

factor in prime decomposition of 9

{3, 9} -> {3 * 3 * 3}, 3 is a repeating prime

factor in prime decomposition of 27

{2, 3, 9} -> {2 * 3 * 3 * 3}, 3 is repeating

prime factor in prime decomposition 

         of 54

Hence total subarray remains which satisfies our

condition are 3.

Input: 2, 3, 5, 15, 7, 2 Output: 12

Tags array, sieve

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English wish_me 2017-09-19 10:23:20 855 Initial revision (published)