素数频率大于或等于k的数-yiteyi-C++库

给定一个数组，查找在数组中出现素数次且频率最小为k（频率>=k）的元素。

null

例如：

Input : int[] arr = { 11, 11, 11, 23, 11, 37, 51,                       37, 37, 51, 51, 51, 51 };        k = 2Output : 37, 51Explanation :11's count is 4, 23 count 1, 37 count 3, 51 count 5. 37 and 51 are two number that appear prime number oftime and frequencies greater than or equal to k.Input : int[] arr = { 11, 22, 33 } min Occurrence = 1Output : -1None of the count is prime number of times

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法： 1.创建一个映射，将数字作为键，将值作为其在输入数组中的引用。 2.迭代映射键并查找对应于其键的值，返回具有满足条件的最小值键的值为素数且>=min 作为输入。

C++

                         // C++ code to find number                       
                         // occurring prime number                       
                         // of times with frequency >= k                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Check if the number of                       
                         // occurrences are primes                       
                         // or not                       
                         bool                                     isPrime(                                     int                                     n)                       
                         {                       
                                                 // Corner case                       
                                                 if                                     (n <= 1)                                     return                                     false                                     ;                       
           
                                                 // Check from 2 to n-1                       
                                                 for                                     (                                     int                                     i = 2; i < n; i++)                       
                                                 if                                     (n % i == 0)                       
                                                 return                                     false                                     ;                       
           
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Function to find number                       
                         // with prime occurrences                       
                         void                                     primeOccurences(                                     int                                     arr[],                                     int                                     k)                       
                         {                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > map;                       
                                   
                                                 // Insert values and                       
                                                 // their frequencies                       
                                                 for                                     (                                     int                                     i = 0; i < 12; i++)                       
                                                 map[arr[i]]++;                       
           
                                                 // Traverse map and find                       
                                                 // elements with prime                       
                                                 // frequencies and frequency                       
                                                 // at least k                       
                                                 for                                     (                                     auto                                     x : map)                       
                                                 {                       
                                                 if                                     (isPrime(x.second) &&                       
                                                 x.second >= k)                       
                                                 cout << x.first << endl;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {11, 11, 11, 23,                       
                                                 11, 37, 37, 51,                       
                                                 51, 51, 51, 51};                       
                                                 int                                     k = 2;                       
           
                                                 primeOccurences(arr, k);                       
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by                       
                         // Manish Shaw(manishshaw1)                       

JAVA

                         // Java code to find number occurring prime                       
                         // number of times with frequency >= k                       
                         import                                     java.util.*;                       
           
                         public                                     class                                     PrimeNumber {                       
           
                                                 // Function to find number with prime occurrences                       
                                                 static                                     void                                     primeOccurences(                                     int                                     [] arr,                                     int                                     k)                       
                                                 {                       
                                                 Map<Integer, Integer> map =                                     new                                     HashMap<>();                       
           
                                                 // Insert values and their frequencies                       
                                                 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);                       
                                                 }                       
           
                                                 // Traverse map and find elements with                       
                                                 // prime frequencies and frequency at                       
                                                 // least k                       
                                                 for                                     (Map.Entry<Integer, Integer> entry :                       
                                                 map.entrySet()) {                       
                                                 int                                     value = entry.getValue();                       
                                                 if                                     (isPrime(value) && value >= k)                       
                                                 System.out.println(entry.getKey());                       
                                                 }                       
                                                 }                       
           
                                                 // Check if the number of occurrences                       
                                                 // are primes or not                       
                                                 private                                     static                                     boolean                                     isPrime(                                     int                                     n)                       
                                                 {                       
           
                                                 if                                     ((n >                                     2                                     && n %                                     2                                     ==                                     0                                     ) || n ==                                     1                                     )                       
                                                 return                                     false                                     ;                       
           
                                                 for                                     (                                     int                                     i =                                     3                                     ; i <= (                                     int                                     )Math.sqrt(n);                       
                                                 i +=                                     2                                     ) {                       
                                                 if                                     (n % i ==                                     0                                     )                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                                 return                                     true                                     ;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     [] arr = {                                     11                                     ,                                     11                                     ,                                     11                                     ,                                     23                                     ,                                     11                                     ,                                     37                                     ,                       
                                                 37                                     ,                                     51                                     ,                                     51                                     ,                                     51                                     ,                                     51                                     ,                                     51                                     };                       
                                                 int                                     k =                                     2                                     ;                       
           
                                                 primeOccurences(arr, k);                       
                                                 }                       
                         }                       

Python3

                         # Python3 code to find number                       
                         # occurring prime number of                       
                         # times with frequency >= k                       
           
                         # Function to find number                       
                         # with prime occurrences                       
                         def                                     primeOccurences(arr, k):                       
                                                 map                                     =                                     {}                       
           
                                                 # Insert values and their frequencies                       
                                                 for                                     val                                     in                                     arr:                       
                                                 freq                                     =                                     0                       
                                   
                                                 if                                     val                                     in                                     map                                     :                       
                                                 freq                                     =                                     map                                     [val]                       
                                                 freq                                     +                                     =                                     1                       
                                   
                                                 else                                     :                       
                                                 freq                                     =                                     1                       
                                                 map                                     [val]                                     =                                     freq                       
           
                                                 # Traverse map and find elements                       
                                                 # with prime frequencies and                       
                                                 # frequency at least k                       
                                                 for                                     entry                                     in                                     map                                     :                       
                                                 value                                     =                                     map                                     [entry]                       
                                   
                                                 if                                     isPrime(value)                                     and                                     value >                                     =                                     k:                       
                                                 print                                     (entry)                       
           
                         # Check if the number of occurrences                       
                         # are primes or not                       
                         def                                     isPrime(n):                       
           
                                                 if                                     (n >                                     2                                     and                                     not                                     n                                     %                                     2                                     )                                     or                                     n                                     =                                     =                                     1                                     :                       
                                                 return                                     False                       
           
                                                 for                                     i                                     in                                     range                                     (                                     3                                     ,                                     int                                     (n                                     *                                     *                                     0.5                                     +                                     1                                     ),                                     2                                     ):                       
                                                 if                                     not                                     n                                     %                                     i:                       
                                                 return                                     False                       
                                   
                                                 return                                     True                       
           
           
                         # Driver code                       
           
                         arr                                     =                                     [                                     11                                     ,                                     11                                     ,                                     11                                     ,                                     23                                     ,                                     11                                     ,                                     37                                     ,                       
                                                 37                                     ,                                     51                                     ,                                     51                                     ,                                     51                                     ,                                     51                                     ,                                     51                                     ]                       
                         k                                     =                                     2                       
           
                         primeOccurences(arr, k)                       
           
           
                         # This code is contributed by Ansu Kumari.                       

C#

                         // C# code to find number                       
                         // occurring prime number                       
                         // of times with frequency >= k                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG                       
                         {                       
           
                                                 // Function to find number                       
                                                 // with prime occurrences                       
                                                 static                                     void                                     primeOccurences(                                     int                                     [] arr,                       
                                                 int                                     k)                       
                                                 {                       
                                                 Dictionary<                                     int                                     ,                                     int                                     > map =                       
                                                 new                                     Dictionary<                                     int                                     ,                                     int                                     >();                       
                                   
                                                 // Insert values and                       
                                                 // their frequencies                       
                                                 for                                     (                                     int                                     i = 0; i < arr.Length; i++)                       
                                                 {                       
                                                 int                                     val = arr[i];                       
           
                                                 int                                     freq;                       
                                                 if                                     (map.ContainsKey(val))                       
                                                 {                       
                                                 freq = map[val];                       
                                                 freq++;                       
                                                 map.Remove(val);                       
                                                 }                       
                                                 else                       
                                                 freq = 1;                       
                                                 map.Add(val, freq);                       
                                                 }                       
           
                                                 // Traverse map and find elements                       
                                                 // with prime frequencies and                       
                                                 // frequency atleast k                       
                                                 foreach                                     (KeyValuePair<                                     int                                     ,                                     int                                     >                       
                                                 pair                                     in                                     map)                       
                                                 {                       
                                                 int                                     value = pair.Value;                       
                                                 if                                     (isPrime(value) &&                       
                                                 value >= k)                       
                                                 Console.WriteLine(pair.Key);                       
                                                 }                       
                                                 }                       
           
                                                 // Check if the number                       
                                                 // of occurrences                       
                                                 // are primes or not                       
                                                 static                                     bool                                     isPrime(                                     int                                     n)                       
                                                 {                       
                                                 if                                     ((n > 2 &&                       
                                                 n % 2 == 0) || n == 1)                       
                                                 return                                     false                                     ;                       
           
                                                 for                                     (                                     int                                     i = 3;                       
                                                 i <= (                                     int                                     )Math.Sqrt(n);                       
                                                 i += 2)                       
                                                 {                       
                                                 if                                     (n % i == 0)                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                                 return                                     true                                     ;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr =                                     new                                     int                                     []{11, 11, 11, 23, 11, 37,                       
                                                 37, 51, 51, 51, 51, 51};                       
                                                 int                                     k = 2;                       
           
                                                 primeOccurences(arr, k);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by                       
                         // Manish Shaw(manishshaw1)                       

Javascript

                         <script>                       
                         // Javascript code to find number                       
                         // occurring prime number                       
                         // of times with frequency >= k                       
           
                         // Check if the number of                       
                         // occurrences are primes                       
                         // or not                       
                         function                                     isPrime(n) {                       
                                                 // Corner case                       
                                                 if                                     (n <= 1)                                     return                                     false                                     ;                       
           
                                                 // Check from 2 to n-1                       
                                                 for                                     (let i = 2; i < n; i++)                       
                                                 if                                     (n % i == 0)                       
                                                 return                                     false                                     ;                       
           
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Function to find number                       
                         // with prime occurrences                       
                         function                                     primeOccurences(arr, k) {                       
                                                 let map =                                     new                                     Map();                       
           
                                                 // Insert values and                       
                                                 // their frequencies                       
                                                 for                                     (let i = 0; i < arr.length; i++) {                       
                                                 let val = arr[i];                       
           
                                                 let freq;                       
                                                 if                                     (map.has(val)) {                       
                                                 freq = map.get(val);                       
                                                 freq++;                       
                                                 }                       
                                                 else                       
                                                 freq = 1;                       
                                                 map.set(val, freq);                       
                                                 }                       
           
                                                 // Traverse map and find                       
                                                 // elements with prime                       
                                                 // frequencies and frequency                       
                                                 // at least k                       
                                                 for                                     (let x of map) {                       
                                                 if                                     (isPrime(x[1]) &&                       
                                                 x[1] >= k)                       
                                                 document.write(x[0] +                                     "<br>"                                     );                       
                                                 }                       
                         }                       
           
                         // Driver code                       
           
                         let arr = [11, 11, 11, 23,                       
                                                 11, 37, 37, 51,                       
                                                 51, 51, 51, 51];                       
                         let k = 2;                       
           
                         primeOccurences(arr, k);                       
           
                         // This code is contributed by                       
                         // gfgking                       
           
                         </script>                       

输出：

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章