[经典面试题]给你一个自然数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;
}