给定和最小差的共素数对-yiteyi-C++库

共素数对或互素数对是指GCD为1的数对。给定一个数，n表示一个共素数对（a，B）的和，使得a–B最小。

null

例如：

Input : 12 Output : 5 7Possible co-prime pairs are (5, 7), (1, 11)but difference between 5 and 7 is minimumInput : 13Output : 6 7Possible co-prime pairs are (6, 7), (5, 8),(4, 9), (3, 10), (2, 11) and (1, 12) but difference between 6 and 7  is minimum

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

A. 简单解决方案 迭代从1到n-1的所有数字。对于每个数字x，检查n–x和x是否为共素数。如果是，那么如果两者之间的差异小于目前为止的最小差异，则更新结果。一 有效解决方案 基于这样一个事实，即差值最小的数字应该接近n/2。我们从n/2循环到1。检查每个可能的对，当找到第一个可能的共素数对时，显示它并停止循环。

C++

                         // CPP program to represent a number                       
                         // as sum of a co-prime pair such that                       
                         // difference between them is minimum                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to check if pair                       
                         // is co-prime or not                       
                         bool                                     coprime(                                     int                                     a,                                     int                                     b)                       
                         {                       
                                                 return                                     (__gcd(a, b) == 1);                       
                         }                       
           
                         // function to find and print                       
                         // co-prime pair                       
                         void                                     pairSum(                                     int                                     n){                       
                                   
                                                 int                                     mid = n / 2;                       
           
                                                 for                                     (                                     int                                     i = mid; i >= 1; i--) {                       
                                                 if                                     (coprime(i, n - i) == 1) {                       
                                                 cout << i <<                                     " "                                     << n - i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 11;                       
                                                 pairSum(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to represent a                       
                         // number as sum of a co-prime                       
                         // pair such that difference                       
                         // between them is minimum                       
                         class                                     GFG                       
                         {                       
                                                 static                                     int                                     __gcd(                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                                 return                                     b ==                                     0                                     ? a :                       
                                                 __gcd(b, a % b);                       
                                                 }                       
                                   
                                                 // function to check if pair                       
                                                 // is co-prime or not                       
                                                 static                                     boolean                                     coprime(                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                                 return                                     (__gcd(a, b) ==                                     1                                     );                       
                                                 }                       
                                   
                                                 // function to find and                       
                                                 // print co-prime pair                       
                                                 static                                     void                                     pairSum(                                     int                                     n)                       
                                                 {                       
                                                 int                                     mid = n /                                     2                                     ;                       
                                   
                                                 for                                     (                                     int                                     i = mid; i >=                                     1                                     ; i--)                       
                                                 {                       
                                                 if                                     (coprime(i, n - i) ==                                     true                                     )                       
                                                 {                       
                                                 System.out.print( i +                                     " "                                     +                       
                                                 (n - i));                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     n =                                     11                                     ;                       
                                                 pairSum(n);                       
                                   
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007                       

Python3

                         # Python3 program to represent                       
                         # a number as sum of a co-prime                       
                         # pair such that difference                       
                         # between them is minimum                       
                         import                                     math                       
           
                         # function to check if pair                       
                         # is co-prime or not                       
                         def                                     coprime(a, b):                       
                                                 return                                     1                                     if                                     (math.gcd(a, b)                                     =                                     =                                     1                                     )                                     else                                     0                                     ;                       
           
                         # function to                       
                         # find and print                       
                         # co-prime pair                       
                         def                                     pairSum(n):                       
                                                 mid                                     =                                     int                                     (n                                     /                                     2                                     );                       
                                                 i                                     =                                     mid;                       
                                                 while                                     (i >                                     =                                     1                                     ):                       
                                                 if                                     (coprime(i, n                                     -                                     i)                                     =                                     =                                     1                                     ):                       
                                                 print                                     (i, n                                     -                                     i);                       
                                                 break                                     ;                       
                                                 i                                     =                                     i                                     -                                     1                                     ;                       
           
                         # Driver code                       
                         n                                     =                                     11                                     ;                       
                         pairSum(n);                       
           
                         # This code is contributed                       
                         # by mits                       

C#

                         // C# program to represent a number                       
                         // as sum of a co-prime pair such that                       
                         // difference between them is minimum                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 static                                     int                                     __gcd(                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                                 return                                     b == 0 ? a : __gcd(b, a % b);                       
                                                 }                       
                                   
                                                 // function to check if pair                       
                                                 // is co-prime or not                       
                                                 static                                     bool                                     coprime(                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                                 return                                     (__gcd(a, b) == 1);                       
                                                 }                       
                                   
                                                 // function to find and print                       
                                                 // co-prime pair                       
                                                 static                                     void                                     pairSum(                                     int                                     n)                       
                                                 {                       
                                                 int                                     mid = n / 2;                       
                                   
                                                 for                                     (                                     int                                     i = mid; i >= 1; i--)                       
                                                 {                       
                                                 if                                     (coprime(i, n - i) ==                                     true                                     )                       
                                                 {                       
                                                 Console.Write( i +                                     " "                       
                                                 + (n - i));                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 11;                       
                                                 pairSum(n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007                       

PHP

                         <?php                       
                         // PHP program to represent                       
                         // a number as sum of a                       
                         // co-prime pair such that                       
                         // difference between them                       
                         // is minimum                       
           
                         function                                     gcd(                                     $num1                                     ,                                     $num2                                     )                       
                         {                       
                                   
                         /* finds the greatest common                       
                         factor between two numbers */                       
                         while                                     (                                     $num2                                     != 0)                       
                         {                       
                                                 $t                                     =                                     $num1                                     %                                     $num2                                     ;                       
                                                 $num1                                     =                                     $num2                                     ;                       
                                                 $num2                                     =                                     $t                                     ;                       
                         }                       
                         return                                     $num1                                     ;                       
                         }                       
           
                         // function to check if pair                       
                         // is co-prime or not                       
                         function                                     coprime(                                     $a                                     ,                                     $b                                     )                       
                         {                       
                                                 if                                     (gcd(                                     $a                                     ,                                     $b                                     ) == 1)                       
                                                 return                                     1;                       
                                                 else                       
                                                 return                                     0;                       
                         }                       
           
                         // function to find and                       
                         // print co-prime pair                       
                         function                                     pairSum(                                     $n                                     )                       
                         {                       
                                                 $mid                                     = (int)((                                     $n                                     / 2));                       
           
                                                 for                                     (                                     $i                                     =                                     $mid                                     ;                                     $i                                     >= 1;                                     $i                                     --)                       
                                                 {                       
                                                 if                                     (coprime(                                     $i                                     ,                                     $n                                     -                                     $i                                     ) == 1)                       
                                                 {                       
                                                 echo                                     $i                                     .                                     " "                                     . (                                     $n                                     -                                     $i                                     );                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         $n                                     = 11;                       
                         pairSum(                                     $n                                     );                       
           
                         // This code is contributed                       
                         // by mits                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript  program to represent a                       
                         // number as sum of a co-prime                       
                         // pair such that difference                       
                         // between them is minimum                       
           
                                                 function                                     __gcd(a, b)                       
                                                 {                       
                                                 return                                     b == 0 ? a :                       
                                                 __gcd(b, a % b);                       
                                                 }                       
                                   
                                                 // function to check if pair                       
                                                 // is co-prime or not                       
                                                 function                                     coprime(a, b)                       
                                                 {                       
                                                 return                                     (__gcd(a, b) == 1);                       
                                                 }                       
                                   
                                                 // function to find and                       
                                                 // print co-prime pair                       
                                                 function                                     pairSum(n)                       
                                                 {                       
                                                 let mid = Math.floor(n / 2);                       
                                   
                                                 for                                     (let i = mid; i >= 1; i--)                       
                                                 {                       
                                                 if                                     (coprime(i, n - i) ==                                     true                                     )                       
                                                 {                       
                                                 document.write( i +                                     " "                                     +                       
                                                 (n - i));                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                         // Driver code                       
           
                                                 let n = 11;                       
                                                 pairSum(n);                       
                                   
                         </script>                       