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


目录
相关文章
|
2月前
|
C++
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
|
2月前
|
机器学习/深度学习 存储 算法
数据结构与算法面试题:给定非负整数 m 和 n,计算不大于 m 的数字中,素数的个数。(提示:算法原理为埃氏筛、线性筛)
数据结构与算法面试题:给定非负整数 m 和 n,计算不大于 m 的数字中,素数的个数。(提示:算法原理为埃氏筛、线性筛)
56 0
|
2月前
剑指Offer LeetCode 面试题21. 调整数组顺序使奇数位于偶数前面
剑指Offer LeetCode 面试题21. 调整数组顺序使奇数位于偶数前面
34 0
剑指Offer - 面试题21:调整数组顺序使奇数位于偶数前面
剑指Offer - 面试题21:调整数组顺序使奇数位于偶数前面
39 0
|
存储 算法 开发者
面试官本拿求素数搞我,但被我优雅的“回击“了(素数筛)
现在的面试官,是无数开发者的梦魇,能够吊打面试官的属实不多,因为大部分面试官真的有那么那几下子。但在面试中,我们这些小生存者不能全盘否定只能单点突破—从某个问题上让面试官眼前一亮。这不,今天就来分享来了。
101 0
面试官本拿求素数搞我,但被我优雅的“回击“了(素数筛)
|
关系型数据库 MySQL 测试技术
软件测试mysql面试题:如何从表中选择所有偶数记录?
软件测试mysql面试题:如何从表中选择所有偶数记录?
69 0
面试 6:调整数组顺序使奇数位于偶数前面
今天给大家带来的是 《剑指 Offer》习题:调整数组顺序使奇数位于偶数前面,纯 Java 实现希望大家多加思考。 面试题:输入一个整型数组,实现一个函数来调整该数组中的数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分,希望时间复杂度尽量小。
2370 0
|
14天前
|
存储 算法 Java
Java面试之SpringCloud篇
Java面试之SpringCloud篇
30 1
|
14天前
|
缓存 NoSQL Redis
Java面试之redis篇
Java面试之redis篇
34 0
|
14天前
|
SQL 关系型数据库 MySQL
java面试之MySQL数据库篇
java面试之MySQL数据库篇
22 0
java面试之MySQL数据库篇