【题目】
给你一个自然数N,求[6,N]之内的所有素数中,两两之和为偶数的那些偶数
---------百度校招
【分析】
1.对于给定的N,我们可以用筛法求素素数的方法在O(n)的时间复杂度内求出所有的素数。
2.除2之外,所有的素数相加都为偶数,所以求出6~N之间的素数,打印两两的和就可以,时间复杂度O(n^2)
【代码】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = 1000001;
int Mark[MAX];
int Prime[MAX];
// 刷法求素数
void IsPrime(){
int index = 0;
// 初始化
memset(Mark,0,sizeof(Mark[0])*MAX);
for(int i = 2;i <= MAX;i++){
//如果未标记则得到一个素数
if(Mark[i] == 0){
Prime[index++] = i;
}//if
//标记目前得到的素数的i倍为非素数
for(int j = 0;j < index,Prime[j] * i <= MAX;j++){
Mark[Prime[j]*i] = 1;
// prime数组 中的素数是递增的,当 i 能整除 prime[j],
// 那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉
if(i % Prime[j] == 0){
break;
}//if
}//for
}//for
}
void PrimeSum(int n){
int sum;
int* array = (int*)malloc(sizeof(int)*(2*n));
// 初始化
memset(array,0,sizeof(array[0])*(2*n+1));
// 统计
for(int i = 6;i <= n;i++){
// 非素数
if(Mark[i] == 1){
continue;
}
for(int j = i+1;j <= n;j++){
// 非素数
if(Mark[j] == 1){
continue;
}
sum = i+j;
// 两两之和为偶数的那些偶数
if(array[sum] == 0){
array[sum] = 1;
}//if
}//for
}//for
// 输出两两之和为偶数的那些偶数
for(int i = 18;i <= (n+n);i++){
if(array[i]){
cout<<i<<endl;
}//if
}//for
}
int main(){
//筛法求素数
IsPrime();
// 两两之和为偶数的那些偶数
PrimeSum(11);
return 0;
}
分享到:
相关推荐
任意输入一个偶数n(n>4),请将它分解为两个素数之和。
编写一个程序,从键盘输入一个偶数,输出该偶数写成的两个素数之和
而后编制主函数,任意输入一个大于4的偶数d,找出满足d=d1+d2的所有数对,其中要求d1与d2均为素数(通过调用prime来判断素数)。如偶数18可以分解为11+7以及13+5;而偶数80可以分解为:43+37、61+19、67+13、73+7。
编程求解1到n之间所有素数之和,输入只有一个n,输出为一个数。
表偶数(≥6)为两个奇素数之和,许作铭,罗贵文,本文通过利用一种新的筛法与台阶理论,得到了任意偶数(≥6)表为“两个奇素数之和”表法个数的显示公式或称Goldbach定理。应用本定
验证哥德巴赫猜想,任意一个大于等于6的偶数都可以分解为两个素数之和,VB6.0源代码编写
求解第N个质数(第N个素数)vs2010项目计算时间差不多 用的是试除法
素数又叫质数,质数是指在大于1的自然数中,除了1和它本身以外,不能被其他自然数整除的数。 问题: 输入一个整数n,输出1~n中的素数,里有详细解释,有问题也欢迎留言!谢谢支持啦~
正偶数分解两个素数之和
【描述】求m-n以内所有素数之和并输出。...
LabView 计算整数N内所有的素数 示例代码
用来筛选自然数中的质数。 可以从小到大筛选。
验证哥德巴赫猜想:一个大偶数可以分解为两个素数之和。分解500~1000之间的大偶数。
编写C++程序完成以下功能: (1) 提示用户输入N; (2) 计算出从2到N之间的所有素数; (3) 将结果保存在一个文本文件中。
一个文本文件中,每行文本只包含一个素数数据。 2. 编写程序求出10万以内的所有素数,然后再判断这些素数中 哪些是由素数拼接而成的。例如素数23就符合条件, 23本身是素数,其由素数2,和素数3拼接(连接)组成...
C# 请输入一个偶数 您输入的不是偶数,请输入一个偶数 该偶数
输入一个小于21的数n构成一个循环, 将1-n个数全部用上, 相邻数之和为质数。 输出有多少种情况。
我们这一软件,您只要输入任意两个正整数,点击[开始寻找]按钮,几秒钟或是较短时间,就可找出该闭区间内所有素数。查找出的素数可以逐行显示,便于导入Excel等工具,也可连续显示,方便插入论文,而且可所列数据既...
输出n以内的所有素数输出n以内的所有素数输出n以内的所有素数输出n以内的所有素数输出n以内的所有素数输出n以内的所有素数输出n以内的所有素数输出n以内的所有素数输出n以内的所有素数输出n以内的所有素数输出n以内...
而后编制主函数,任意输入一个大于4的偶数d,找出满足d=d1+d2的所有数对,其中要求d1与d2均为素数(通过调用prime来判断素数)。如偶数18可以分解为11+7以及13+5;而偶数80可以分解为:43+37、61+19、67+13、73+7。...