在中国退休后移民美国:四个素数之和问题
来源:百度文库 编辑:神马品牌网 时间:2024/04/25 14:33:52
大家都知道素数有无穷多个,这个理论是由欧拉证明的。那么任何一个整数都能表示为四个素数之和吗?现在需要你通过编程来验证这个问题。注意解决此问题的方法必须高效,因为我们给你的时间不多。
在本问题中,一个素数是指一个正整数,且该正整数有且只有两个不同的因子。例如37是一个素数,因为它只有两个不同的因子37和1。
输入
每行输入一个整数N(N<=10000000),你需要将这个数字表示为四个素数之和。输入0时程序退出。
输出
对于每个非零的输入,输出一行,这行中应当包含符合要求的四个素数。如果这个数不能表示为四个素数之和,那么输出一行“Impossible”。对于同一个输入,答案可能是不唯一的,只需输出一种合理的就可以了。
提示
解决这个问题的关键在“高效”,要想高效的解决这个问题,需要借助前人已经证明了的思想。相信大家都听说过“哥德巴赫猜想”,那么要想解决这个问题,就可以
借助这个猜想中已经被证明的部分了。那么“哥德巴赫猜想”的内容是什么以及在这个题目中应当如何使用,就留给大家自己去解决了。
在这个题目中不可避免的要实现一个判断某个整数是否为素数的函数,这个函数也是有很多值得优化的地方的,现在简要说明一下:
1. 2 以上的所有的偶数都不是素数,因此没有必要对偶数进行判断;
2. 一个数 N 的因子除了 1 和它自身外,都不会大于 ,而当一个因子大于 时,则必然有一个小于 的因子和它对应。
如果把以上的内容都考虑到了,那么相应的程序一定是非常高效的。
测试用例 0 测试输入 1 23
2 36
3 46
4 0
测试用例 1
1 5028
2 8047
3 12045
4 0
测试用例 2
1 293472
2 9283642
3 2347123
4 0
期待的输出
1 3 11 2 7
2 3 7 13 13
3 11 11 17 7
1 2 2 3 5021
2 2 3 3 8039
3 2 3 3 12037
1 2 2 37 293431
2 2 2 31 9283607
3 2 3 271 2346847
请编出具体的C程序。
在本问题中,一个素数是指一个正整数,且该正整数有且只有两个不同的因子。例如37是一个素数,因为它只有两个不同的因子37和1。
输入
每行输入一个整数N(N<=10000000),你需要将这个数字表示为四个素数之和。输入0时程序退出。
输出
对于每个非零的输入,输出一行,这行中应当包含符合要求的四个素数。如果这个数不能表示为四个素数之和,那么输出一行“Impossible”。对于同一个输入,答案可能是不唯一的,只需输出一种合理的就可以了。
提示
解决这个问题的关键在“高效”,要想高效的解决这个问题,需要借助前人已经证明了的思想。相信大家都听说过“哥德巴赫猜想”,那么要想解决这个问题,就可以
借助这个猜想中已经被证明的部分了。那么“哥德巴赫猜想”的内容是什么以及在这个题目中应当如何使用,就留给大家自己去解决了。
在这个题目中不可避免的要实现一个判断某个整数是否为素数的函数,这个函数也是有很多值得优化的地方的,现在简要说明一下:
1. 2 以上的所有的偶数都不是素数,因此没有必要对偶数进行判断;
2. 一个数 N 的因子除了 1 和它自身外,都不会大于 ,而当一个因子大于 时,则必然有一个小于 的因子和它对应。
如果把以上的内容都考虑到了,那么相应的程序一定是非常高效的。
测试用例 0 测试输入 1 23
2 36
3 46
4 0
测试用例 1
1 5028
2 8047
3 12045
4 0
测试用例 2
1 293472
2 9283642
3 2347123
4 0
期待的输出
1 3 11 2 7
2 3 7 13 13
3 11 11 17 7
1 2 2 3 5021
2 2 3 3 8039
3 2 3 3 12037
1 2 2 37 293431
2 2 2 31 9283607
3 2 3 271 2346847
请编出具体的C程序。
这个问题放在这里是不是有点太专业了
其实不难,很容易实现的
为个很好编的呀你想你一下就可以了呀。你知道怎么编素数的程序吧那在那个的基础上加上一个判断语句就可以了呀
想给你编个,但是不懂数论.没思路