题目357：质数生成数

永恒的蓝色梦想

                               
登录/注册后可看大图

                               
登录/注册后可看大图

永恒的蓝色梦想

恭喜我自己，研究了好多天，一道题没研究出来
乖乖滚回来翻译

永恒的蓝色梦想

这道题好像可以用两个筛子做

lijiachen

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

欧拉计划不是很难啊？

lijiachen

蹭鱼币~

lijiachen

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

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

代号-K

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

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

这个也是求质数问题

有理由相信

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

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

Stubborn

我看看题目要求哈

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

   n满足以下条件。

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

guosl

答案：1739023853137

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

using namespace std;
bool a[100000001];
bool b[100000001];

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

阿萨德按时

myqf123

myqf123

unsigned_int

unsigned_int

yubi