# Product of proper divisors of a number for Q queries

Given an integer **N, **the task is to find the product of proper divisors of the number modulo 10^{9 }+ 7 for **Q** queries.

**Examples:**

Attention reader! All those who say programming isn't for kids, just haven't met the right mentors yet. Join the ** Demo Class for First Step to Coding Course, **specifically **designed for students of class 8 to 12. **

The students will get to learn more about the world of programming in these **free classes** which will definitely help them in making a wise career choice in the future.

Input:Q = 4, arr[] = { 4, 6, 8, 16 };Output:2 6 8 64Explanation:

4 => 1, 2 = 1 * 2 = 2

6 => 1, 2, 3 = 1 * 2 * 3 = 6

8 => 1, 2, 4 = 1 * 2 * 4 = 8

16 => 1, 2, 4, 8 = 1 * 2 * 4 * 8 = 64

Input:arr[] = { 3, 6, 9, 12 }Output:1 6 3 144

**Approach:** The idea is to pre-compute and store product of proper divisors of elements with the help of Sieve of Eratosthenes.

Below is the implementation of the above approach:

## C++

`// C++ implementation of` `// the above approach` `#include <bits/stdc++.h>` `#define ll long long int` `#define mod 1000000007` `using` `namespace` `std;` `vector<ll> ans(100002, 1);` `// Function to precompute the product` `// of proper divisors of a number at` `// it's corresponding index` `void` `preCompute()` `{` ` ` `for` `(` `int` `i = 2; i <= 100000 / 2; i++) {` ` ` `for` `(` `int` `j = 2 * i; j <= 100000; j += i) {` ` ` `ans[j] = (ans[j] * i) % mod;` ` ` `}` ` ` `}` `}` `int` `productOfProperDivi(` `int` `num)` `{` ` ` `// Returning the pre-computed` ` ` `// values` ` ` `return` `ans[num];` `}` `// Driver code` `int` `main()` `{` ` ` `preCompute();` ` ` `int` `queries = 5;` ` ` `int` `a[queries] = { 4, 6, 8, 16, 36 };` ` ` `for` `(` `int` `i = 0; i < queries; i++) {` ` ` `cout << productOfProperDivi(a[i])` ` ` `<< ` `", "` `;` ` ` `}` ` ` `return` `0;` `}` |

## Java

`// Java implementation of` `// the above approach` `import` `java.util.*;` `class` `GFG` `{` ` ` `static` `final` `int` `mod = ` `1000000007` `;` ` ` `static` `long` `[] ans = ` `new` `long` `[` `100002` `];` ` ` `// Function to precompute the product` ` ` `// of proper divisors of a number at` ` ` `// it's corresponding index` ` ` `static` `void` `preCompute()` ` ` `{` ` ` `for` `(` `int` `i = ` `2` `; i <= ` `100000` `/ ` `2` `; i++)` ` ` `{` ` ` `for` `(` `int` `j = ` `2` `* i; j <= ` `100000` `; j += i)` ` ` `{` ` ` `ans[j] = (ans[j] * i) % mod;` ` ` `}` ` ` `}` ` ` `}` ` ` `static` `long` `productOfProperDivi(` `int` `num)` ` ` `{` ` ` `// Returning the pre-computed` ` ` `// values` ` ` `return` `ans[num];` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `Arrays.fill(ans, ` `1` `);` ` ` `preCompute();` ` ` `int` `queries = ` `5` `;` ` ` `int` `[] a = { ` `4` `, ` `6` `, ` `8` `, ` `16` `, ` `36` `};` ` ` `for` `(` `int` `i = ` `0` `; i < queries; i++)` ` ` `{` ` ` `System.out.print(productOfProperDivi(a[i]) + ` `", "` `);` ` ` `}` ` ` `}` `}` `// This code is contributed by Rajput-Ji` |

## Python3

`# Python3 implementation of` `# the above approach` `mod ` `=` `1000000007` `ans ` `=` `[` `1` `] ` `*` `(` `100002` `)` `# Function to precompute the product` `# of proper divisors of a number at` `# it's corresponding index` `def` `preCompute():` ` ` `for` `i ` `in` `range` `(` `2` `, ` `100000` `/` `/` `2` `+` `1` `):` ` ` `for` `j ` `in` `range` `(` `2` `*` `i, ` `100001` `, i):` ` ` `ans[j] ` `=` `(ans[j] ` `*` `i) ` `%` `mod` `def` `productOfProperDivi(num):` ` ` `# Returning the pre-computed` ` ` `# values` ` ` `return` `ans[num]` `# Driver code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `preCompute()` ` ` `queries ` `=` `5` ` ` `a ` `=` `[ ` `4` `, ` `6` `, ` `8` `, ` `16` `, ` `36` `]` ` ` `for` `i ` `in` `range` `(queries):` ` ` `print` `(productOfProperDivi(a[i]), end ` `=` `", "` `)` `# This code is contributed by chitranayal` |

## C#

`// C# implementation of` `// the above approach` `using` `System;` `class` `GFG{` ` ` `static` `readonly` `int` `mod = 1000000007;` `static` `long` `[] ans = ` `new` `long` `[100002];` `// Function to precompute the product` `// of proper divisors of a number at` `// it's corresponding index` `static` `void` `preCompute()` `{` ` ` `for` `(` `int` `i = 2; i <= 100000 / 2; i++)` ` ` `{` ` ` `for` `(` `int` `j = 2 * i; j <= 100000; j += i)` ` ` `{` ` ` `ans[j] = (ans[j] * i) % mod;` ` ` `}` ` ` `}` `}` `static` `long` `productOfProperDivi(` `int` `num)` `{` ` ` `// Returning the pre-computed` ` ` `// values` ` ` `return` `ans[num];` `}` `// Driver code` `public` `static` `void` `Main(String[] args)` `{` ` ` `for` `(` `int` `i = 0 ; i < 100002; i++)` ` ` `ans[i] = 1;` ` ` ` ` `preCompute();` ` ` `int` `queries = 5;` ` ` `int` `[] a = { 4, 6, 8, 16, 36 };` ` ` `for` `(` `int` `i = 0; i < queries; i++)` ` ` `{` ` ` `Console.Write(productOfProperDivi(a[i]) + ` `", "` `);` ` ` `}` `}` `}` `// This code is contributed by Princi Singh` |

## Javascript

`<script>` `// Javascript implementation of` `// the above approach` `mod = 1000000007` `ans = Array(100002).fill(1)` `// Function to precompute the product` `// of proper divisors of a number at` `// it's corresponding index` `function` `preCompute()` `{` ` ` `for` `(` `var` `i = 2; i <= 100000 / 2; i++) {` ` ` `for` `(` `var` `j = 2 * i; j <= 100000; j += i) {` ` ` `ans[j] = (ans[j] * i) % mod;` ` ` `}` ` ` `}` `}` `function` `productOfProperDivi(num)` `{` ` ` `// Returning the pre-computed` ` ` `// values` ` ` `return` `ans[num];` `}` `// Driver code` `preCompute();` `var` `queries = 5;` `var` `a = [ 4, 6, 8, 16, 36 ];` `for` `(` `var` `i = 0; i < queries; i++) {` ` ` `document.write( productOfProperDivi(a[i])` ` ` `+ ` `", "` `);` `}` `</script>` |

**Output:**

2, 6, 8, 64, 279936,