给定一个由 n 个元素组成的数组 arr[] ，任务是找出数组中具有素频率的元素的乘积。因为产品可以很大，所以打印产品的模 10 9 7 。注意说明 1 既不是素的也不是复合的。 示例:
输入: arr[] = {5，4，6，5，4，6} 输出: 120 所有元素出现 2 次这是一个素数 所以，5 * 4 * 6 = 120 输入: arr[] = {1，2，3，3，2，3，3} 输出: 6 只有 2 和 3 出现素数 i 次 所以，2 * 3 = 6
进场:
- 遍历数组，将所有元素的频率存储在图中。
- 构建厄拉多塞的筛，用于测试一个数在 o(1)时间内的素性。
- 使用上一步中计算的筛阵列计算具有主频的元素的乘积。
以下是上述方法的实现:
c
// c implementation of the approach
#include
using namespace std;
#define mod 1000000007
// function to create sieve to check primes
void sieveoferatosthenes(bool prime[], int p_size)
{
// false here indicates
// that it is not prime
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= p_size; p ) {
// if prime[p] is not changed,
// then it is a prime
if (prime[p]) {
// update all multiples of p,
// set them to non-prime
for (int i = p * 2; i <= p_size; i = p)
prime[i] = false;
}
}
}
// function to return the product of elements
// in an array having prime frequency
int productprimefreq(int arr[], int n)
{
bool prime[n 1];
memset(prime, true, sizeof(prime));
sieveoferatosthenes(prime, n 1);
int i, j;
// map is used to store
// element frequencies
unordered_map m;
for (i = 0; i < n; i )
m[arr[i]] ;
long product = 1;
// traverse the map using iterators
for (auto it = m.begin(); it != m.end(); it ) {
// count the number of elements
// having prime frequencies
if (prime[it->second]) {
product *= (it->first % mod);
product %= mod;
}
}
return (int)(product);
}
// driver code
int main()
{
int arr[] = { 5, 4, 6, 5, 4, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << productprimefreq(arr, n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java implementation of the approach
import java.util.*;
class gfg
{
static int mod = 1000000007;
// function to create sieve to check primes
static void sieveoferatosthenes(boolean prime[],
int p_size)
{
// false here indicates
// that it is not prime
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= p_size; p )
{
// if prime[p] is not changed,
// then it is a prime
if (prime[p])
{
// update all multiples of p,
// set them to non-prime
for (int i = p * 2;
i <= p_size; i = p)
prime[i] = false;
}
}
}
// function to return the product of elements
// in an array having prime frequency
static int productprimefreq(int arr[], int n)
{
boolean []prime = new boolean[n 1];
for (int i = 0; i < n; i )
prime[i] = true;
sieveoferatosthenes(prime, n 1);
int i, j;
// map is used to store
// element frequencies
hashmap mp = new hashmap();
for (i = 0 ; i < n; i )
{
if(mp.containskey(arr[i]))
{
mp.put(arr[i], mp.get(arr[i]) 1);
}
else
{
mp.put(arr[i], 1);
}
}
long product = 1;
// traverse the map using iterators
for (map.entry it : mp.entryset())
{
// count the number of elements
// having prime frequencies
if (prime[it.getvalue()])
{
product *= (it.getkey() % mod);
product %= mod;
}
}
return (int)(product);
}
// driver code
static public void main (string []arg)
{
int arr[] = { 5, 4, 6, 5, 4, 6 };
int n = arr.length;
system.out.println(productprimefreq(arr, n));
}
}
// this code is contributed by rajput-ji
python 3
# python3 implementation of the approach
mod = 1000000007
# function to create sieve to check primes
def sieveoferatosthenes(prime, p_size):
# false here indicates
# that it is not prime
prime[0] = false
prime[1] = false
for p in range(2, p_size):
# if prime[p] is not changed,
# then it is a prime
if (prime[p]):
# update all multiples of p,
# set them to non-prime
for i in range(2 * p, p_size, p):
prime[i] = false
# function to return the product of elements
# in an array having prime frequency
def productprimefreq(arr, n):
prime = [true for i in range(n 1)]
sieveoferatosthenes(prime, n 1)
i, j = 0, 0
# map is used to store
# element frequencies
m = dict()
for i in range(n):
m[arr[i]] = m.get(arr[i], 0) 1
product = 1
# traverse the map using iterators
for it in m:
# count the number of elements
# having prime frequencies
if (prime[m[it]]):
product *= it % mod
product %= mod
return product
# driver code
arr = [5, 4, 6, 5, 4, 6]
n = len(arr)
print(productprimefreq(arr, n))
# this code is contributed by mohit kumar
c
// c# implementation for above approach
using system;
using system.collections.generic;
class gfg
{
static int mod = 1000000007;
// function to create sieve to check primes
static void sieveoferatosthenes(bool []prime,
int p_size)
{
// false here indicates
// that it is not prime
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= p_size; p )
{
// if prime[p] is not changed,
// then it is a prime
if (prime[p])
{
// update all multiples of p,
// set them to non-prime
for (int i = p * 2;
i <= p_size; i = p)
prime[i] = false;
}
}
}
// function to return the product of elements
// in an array having prime frequency
static int productprimefreq(int []arr, int n)
{
bool []prime = new bool[n 1];
int i;
for (i = 0; i < n; i )
prime[i] = true;
sieveoferatosthenes(prime, n 1);
// map is used to store
// element frequencies
dictionary mp = new dictionary();
for (i = 0 ; i < n; i )
{
if(mp.containskey(arr[i]))
{
var val = mp[arr[i]];
mp.remove(arr[i]);
mp.add(arr[i], val 1);
}
else
{
mp.add(arr[i], 1);
}
}
long product = 1;
// traverse the map using iterators
foreach(keyvaluepair it in mp)
{
// count the number of elements
// having prime frequencies
if (prime[it.value])
{
product *= (it.key % mod);
product %= mod;
}
}
return (int)(product);
}
// driver code
static public void main (string []arg)
{
int []arr = { 5, 4, 6, 5, 4, 6 };
int n = arr.length;
console.writeline(productprimefreq(arr, n));
}
}
// this code is contributed by princi singh
java 描述语言
output:
120
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
