永恒的蓝色梦想 发表于 2020-7-3 17:00:29

题目357：质数生成数

本帖最后由 永恒的蓝色梦想 于 2020-7-3 17:02 编辑

https://s1.ax1x.com/2020/07/03/NX5dVU.png
https://s1.ax1x.com/2020/07/03/NX5UbT.png

永恒的蓝色梦想 发表于 2020-7-3 17:01:46

恭喜我自己，研究了好多天，一道题没研究出来{:10_260:}
乖乖滚回来翻译{:10_312:}

永恒的蓝色梦想 发表于 2020-7-3 17:03:15

这道题好像可以用两个筛子做{:10_277:}

lijiachen 发表于 2020-7-19 14:20:39

永恒的蓝色梦想 发表于 2020-7-3 17:01
恭喜我自己，研究了好多天，一道题没研究出来
乖乖滚回来翻译

欧拉计划不是很难啊？
{:10_281:}

lijiachen 发表于 2020-7-19 14:21:22

蹭鱼币~

lijiachen 发表于 2020-7-19 15:10:38

本帖最后由 lijiachen 于 2020-7-19 15:20 编辑

永恒的蓝色梦想 发表于 2020-7-3 17:01
恭喜我自己，研究了好多天，一道题没研究出来
乖乖滚回来翻译

我已经研究出了一个算法，小范围内（10000以内）可行，但就是算的太慢，100000000这么大的范围算不了{:10_266:}{:10_266:}{:10_266:}

代号-K 发表于 2020-7-21 14:11:23

本帖最后由 代号-K 于 2020-7-21 14:36 编辑

第一步，先求1~100000000范围内的质数
第二步，（对于整数 i）判断 i+1 是否为质数
第三步，是，则进行判断 i 是否为质数生成数，否则 i = i + 1， 跳转第二步

也可以把两个步骤合在一起
如果 i 为质数，则判断 i -1 是否为质数生成数
质数生成数也就是因子对之和是否为质数

这个也是求质数问题

有理由相信 发表于 2020-7-23 14:30:52

代号-K 发表于 2020-7-21 14:11
第一步，先求1~100000000范围内的质数
第二步，（对于整数 i）判断 i+1 是否为质数
第三步，是，则进行判 ...

所以是从质数生成数的因子对中最特殊的一对（1和本身）入手，找到可能是质数生成数的i，再筛选。

Stubborn 发表于 2020-9-11 16:45:11

本帖最后由 Stubborn 于 2020-9-11 16:47 编辑

我看看题目要求哈

求1个亿以内的所有n的和。

   n满足以下条件。

对于N的每一个因数，d + n / d 都是质数。

guosl 发表于 2021-3-5 08:26:28

答案：1739023853137
/*
答案：1739023853137
耗时：1.63907秒
*/
#include <iostream>
#include <cstring>
#include <omp.h>

using namespace std;
bool a;
bool b;

int main(void)
{
double t = omp_get_wtime();
long long ans = 0;
//素数打表开始
memset(a, 1, sizeof(a));
memset(b, 1, sizeof(b));
a = false;
for (long long i = 2; i <= 10000; i++)
{
    if (a == true)
      for (long long j = i; i*j <= 100000000; j++)
      a = false;
}
//素数打表结束
#pragma omp parallel for reduction(+: ans) shared(b) schedule(guided)
for (long long x = 1; x <= 100000000; x++)
{
    b = true;
    if (x != 1 && x % 2 == 1)//排除奇数
      continue;
    for (long long y = 1; y <= x / y; y++)
    {
      if (x%y == 0 && a == false)
      {
      b = false;
      break;
      }
    }
    if (b == true)
      ans = ans + x;
}
t = omp_get_wtime() - t;
cout << ans << endl << t << endl;
return 0;
}

阿萨德按时 发表于 2021-11-26 11:00:33

{:10_254:}

myqf123 发表于 2022-4-15 16:38:11

{:10_278:}

myqf123 发表于 2022-4-15 17:25:58

{:10_259:}

unsigned_int 发表于 2023-8-24 20:30:39

{:10_277:}

unsigned_int 发表于 2023-8-26 22:02:29

yubi
页: [1]
查看完整版本: 题目357：质数生成数