题目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

1. /*
   
2. 答案：1739023853137
   
3. 耗时：1.63907秒
   
4. */
   
5. #include <iostream>
   
6. #include <cstring>
   
7. #include <omp.h>
   
8. 
   
9. using namespace std;
   
10. bool a[100000001];
    
11. bool b[100000001];
    
12. 
    
13. int main(void)
    
14. {
    
15.   double t = omp_get_wtime();
    
16.   long long ans = 0;
    
17.   //素数打表开始
    
18.   memset(a, 1, sizeof(a));
    
19.   memset(b, 1, sizeof(b));
    
20.   a[1] = false;
    
21.   for (long long i = 2; i <= 10000; i++)
    
22.   {
    
23.     if (a[i] == true)
    
24.       for (long long j = i; i*j <= 100000000; j++)
    
25.         a[j * i] = false;
    
26.   }
    
27.   //素数打表结束
    
28. #pragma omp parallel for reduction(+: ans) shared(b) schedule(guided)
    
29.   for (long long x = 1; x <= 100000000; x++)
    
30.   {
    
31.     b[x] = true;
    
32.     if (x != 1 && x % 2 == 1)//排除奇数
    
33.       continue;
    
34.     for (long long y = 1; y <= x / y; y++)
    
35.     {
    
36.       if (x%y == 0 && a[y + x / y] == false)
    
37.       {
    
38.         b[x] = false;
    
39.         break;
    
40.       }
    
41.     }
    
42.     if (b[x] == true)
    
43.       ans = ans + x;
    
44.   }
    
45.   t = omp_get_wtime() - t;
    
46.   cout << ans << endl << t << endl;
    
47.   return 0;
    
48. }
    

复制代码

阿萨德按时

myqf123

myqf123

unsigned_int

unsigned_int

yubi