检查最小数字的第一位和最后一位是否构成素数-yiteyi-C++库

给定一个仅包含0到9的数字的数组arr[]，任务是从给定的数字中形成可能的最小数字，然后检查由此创建的数字的第一位和最后一位是否可以重新排列以形成素数。 例如：

null

输入： arr[]={2,6,4,9} 输出： 最低人数：2469 素数组合：29 第一位和最后一位数字分别为2和9。组合为29和92。只有29岁是最好的。 输入： arr[]={2,6,4,3,1,7} 输出： 最低人数：123467 素数组合：17 71 第一位和最后一位数字分别为1和7。组合是17和71，两者都是素数

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法：

创建一个大小为10的散列，将给定数组中的数字出现的次数存储到散列表中。
从数字0开始，按降序打印数字的出现次数。类似于通过重新排列给定数字的数字而得到的最小数字 .
对于素数检查，检查使用第一位和最后一位数字形成的数字是否为素数。反过来也一样。

以下是上述方法的实施情况：

C++

                         // C++ implementation of above approach                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to check prime                       
                         int                                     isPrime(                                     int                                     n)                       
                         {                       
                                                 int                                     i, c = 0;                       
                                                 for                                     (i = 1; i < n / 2; i++) {                       
                                                 if                                     (n % i == 0)                       
                                                 c++;                       
                                                 }                       
                                                 if                                     (c == 1)                       
                                                 return                                     1;                       
                                                 else                       
                                                 return                                     0;                       
                         }                       
           
                         // Function to generate smallest possible                       
                         // number with given digits                       
                         void                                     findMinNum(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // Declare a hash array of size 10                       
                                                 // and initialize all the elements to zero                       
                                                 int                                     first = 0, last = 0, num, rev, i;                       
                                                 int                                     hash[10] = { 0 };                       
           
                                                 // store the number of occurrences of the digits                       
                                                 // in the given array into the hash table                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 hash[arr[i]]++;                       
                                                 }                       
           
                                                 // Traverse the hash in ascending order                       
                                                 // to print the required number                       
                                                 cout <<                                     "Minimum number: "                                     ;                       
                                                 for                                     (                                     int                                     i = 0; i <= 9; i++) {                       
           
                                                 // Print the number of times a digits occurs                       
                                                 for                                     (                                     int                                     j = 0; j < hash[i]; j++)                       
                                                 cout << i;                       
                                                 }                       
           
                                                 cout << endl;                       
           
                                                 // extracting the first digit                       
                                                 for                                     (i = 0; i <= 9; i++) {                       
                                                 if                                     (hash[i] != 0) {                       
                                                 first = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                                 // extracting the last digit                       
                                                 for                                     (i = 9; i >= 0; i--) {                       
                                                 if                                     (hash[i] != 0) {                       
                                                 last = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 num = first * 10 + last;                       
                                                 rev = last * 10 + first;                       
           
                                                 // printing the prime combinations                       
                                                 cout <<                                     "Prime combinations: "                                     ;                       
                                                 if                                     (isPrime(num) && isPrime(rev))                       
                                                 cout << num <<                                     " "                                     << rev;                       
           
                                                 else                                     if                                     (isPrime(num))                       
                                                 cout << num;                       
           
                                                 else                                     if                                     (isPrime(rev))                       
                                                 cout << rev;                       
           
                                                 else                       
                                                 cout <<                                     "No combinations exist"                                     ;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 1, 2, 4, 7, 8};                       
                                                 findMinNum(arr, 5);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                                   
                         // Java implementation of above approach                       
           
                         import                                     java.io.*;                       
           
                         class                                     SmallPrime                       
                         {                       
           
                         // function to check prime                       
                         static                                     boolean                                     isPrime(                                     int                                     n)                       
                         {                       
                                                 int                                     i, c =                                     0                                     ;                       
                                                 for                                     (i =                                     1                                     ; i < n /                                     2                                     ; i++)                       
                                                 {                       
                                                 if                                     (n % i ==                                     0                                     )                       
                                                 c++;                       
                                                 }                       
                                                 if                                     (c ==                                     1                                     )                       
                                                 {                       
                                                 return                                     true                                     ;                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 return                                     false                                     ;                       
                                                 }                       
                         }                       
           
                         // Function to generate smallest possible                       
                         // number with given digits                       
                         static                                     void                                     findMinNum(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // Declare a hash array of size 10                       
                                                 // and initialize all the elements to zero                       
                                                 int                                     first =                                     0                                     , last =                                     0                                     , num, rev, i;                       
                                                 int                                     hash[] =                                     new                                     int                                     [                                     10                                     ];                       
           
                                                 // store the number of occurrences of the digits                       
                                                 // in the given array into the hash table                       
                                                 for                                     ( i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 hash[arr[i]]++;                       
                                                 }                       
           
                                                 // Traverse the hash in ascending order                       
                                                 // to print the required number                       
                                                 System.out.print(                                     "Minimum number: "                                     );                       
                                                 for                                     ( i =                                     0                                     ; i <=                                     9                                     ; i++)                       
                                                 {                       
           
                                                 // Print the number of times a digits occurs                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j < hash[i]; j++)                       
                                                 System.out.print(i);                       
                                   
                                                 }                       
                                                 System.out.println();                       
           
                                                 System.out.println();                       
                                                 // extracting the first digit                       
                                                 for                                     (i =                                     0                                     ; i <=                                     9                                     ; i++)                       
                                                 {                       
                                                 if                                     (hash[i] !=                                     0                                     )                       
                                                 {                       
                                                 first = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                                 // extracting the last digit                       
                                                 for                                     (i =                                     9                                     ; i >=                                     0                                     ; i--)                       
                                                 {                       
                                                 if                                     (hash[i] !=                                     0                                     )                       
                                                 {                       
                                                 last = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 num = first *                                     10                                     + last;                       
                                                 rev = last *                                     10                                     + first;                       
           
                                                 // printing the prime combinations                       
                                                 System.out.print(                                     "Prime combinations: "                                     );                       
                                                 if                                     (isPrime(num) && isPrime(rev))                       
                                                 {                       
                                                 System.out.println(num +                                     " "                                     + rev);                       
                                                 }                       
                                                 else                                     if                                     (isPrime(num))                       
                                                 {                       
                                                 System.out.println(num);                       
                                                 }                       
                                                 else                                     if                                     (isPrime(rev))                       
                                                 {                       
                                                 System.out.println(rev);                       
                                                 }                       
           
                                                 else                       
                                                 {                       
                                                 System.out.println(                                     "No combinations exist"                                     );                       
                                                 }                       
                         }                       
           
                         // Driver code                       
           
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 SmallPrime smallprime =                                     new                                     SmallPrime();                       
                                                 int                                     arr[] = {                                     1                                     ,                                     2                                     ,                                     4                                     ,                                     7                                     ,                                     8                                     };                       
                                                 smallprime.findMinNum(arr,                                     5                                     );                       
                                                 }                       
                         }                       
           
                         // This code has been contributed by inder_verma.                       

Python3

                         # Python3 implementation of above                       
                         # approach                       
                         import                                     math as mt                       
           
                         # function to check prime                       
                         def                                     isPrime(n):                       
                                                 i, c                                     =                                     0                                     ,                                     0                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     /                                     /                                     2                                     ):                       
                                                 if                                     (n                                     %                                     i                                     =                                     =                                     0                                     ):                       
                                                 c                                     +                                     =                                     1                       
                                   
                                                 if                                     (c                                     =                                     =                                     1                                     ):                       
                                                 return                                     1                       
                                                 else                                     :                       
                                                 return                                     0                       
           
                         # Function to generate smallest possible                       
                         # number with given digits                       
                         def                                     findMinNum(arr, n):                       
                                   
                                                 # Declare a Hash array of size 10                       
                                                 # and initialize all the elements to zero                       
                                                 first, last                                     =                                     0                                     ,                                     0                       
                                                 Hash                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (                                     10                                     )]                       
           
                                                 # store the number of occurrences of                       
                                                 # the digits in the given array into                       
                                                 # the Hash table                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 Hash                                     [arr[i]]                                     +                                     =                                     1                       
           
                                                 # Traverse the Hash in ascending order                       
                                                 # to print the required number                       
                                                 print                                     (                                     "Minimum number: "                                     , end                                     =                                     "")                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     ,                                     10                                     ):                       
                                   
                                                 # Print the number of times                       
                                                 # a digits occurs                       
                                                 for                                     j                                     in                                     range                                     (                                     Hash                                     [i]):                       
                                                 print                                     (i, end                                     =                                     "")                       
                                   
                                                 print                                     ()                       
                                   
                                                 # extracting the first digit                       
                                                 for                                     i                                     in                                     range                                     (                                     10                                     ):                       
                                                 if                                     (                                     Hash                                     [i] !                                     =                                     0                                     ):                       
                                                 first                                     =                                     i                       
                                                 break                       
                                   
                                                 # extracting the last digit                       
                                                 for                                     i                                     in                                     range                                     (                                     9                                     ,                                     -                                     1                                     ,                                     -                                     1                                     ):                       
                                                 if                                     (                                     Hash                                     [i] !                                     =                                     0                                     ):                       
                                                 last                                     =                                     i                       
                                                 break                       
                                   
                                                 num                                     =                                     first                                     *                                     10                                     +                                     last                       
                                                 rev                                     =                                     last                                     *                                     10                                     +                                     first                       
           
                                                 # printing the prime combinations                       
                                                 print                                     (                                     "Prime combinations: "                                     , end                                     =                                     "")                       
                                                 if                                     (isPrime(num)                                     and                                     isPrime(rev)):                       
                                                 print                                     (num,                                     " "                                     , rev)                       
                                                 elif                                     (isPrime(num)):                       
                                                 print                                     (num)                       
                                                 elif                                     (isPrime(rev)):                       
                                                 print                                     (rev)                       
                                                 else                                     :                       
                                                 print                                     (                                     "No combinations exist"                                     )                       
           
                         # Driver code                       
                         arr                                     =                                     [                                     1                                     ,                                     2                                     ,                                     4                                     ,                                     7                                     ,                                     8                                     ]                       
                         findMinNum(arr,                                     5                                     )                       
           
                         # This code is contributed by                       
                         # Mohit kumar 29                       

C#

                         // C# implementation of above approach                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                         // function to check prime                       
                         static                                     bool                                     isPrime(                                     int                                     n)                       
                         {                       
                                                 int                                     i, c = 0;                       
                                                 for                                     (i = 1; i < n / 2; i++)                       
                                                 {                       
                                                 if                                     (n % i == 0)                       
                                                 {                       
                                                 c++;                       
                                                 }                       
                                                 }                       
                                                 if                                     (c == 1)                       
                                                 {                       
                                                 return                                     true                                     ;                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 return                                     false                                     ;                       
                                                 }                       
                         }                       
           
                         // Function to generate smallest                       
                         // possible number with given digits                       
                         static                                     void                                     findMinNum(                                     int                                     [] arr,                                     int                                     n)                       
                         {                       
                                                 // Declare a hash array of                       
                                                 // size 10 and initialize                       
                                                 // all the elements to zero                       
                                                 int                                     first = 0, last = 0, num, rev, i;                       
                                                 int                                     [] hash =                                     new                                     int                                     [10];                       
           
                                                 // store the number of occurrences                       
                                                 // of the digits in the given array                       
                                                 // into the hash table                       
                                                 for                                     (i = 0; i < n; i++)                       
                                                 {                       
                                                 hash[arr[i]]++;                       
                                                 }                       
           
                                                 // Traverse the hash in ascending order                       
                                                 // to print the required number                       
                                                 Console.Write(                                     "Minimum number: "                                     );                       
                                                 for                                     (i = 0; i <= 9; i++)                       
                                                 {                       
           
                                                 // Print the number of times                       
                                                 // a digits occurs                       
                                                 for                                     (                                     int                                     j = 0; j < hash[i]; j++)                       
                                                 {                       
                                                 Console.Write(i);                       
                                                 }                       
           
                                                 }                       
                                                 Console.WriteLine();                       
           
                                                 Console.WriteLine();                       
                                   
                                                 // extracting the first digit                       
                                                 for                                     (i = 0; i <= 9; i++)                       
                                                 {                       
                                                 if                                     (hash[i] != 0)                       
                                                 {                       
                                                 first = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 // extracting the last digit                       
                                                 for                                     (i = 9; i >= 0; i--)                       
                                                 {                       
                                                 if                                     (hash[i] != 0)                       
                                                 {                       
                                                 last = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 num = first * 10 + last;                       
                                                 rev = last * 10 + first;                       
           
                                                 // printing the prime combinations                       
                                                 Console.Write(                                     "Prime combinations: "                                     );                       
                                                 if                                     (isPrime(num) && isPrime(rev))                       
                                                 {                       
                                                 Console.WriteLine(num +                                     " "                                     + rev);                       
                                                 }                       
                                                 else                                     if                                     (isPrime(num))                       
                                                 {                       
                                                 Console.WriteLine(num);                       
                                                 }                       
                                                 else                                     if                                     (isPrime(rev))                       
                                                 {                       
                                                 Console.WriteLine(rev);                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 Console.WriteLine(                                     "No combinations exist"                                     );                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 int                                     [] arr = {1, 2, 4, 7, 8};                       
                                                 findMinNum(arr, 5);                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by PrinciRaj1992                       

PHP

                         <?php                       
                         // PHP implementation of above approach                       
           
                         // function to check prime                       
                         function                                     isPrime(                                     $n                                     )                       
                         {                       
                                                 $c                                     = 0;                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     / 2;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $n                                     %                                     $i                                     == 0)                       
                                                 $c                                     ++;                       
                                                 }                       
                                                 if                                     (                                     $c                                     == 1)                       
                                                 return                                     1;                       
                                                 else                       
                                                 return                                     0;                       
                         }                       
           
                         // Function to generate smallest possible                       
                         // number with given digits                       
                         function                                     findMinNum(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 // Declare a hash array of size 10                       
                                                 // and initialize all the elements to zero                       
                                                 $first                                     = 0;                                     $last                                     = 0;                       
                                                 $num                                     ;                                     $rev                                     ;                                     $i                                     ;                       
                                                 $hash                                     =                                     array_fill                                     (0, 20, 0);                       
           
                                                 // store the number of occurrences of                       
                                                 // the digits in the given array into                       
                                                 // the hash table                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 $hash                                     [                                     $arr                                     [                                     $i                                     ]]++;                       
                                                 }                       
           
                                                 // Traverse the hash in ascending order                       
                                                 // to print the required number                       
                                                 echo                                     "Minimum number: "                                     ;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <= 9;                                     $i                                     ++)                       
                                                 {                       
           
                                                 // Print the number of times a                       
                                                 // digits occurs                       
                                                 for                                     (                                     $j                                     = 0;                                     $j                                     <                                     $hash                                     [                                     $i                                     ];                                     $j                                     ++)                       
                                                 echo                                     $i                                     ;                       
                                                 }                       
           
                                                 // extracting the first digit                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <= 9;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $hash                                     [                                     $i                                     ] != 0)                       
                                                 {                       
                                                 $first                                     =                                     $i                                     ;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 // extracting the last digit                       
                                                 for                                     (                                     $i                                     = 9;                                     $i                                     >= 0;                                     $i                                     --)                       
                                                 {                       
                                                 if                                     (                                     $hash                                     [                                     $i                                     ] != 0)                       
                                                 {                       
                                                 $last                                     =                                     $i                                     ;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 $num                                     =                                     $first                                     * 10 +                                     $last                                     ;                       
                                                 $rev                                     =                                     $last                                     * 10 +                                     $first                                     ;                       
           
                                                 // printing the prime combinations                       
                                                 echo                                     "Prime combinations: "                                     ;                       
                                                 if                                     (isPrime(                                     $num                                     ) && isPrime(                                     $rev                                     ))                       
                                                 echo                                     $num                                     .                                     " "                                     .                                     $rev                                     ;                       
           
                                                 else                                     if                                     (isPrime(                                     $num                                     ))                       
                                                 echo                                     $num                                     ;                       
           
                                                 else                                     if                                     (isPrime(                                     $rev                                     ))                       
                                                 echo                                     $rev                                     ;                       
           
                                                 else                       
                                                 echo                                     "No combinations exist"                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     (1, 2, 4, 7, 8);                       
                         findMinNum(                                     $arr                                     , 5);                       
           
                         // This code is contributed                       
                         // by Rajput-Ji                       
                         ?>                       

Javascript

                         <script>                       
                                                 // JavaScript implementation of above approach                       
                                                 // function to check prime                       
                                                 function                                     isPrime(n) {                       
                                                 var                                     i,                       
                                                 c = 0;                       
                                                 for                                     (i = 1; i < n / 2; i++) {                       
                                                 if                                     (n % i == 0) c++;                       
                                                 }                       
                                                 if                                     (c == 1)                                     return                                     1;                       
                                                 else                                     return                                     0;                       
                                                 }                       
           
                                                 // Function to generate smallest possible                       
                                                 // number with given digits                       
                                                 function                                     findMinNum(arr, n) {                       
                                                 // Declare a hash array of size 10                       
                                                 // and initialize all the elements to zero                       
                                                 var                                     first = 0,                       
                                                 last = 0,                       
                                                 num,                       
                                                 rev,                       
                                                 i;                       
                                                 var                                     hash =                                     new                                     Array(10).fill(0);                       
           
                                                 // store the number of occurrences of the digits                       
                                                 // in the given array into the hash table                       
                                                 for                                     (                                     var                                     i = 0; i < n; i++) {                       
                                                 hash[arr[i]]++;                       
                                                 }                       
           
                                                 // Traverse the hash in ascending order                       
                                                 // to print the required number                       
                                                 document.write(                                     "Minimum number: "                                     );                       
                                                 for                                     (                                     var                                     i = 0; i <= 9; i++) {                       
                                                 // Print the number of times a digits occurs                       
                                                 for                                     (                                     var                                     j = 0; j < hash[i]; j++) document.write(i);                       
                                                 }                       
           
                                                 document.write(                                     "<br>"                                     );                       
           
                                                 // extracting the first digit                       
                                                 for                                     (i = 0; i <= 9; i++) {                       
                                                 if                                     (hash[i] != 0) {                       
                                                 first = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                                 // extracting the last digit                       
                                                 for                                     (i = 9; i >= 0; i--) {                       
                                                 if                                     (hash[i] != 0) {                       
                                                 last = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 num = first * 10 + last;                       
                                                 rev = last * 10 + first;                       
           
                                                 // printing the prime combinations                       
                                                 document.write(                                     "Prime combinations: "                                     );                       
                                                 if                                     (isPrime(num) && isPrime(rev)) document.write(num +                                     " "                                     + rev);                       
                                                 else                                     if                                     (isPrime(num)) document.write(num);                       
                                                 else                                     if                                     (isPrime(rev)) document.write(rev);                       
                                                 else                                     document.write(                                     "No combinations exist"                                     );                       
                                                 }                       
           
                                                 // Driver code                       
                                                 var                                     arr = [1, 2, 4, 7, 8];                       
                                                 findMinNum(arr, 5);                       
                                                 </script>                       

输出：

Minimum number: 12478Prime combinations: No combinations exist

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

THE END

技术文章