[经典面试题]给你一个自然数N，求[6,N]之内的所有素数中，两两之和为偶数的那些偶数

本文主要是介绍[经典面试题]给你一个自然数N，求[6,N]之内的所有素数中，两两之和为偶数的那些偶数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目】

给你一个自然数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，求[6,N]之内的所有素数中，两两之和为偶数的那些偶数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---