将给定的数表示为4个正素数的和。如果无法表达，则打印“-1”。
null
例如：
Input: 24Output: 3 11 3 7 Explanation : 3+11+3+7 = 24 and 3, 11, 7 are all prime. Input: 46Output: 11 11 17 7 explanation : 11+11+17+7 = 46 and 11, 7, 17 are all prime.
方法： 每一个大于2的偶数整数都可以表示为两个数的和 哥德巴赫猜想 . 下面是一些将数字表示为4个素数之和的事实。
- 数字必须大于或等于8，因为2是最小的素数
- 如果给定的数是偶数，我们可以把它分解为（2+2）+x，这样x就保持偶数，并且可以分解成两个素数。
- 如果给定的数是奇数，我们可以把它分解为（2+3）+x，这样x保持偶数，并且可以分解为两个素数。
现在我们可以很容易地用两个素数的和来表示n 链接
C++
// CPP program to express n as sum of 4 primes. #include <bits/stdc++.h> using namespace std; // function to check if a number is prime or not int isPrime( int x) { // does square root of the number int s = sqrt (x); // traverse from 2 to sqrt(n) for ( int i = 2; i <= s; i++) // if any divisor found then non prime if (x % i == 0) return 0; // if no divisor is found then it is a prime return 1; } void Num( int x, int & a, int & b) { // iterates to check prime or not for ( int i = 2; i <= x / 2; i++) { // calls function to check if i and x-i // is prime or not if (isPrime(i) && isPrime(x - i)) { a = i; b = x - i; // if two prime numbers are found, // then return return ; } } } // function to generate 4 prime numbers adding upto n void generate( int n) { // if n<=7 then 4 numbers cannot sum to // get that number if (n <= 7) cout << "Impossible to form" << endl; // a and b stores the last two numbers int a, b; // if it is not even then 2 and 3 are first // two of sequence if (n % 2 != 0) { // calls the function to get the other // two prime numbers considering first two // primes as 2 and 3 (Note 2 + 3 = 5) Num(n - 5, a, b); // print 2 and 3 as the firsts two prime // and a and b as the last two. cout << "2 3 " << a << " " << b << endl; } // if it is even then 2 and 2 are first two // of sequence else { /// calls the function to get the other // two prime numbers considering first two // primes as 2 and 2 (Note 2 + 2 = 4) Num(n - 4, a, b); // print 2 and 2 as the firsts two prime // and a and b as the last two. cout << "2 2 " << a << " " << b << endl; } } // driver program to test the above function int main() { int n = 28; generate(n); return 0; } |
JAVA
// Java program to express n as sum of // 4 primes. class GFG { static int a = 0 , b = 0 ; // function to check if a number // is prime or not static int isPrime( int x) { // does square root of the // number int s = ( int )Math.sqrt(x); // traverse from 2 to sqrt(n) for ( int i = 2 ; i <= s; i++) // if any divisor found // then non prime if (x % i == 0 ) return 0 ; // if no divisor is found // then it is a prime return 1 ; } static void Num( int x) { // iterates to check prime // or not for ( int i = 2 ; i <= x / 2 ; i++) { // calls function to check // if i and x-i is prime // or not if (isPrime(i) != 0 && isPrime(x - i) != 0 ) { a = i; b = x - i; // if two prime numbers // are found, then return return ; } } } // function to generate 4 prime // numbers adding upto n static void generate( int n) { // if n<=7 then 4 numbers cannot // sum to get that number if (n <= 7 ) System.out.println( "Impossible" + " to form" ); // if it is not even then 2 and 3 // are first two of sequence if (n % 2 != 0 ) { // calls the function to get the // other two prime numbers // considering first two primes // as 2 and 3 (Note 2 + 3 = 5) Num(n - 5 ); // print 2 and 3 as the firsts // two prime and a and b as the // last two. System.out.println( "2 3 " + a + " " + b); } // if it is even then 2 and 2 are // first two of sequence else { /// calls the function to get the // other two prime numbers // considering first two primes as // 2 and 2 (Note 2 + 2 = 4) Num(n - 4 ); // print 2 and 2 as the firsts // two prime and a and b as the // last two. System.out.println( "2 2 " + a + " " + b); } } // Driver function to test the above // function public static void main(String[] args) { int n = 28 ; generate(n); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to express # n as sum of 4 primes. import math; # function to check if a # number is prime or not def isPrime(x): # does square root # of the number s = int (math.sqrt(x)) # traverse from 2 to sqrt(n) for i in range ( 2 ,s + 1 ): # if any divisor found # then non prime if (x % i = = 0 ): return 0 # if no divisor is found # then it is a prime return 1 def Num(x): # iterates to check # prime or not ab = [ 0 ] * 2 for i in range ( 2 , int (x / 2 ) + 1 ): # calls function to check # if i and x-i is prime # or not if (isPrime(i) ! = 0 and isPrime(x - i) ! = 0 ): ab[ 0 ] = i ab[ 1 ] = x - i # if two prime numbers # are found, then return return ab # function to generate 4 prime # numbers adding upto n def generate(n): # if n<=7 then 4 numbers cannot # sum to get that number if (n < = 7 ): print ( "Impossible to form" ) # if it is not even then 2 and # 3 are first two of sequence if (n % 2 ! = 0 ): # calls the function to get # the other two prime numbers # considering first two primes # as 2 and 3 (Note 2 + 3 = 5) ab = Num(n - 5 ) # print 2 and 3 as the firsts # two prime and a and b as the # last two. print ( "2 3" ,ab[ 0 ],ab[ 1 ]) # if it is even then 2 and 2 are # first two of sequence else : # calls the function to get # the other two prime numbers # considering first two primes # as 2 and 2 (Note 2 + 2 = 4) ab = Num(n - 4 ) # print 2 and 2 as the firsts # two prime and a and b as the # last two. print ( "2 2" ,ab[ 0 ],ab[ 1 ]) # Driver Code if __name__ = = '__main__' : n = 28 generate(n) # This code is contributed by mits. |
C#
// C# program to express n as sum of // 4 primes. using System; class GFG { static int a = 0, b = 0; // function to check if a number // is prime or not static int isPrime( int x) { // does square root of the // number int s = ( int )Math.Sqrt(x); // traverse from 2 to sqrt(n) for ( int i = 2; i <= s; i++) // if any divisor found // then non prime if (x % i == 0) return 0; // if no divisor is found // then it is a prime return 1; } static void Num( int x) { // iterates to check prime // or not for ( int i = 2; i <= x / 2; i++) { // calls function to check // if i and x-i is prime // or not if (isPrime(i) != 0 && isPrime(x - i) != 0) { a = i; b = x - i; // if two prime numbers // are found, then return return ; } } } // function to generate 4 prime // numbers adding upto n static void generate( int n) { // if n<=7 then 4 numbers cannot // sum to get that number if (n <= 7) Console.Write( "Impossible" + " to form" ); // if it is not even then 2 and // 3 are first two of sequence if (n % 2 != 0) { // calls the function to get // the other two prime numbers // considering first two primes // as 2 and 3 (Note 2 + 3 = 5) Num(n - 5); // print 2 and 3 as the firsts // two prime and a and b as the // last two. Console.Write( "2 3 " + a + " " + b); } // if it is even then 2 and 2 are // first two of sequence else { /// calls the function to get // the other two prime numbers // considering first two primes // as 2 and 2 (Note 2 + 2 = 4) Num(n - 4); // print 2 and 2 as the firsts // two prime and a and b as the // last two. Console.Write( "2 2 " + a + " " + b); } } // Driver function to test the above // function public static void Main() { int n = 28; generate(n); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to express // n as sum of 4 primes. $a = 0; $b = 0; // function to check if a // number is prime or not function isPrime( $x ) { // does square root // of the number $s = (int)(sqrt( $x )); // traverse from 2 to sqrt(n) for ( $i = 2; $i <= $s ; $i ++) // if any divisor found // then non prime if ( $x % $i == 0) return 0; // if no divisor is found // then it is a prime return 1; } function Num( $x ) { global $a ; global $b ; // iterates to check // prime or not for ( $i = 2; $i <= (int)( $x / 2); $i ++) { // calls function to check // if i and x-i is prime // or not if (isPrime( $i ) != 0 && isPrime( $x - $i ) != 0) { $a = $i ; $b = $x - $i ; // if two prime numbers // are found, then return return ; } } } // function to generate 4 prime // numbers adding upto n function generate( $n ) { global $a ; global $b ; // if n<=7 then 4 numbers cannot // sum to get that number if ( $n <= 7) echo "Impossible to form" ; // if it is not even then 2 and // 3 are first two of sequence if ( $n % 2 != 0) { // calls the function to get // the other two prime numbers // considering first two primes // as 2 and 3 (Note 2 + 3 = 5) Num( $n - 5); // print 2 and 3 as the firsts // two prime and a and b as the // last two. echo "2 3 $a $b" ; } // if it is even then 2 and 2 are // first two of sequence else { // calls the function to get // the other two prime numbers // considering first two primes // as 2 and 2 (Note 2 + 2 = 4) Num( $n - 4); // print 2 and 2 as the firsts // two prime and a and b as the // last two. echo "2 2 $a $b" ; } } // Driver Code $n = 28; generate( $n ); // This code is contributed by mits. ?> |
Javascript
<script> // JavaScript program to express n as sum of // 4 primes. let a = 0, b = 0; // function to check if a number // is prime or not function isPrime(x) { // does square root of the // number let s = Math.sqrt(x); // traverse from 2 to sqrt(n) for (let i = 2; i <= s; i++) // if any divisor found // then non prime if (x % i == 0) return 0; // if no divisor is found // then it is a prime return 1; } function Num(x) { // iterates to check prime // or not for (let i = 2; i <= x / 2; i++) { // calls function to check // if i and x-i is prime // or not if (isPrime(i) != 0 && isPrime(x - i) != 0) { a = i; b = x - i; // if two prime numbers // are found, then return return ; } } } // function to generate 4 prime // numbers adding upto n function generate(n) { // if n<=7 then 4 numbers cannot // sum to get that number if (n <= 7) document.write( "Impossible" + " to form" ); // if it is not even then 2 and 3 // are first two of sequence if (n % 2 != 0) { // calls the function to get the // other two prime numbers // considering first two primes // as 2 and 3 (Note 2 + 3 = 5) Num(n - 5); // print 2 and 3 as the firsts // two prime and a and b as the // last two. document.write( "2 3 " + a + " " + b); } // if it is even then 2 and 2 are // first two of sequence else { /// calls the function to get the // other two prime numbers // considering first two primes as // 2 and 2 (Note 2 + 2 = 4) Num(n - 4); // print 2 and 2 as the firsts // two prime and a and b as the // last two. document.write( "2 2 " + a + " " + b); } } // Driver Code let n = 28; generate(n); </script> |
输出：
2 2 5 19
时间复杂性： O（n）sqrt（n）） 辅助空间： O（1）
本文由 拉贾·维克拉马蒂亚 如果你喜欢Geeksforgek，并且想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
