[新手入门] 筛法求素数

[复制链接]
查看9730 | 回复0 | 2020-3-7 16:53:19 | 显示全部楼层 |阅读模式
题目:http://www.wechall.net/challenge/training/prime_factory/index.php
判断一个素数各位置上的数字和是否也是素数
(回顾求素数的方法)

#include<string.h>
#include<iostream>
using namespace std;

const int MAXN = 2000000;  // bool数组长度有限制(如果需要更大的空间可以尝试用其它语言)   用来标记当前位置上是不是素数

// 求素数的函数  --  筛法
void prime(bool primes[]) {
        int prime = 2;  // 2是最小的素数  从2开始去除倍数
        int now;  // 当前不是素数的数字  
        while (prime < MAXN) {
                if (primes[prime]) {
                        int m = 2;  // 倍数
                        now = prime * m;
                        while (now < MAXN) {
                                primes[now] = false;
                                m++;
                                now = prime * m;
                        }
                }
                prime++;
        }
}

// 需求函数
int num_sum(int x) {  // 假设1000000<x<9999999
        int sum = 0;
        while (x > 0) {
                sum += x % 10;
                x /= 10;
        }
        return sum;
}

int main()
{
        bool primes[MAXN];
        memset(primes, true, sizeof(primes));  // 假设所有数都是素数
        primes[1] = false;  // 1不是素数
       
        prime(primes);
       
        int now = 1000000;
        int index = 0;
        while (index < 2) {
                if (primes[now] && primes[num_sum(now)]) {
                        cout<<now;
                        index++;
                }
                now++;
        }
       
        return 0;
}

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

4

主题

6

帖子

65

积分

小有名气

Rank: 3Rank: 3

积分
65