素数分解

medie2005

呵呵，我不懂汇编。

刚才算了一下，用的是10^8以内的素数表，没有发现满足条件的素数，也就是说，要找的素数起码有12位。

zgg___

弱问一下，条件“b.17个连续素数的和”是不是包含了条件“a.3个连续素数的和”？

如果只是追求：本身为素数，且为连续素数和，这两个条件。那么是比较容易算的。
因为素数是很“密”的，或许比想象的要“密”很多呢。所以随机取一些连续素数求和，蒙上素数的可能性是很大的。
比如说前四百万个素数的和是131463314443633，它恰巧也是素数。

zgg___

哦，现在看懂题目了。呵呵。

无心人

这个没想象中的难，但也不容易
主要是不好找到符合所有条件的

mathe

我觉得可以先将一定范围素数求出来，然后先只使用两个最长连续素数条件去过滤。
比如先求从3开始的连续2007个素数之和。此为序列1
然后找到从某个最小的p使得从p开始的连续979个素数之和不小于上面的和。此为序列2。
然后每次将序列1移动一个素数到一下连续2007个素数和，
  同样，移动序列2若干个素数位置，到达下一个和不小于序列1的情况。
只有在这种移动过程中两个序列和相同的情况我们才需要继续检查是否满足其它的求和条件以及和是否是素数。
而这种情况的概率应该是很小的。由于第一个序列之和应该是比较随机的，我们可以认为是一个随机奇数。
同样找到对应第二个序列时，我们知道对于第二个序列，每次移动改变的值的大小为位置差979的两个素数的差值，大概为979log(p)
所以，能够正好同第一个序列产生结果相同的概率大概在2/(979log(p)),这是一个很小的概率。所以大部分情况我们会发现根本不需要做进一步检测。
当然，我们也可以同样再次比较第三个序列，这样，三个序列和都相同的概率会更加小，但是我们就一直逐步移动三个序列，是否有好处比较难判断。

而在遇上序列和相同的情况后，我们可以:
  i) 判断和是否是素数，可以像medie2005的方法判断是否为伪素数，如果通过继续第二步
ii)对于其余序列，序列长度为H,我们可以得到素数平均大小为sum/H,然后在这个附近找到和最接近sum的长度为H的序列
   这个取决于素数保存格式，如果用比特位，马上可以定位（代价是前面两个序列移动时慢一些）
   如果将所有素数保存在数组中，需要采用二分法。
   如果对于所有序列，都通过，进入第三步
iii)通过对每个不超过$sqrt(sum)$的素数求模验证和是否的确为素数。

无心人

好主意

不过，计算过都重合的概率么
如果太小，比如小于1/10000000000000000
那也是无法找到的

mathe

原帖由 medie2005 于 2008-6-19 15:26 发表
呵呵，我不懂汇编。

刚才算了一下，用的是10^8以内的素数表，没有发现满足条件的素数，也就是说，要找的素数起码有12位。

我计算了一下，0xFFFFFFFF以内都不行

无心人

那可麻烦了
大数运算很慢的

建议使用Cell处理器

mathe

Gxqcn帮忙看看，下面这个代码运行到一定时候就好像出错了

1. 
   
2. #define MAX_N  203280220
   
3. unsigned int plist[MAX_N];
   
4. 
   
5. int search_match_prime(unsigned value)
   
6. {
   
7.     int start=0,mid,end=MAX_N-1;
   
8.     mid=(start+end)/2;
   
9.     while(end-start>=2){
   
10.         if(plist[mid]<value){
    
11.             start=mid;
    
12.         }else{
    
13.             end=mid;
    
14.         }
    
15.         mid=(start+end)/2;
    
16.     }
    
17.     return mid;
    
18. }
    
19. 
    
20. bool is_list(int num, unsigned long long sum)
    
21. {
    
22.     unsigned long long aver=sum/num;
    
23.     if(aver>=0xFFFFFFFFLL)aver=0xFFFFFFFF;
    
24.     integer start(aver),end,sump(0);
    
25.     start.NextPrime(start);
    
26.     int prevc,nextc;
    
27.     prevc=num/2;
    
28.     nextc=num-1-prevc;
    
29.     int i;
    
30.     sump=end=start;
    
31.     for(i=0;i<nextc;i++){
    
32.         integer tmp(end);
    
33.         end.NextPrime(tmp);
    
34.         sump+=end;
    
35.     }
    
36.     for(i=0;i<prevc;i++){
    
37.         integer tmp(start);
    
38.         start.PreviousPrime(tmp);
    
39.         sump+=start;
    
40.     }
    
41.     if(sump<integer(sum)){
    
42.         while(sump<integer(sum)){
    
43.             integer newp;
    
44.             newp.NextPrime(end);
    
45.             sump+=newp-start;
    
46.             integer tmp(start);
    
47.             start.NextPrime(tmp);
    
48.             end=newp;
    
49.         }
    
50.     }else{
    
51.         while(sump>integer(sum)){
    
52.             integer newp;
    
53.             newp.PreviousPrime(start);
    
54.             sump-=end-newp;
    
55.             integer tmp(end);
    
56.             end.PreviousPrime(tmp);
    
57.             start=newp;
    
58.         }
    
59.     }
    
60.     return sump==integer(sum);
    
61. }
    
62. 
    
63. #define MF  2007
    
64. #define MS  979
    
65. 
    
66. void candidate(unsigned long long x, int mF,int mS)
    
67. {
    
68.     integer y((unsigned long long)x);
    
69.     if(!y.IsPrime())
    
70.         return;
    
71.     printf("Cand%lld\n",x);
    
72.     if(!is_list(45,x))
    
73.         return;
    
74.     if(!is_list(17,x))
    
75.         return;
    
76.     if(!is_list(3,x))
    
77.         return;
    
78.     printf("%lld\n",x);
    
79. }
    
80. int main(int argc, char* argv[])
    
81. {
    
82.     int i;
    
83.     long long max_sum=0;
    
84.     long long sumMF=0;
    
85.     long long sumMS=0;
    
86.     int count = HugeCalc::GetPrimeList(plist,MAX_N,3,0xFFFFFFFF);
    
87.     int iMS,iMF;
    
88.     if(count!=MAX_N){
    
89.         fprintf(stderr,"Invalid number of primes\n");
    
90.     }
    
91.     printf("Init finished\n");
    
92.     for(i=0;i<MS;i++){
    
93.         max_sum+=plist[MAX_N-1-i];
    
94.     }
    
95.     for(i=0;i<MS;i++){
    
96.         sumMS+=plist[i];
    
97.     }
    
98.     sumMF=sumMS;
    
99.     for(;i<MF;i++){
    
100.         sumMF+=plist[i];
     
101.     }
     
102.     iMF=0;iMS=0;
     
103.     while(sumMF<=max_sum&&iMF<MAX_N){
     
104.         while(sumMS<sumMF&&iMS<MAX_N){
     
105.             sumMS+=plist[iMS+MS]-plist[iMS];
     
106.             iMS++;
     
107.         }
     
108.         if(sumMS==sumMF){
     
109.             candidate(sumMF,iMF,iMS);
     
110.         }
     
111.         sumMF+=plist[iMF+MF]-plist[iMF];
     
112.         iMF++;
     
113.     }
     
114.     return 0;
     
115. }
     

复制代码

无心人

是不是存在内存漏洞？

另外，GxQ是否考虑做一个定长整数的库阿？
比如分别处理64位，128位，256位整数

以防止为大数的额外处理来浪费小数运算的时间
我想某些运算，如果仅考虑小数，能有50％的性能提升呢