素数频率大于或等于k的数


难度级别 易得奖学金
经常问 ol石 亚马逊 事实集 风筝 GreyOrange Pinterest Xome
排列 哈希 素数

问题陈述

问题“素数频率大于或等于k的数字”指出给您一个整数数组,大小为n,整数值k。 其中的所有数字都是质数。 问题陈述要求找出出现在数组中至少k次的质数和素数在数组中的质数。

使用案列

arr[] = {29, 11, 37, 53, 53, 53, 29, 53, 29, 53}, k = 2
29 and 53

说明:29和53分别出现3次和5次,这也满足了至少出现k次的条件。

查找素数频率大于或等于k的数字的算法

1. Declare a map and store all the numbers of the array in the map with their frequencies.
2. Traverse the map.
    1. Check if the frequency of each element is at least k or greater than k.
    2. Find if that frequency is a prime number or not.
    3. If the frequency is a prime number then print that key else go for other numbers.

说明

我们给出了一个整数数组和一个值k。 给出的所有数字也是主数字,我们已要求找出该数字在数组中是否出现至少k次以及任何质数次,然后打印该数字。 为了解决这个问题,我们将使用 哈希 方法。 我们将使用 地图位置。 我们的任务是找到数字的外观,这意味着我们必须找到每个元素的出现,以解决此问题,我们将使用Map。

我们将遍历数组并计数并将每个元素及其频率存储到地图中。 如果数字是地图中的新条目,则在地图中为其放置一个位置并将其频率标记为1。如果它已经存在,则只需获取其频率并将其频率增加1,然后再次将该频率与它的编号。 这样,我们可以计算每个数字的所有频率。 现在我们需要检查每个数字的频率,首先存在k次,并且出现的次数应该是质数。

对于这种情况,我们将遍历映射中的每个键,并获取其频率。 我们已经创建了一个函数来检查频率是否是质数。 对于质数,它不能为1,也不能被其本身以外的其他数整除。 如果它可以被任何数整除,则返回false。 如果它是可整除的,则打印该键表示该频率的编号,然后进一步输入另一个编号。

 

素数频率大于或等于k的数

 

代码

C ++代码查找素数频率大于或等于k的数字

#include<iostream>
#include<unordered_map>

using namespace std;

bool checkIfPrime(int n)
{
    if (n <= 1)
        return false;

    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return false;

    return true;
}
void numberWithPrimeFreq(int arr[], int k)
{
    unordered_map<int, int> MAP;

    for (int i = 0; i < 12; i++)
        MAP[arr[i]]++;

    for (auto x : MAP)
    {
        if (checkIfPrime(x.second) && x.second >= k)
            cout << x.first << endl;
    }
}
int main()
{
    int arr[] = { 29,11,37,53,53,53,29,53,29,53 };
    int k = 2;

    numberWithPrimeFreq(arr, k);
    return 0;
}
29
53

Java代码查找素数大于或等于k的数字

import java.util.HashMap;
import java.util.Map;

public class  Frequencies_PrimeNumber
{
  public static void numberWithPrimeFreq(int[] arr, int k)
  {
    Map<Integer, Integer> MAP = new HashMap<>();

    for (int i = 0; i < arr.length; i++)
    {
      int val = arr[i];

      int freq;
      if (MAP.containsKey(val))
      {
        freq = MAP.get(val);
        freq++;
      }
      else
        freq = 1;
      MAP.put(val, freq);
    }
    for (Map.Entry<Integer, Integer> entry :MAP.entrySet())
    {
      int TEMP = entry.getValue();
      if (checkIfPrime(TEMP) && TEMP >= k)
        System.out.println(entry.getKey());
    }
  }
  private static boolean checkIfPrime(int n)
  {
    if ((n > 2 && n % 2 == 0) || n == 1)
      return false;

    for (int i = 2 ; i <n;	i ++)
    {
      if (n % i == 0)
        return false;
    }
    return true;
  }
  public static void main(String[] args)
  {
    int[] arr = { 29,11,37,53,53,53,29,53,29,53 };
    int k = 2;

    numberWithPrimeFreq(arr, k);
  }
}
53
29

复杂度分析

时间复杂度

在这里,假设我们有n / k个元素,其频率为k,因此每次都会检查素数。 但是素数检查只需要O(n)时间。 这里n是频率。 因此,即使在最坏的情况下,整个算法也可以在线性时间内运行。 上) 哪里 “N”  是数组中元素的数量。

空间复杂度

由于存储输入所需要的空间, 上) 哪里 “N”  是数组中元素的数量。