求F15后的第一个素数

mathe

试验了一下先筛选，在gmp概率素数测试，在我笔记本上，
test 10 cost 6s
test 20 cost 11s
test 30 cost 17s
test 40 cost 23s
test 50 cost 28s
test 60 cost 34s
test 70 cost 40s
test 80 cost 46s
test 90 cost 51s
test 100 cost 57s
test 110 cost 63s
test 120 cost 68s
test 130 cost 74s
test 140 cost 80s
test 150 cost 86s
test 160 cost 92s
M14+2774 found
test 170 cost 99s
test 180 cost 105s
test 190 cost 110s
test 200 cost 116s
test 210 cost 122s
test 220 cost 128s
100秒左右可以找到M14的解。但是M15大概每测试10个素数需要35s,预计测试6K左右个素数可以找到结果，预计需要6小时左右，和nyy的计算结果花费时间基本一个数量级

nyy

mathe 发表于 2022-9-19 15:16
试验了一下先筛选，在gmp概率素数测试，在我笔记本上，
test 10 cost 6s
test 20 cost 11s

这个是F15之前的第一个素数=F15-25354，
这个间隔是25354呀，你6k怎么可能找到结果？看错了吗？

nyy

mathe 发表于 2022-9-19 15:16
试验了一下先筛选，在gmp概率素数测试，在我笔记本上，
test 10 cost 6s
test 20 cost 11s

你真聪明，居然用小素数筛选，我就比较笨了，我试了一下，用小素数筛选，确实快一些！

nyy

这个是F15后面的三个连续素数。
(2^(2^15)+1)+118112
(2^(2^15)+1)+143904
(2^(2^15)+1)+145026

nyy

再继续后面的两个素数：
(2^(2^15)+1)+160770
(2^(2^15)+1)+162872

nyy

再继续后面的两个素数：
(2^(2^15)+1)+182004
(2^(2^15)+1)+187860
F15后面的全部素数（7个）如下：
(2^(2^15)+1)+118112
(2^(2^15)+1)+143904
(2^(2^15)+1)+145026
(2^(2^15)+1)+160770
(2^(2^15)+1)+162872
(2^(2^15)+1)+182004
(2^(2^15)+1)+187860

mathe

1. #include <gmpxx.h>
   
2. #include <time.h>
   
3. #include <stdio.h>
   
4. #include <omp.h>
   
5. 
   
6. #define FM 15
   
7. #define TC 2
   
8. #define TRANGE 10000000
   
9. #define BLOCKSIZE 200000
   
10. char isp[TRANGE];
    
11. char bsize[BLOCKSIZE];
    
12. 
    
13. void initp()
    
14. {
    
15.         int i;
    
16.         for(i=2;i<TRANGE;i++)isp[i]=1;
    
17.         for(i=2;i<=TRANGE/i;i++){
    
18.                 if(isp[i]){
    
19.                         int j;
    
20.                         for(j=i*i;j<TRANGE;j+=i)isp[j]=0;
    
21.                 }
    
22.         }
    
23. }
    
24. 
    
25. int pow2n(int n, int p)
    
26. {
    
27.         long r=1,m=2;
    
28.         int i;
    
29.         while(n>0){
    
30.                 if(n&1){
    
31.                         r*=m;
    
32.                         r%=p;
    
33.                 }
    
34.                 m*=m;
    
35.                 m%=p;
    
36.                 n>>=1;
    
37.         }
    
38.         return (int)r;
    
39. }
    
40. 
    
41. void init()
    
42. {
    
43.         int i,p;
    
44.         int n=1<<FM;
    
45.         initp();
    
46.         for(i=1;i<BLOCKSIZE;i++)bsize[i]=1;
    
47.         for(p=2;p<TRANGE;p++){
    
48.                 if(!isp[p])continue;
    
49.                 int r=pow2n(n,p);
    
50.                 for(i=p-r;i<BLOCKSIZE;i+=p){
    
51.                         bsize[i]=0;
    
52.                 }
    
53.         }
    
54.         int c=0;
    
55.         for(i=1;i<BLOCKSIZE;i++){
    
56.                 if(bsize[i])c++;
    
57.         }
    
58.         printf("Total %d cands left\n",c);
    
59. }
    
60. 
    
61. int gc;
    
62. int main()
    
63. {
    
64.         int i;
    
65.         time_t start = time(NULL);
    
66.         init();
    
67.         printf("Init done\n");fflush(stdout);
    
68.         mpz_class x=1;
    
69.         x<<=1<<FM; //2^(2^FM)
    
70. #pragma omp parallel for
    
71.         for(i=1;i<BLOCKSIZE;i++){
    
72.                 if(!bsize[i])continue;
    
73.                 mpz_class y=x+i;
    
74.                 gc++;
    
75.                 if(mpz_probab_prime_p(y.get_mpz_t(),TC)){
    
76.                         printf("M%d+%d\n",FM,i-1);
    
77.                         fflush(stdout);
    
78.                         fprintf(stderr,"M%d+%d found\n",FM,i-1);
    
79.                 }
    
80. #if 0
    
81.                 if(gc%7==0){
    
82.                         int diff = time(NULL)-start;
    
83.                         fprintf(stderr,"test %d cost %ds\n",gc,diff);
    
84.                 }
    
85. #endif
    
86.         }
    
87.         return 0;
    
88. }
    

复制代码

nyy

今天争取搞出F16后面的第一个素数！仅仅只是争取，也许间距很大，但是争取搞出来！
8:29开始找，但是到现在还没找到。

nyy

F16后面的两个素数：由于两个素数靠得比较近，所以我就一起贴上来。
(2^(2^16)+1)+44060
(2^(2^16)+1)+44180
找到9:23终于找到一个，耗时54分钟！

nyy

F16前的第一个素数是
(2^(2^16)+1)-5628