数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 算法交流 › 被连续自然数取模后全为质数的最小整数 ...
123
返回列表 发新帖
楼主: wayne

[讨论] 被连续自然数取模后全为质数的最小整数

[复制链接]
mathe
发表于 2020-8-8 16:59:38 | 显示全部楼层
139 (1m30s)
4188696294935413706934768125377042512002
140(1m37s)
4188696294935413706934768125377042512002
141(1m36s)
4188696294935413706934768125377042512002
142(23s)
71375535419096138855747944430720887776002
143(23s)
71375535419096138855747944430720887776002
144(25s)
71375535419096138855747944430720887776002
145(26s)
71375535419096138855747944430720887776002
146(0.6s)
71375535419096138855747944430720887776002
147(0.6s)
71375535419096138855747944430720887776002
148(0.6s)
71375535419096138855747944430720887776002
149(0.6s)
71375535419096138855747944430720887776002
150(0.6s)
71375535419096138855747944430720887776002
151(2m24s)
28466105341303483745606123156025578668368002
152(2m19s)
28466105341303483745606123156025578668368002
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2020-8-8 17:20:22 | 显示全部楼层
153~156
28466105341303483745606123156025578668368002
157
81849859751405924059843476855289279826496002
158~162
746294017377509464097706103446488143037568002
163~165
33635406647457932883180477167488271261164992002
166
154918018148228242519886464835636651505317472002
167~168
299084197184085790849033982186295000595719696002
169~172
3531371825353917671492584999407565716875889792002
173
116810701936766586361368933161051719437728630688002

点评

mathe
笔记本还是强劲的  发表于 2020-8-9 11:53
.·.·.
242~250：1439011990188211741334841754244394476887612560371605459101394720656002  发表于 2020-8-9 09:49
.·.·.
准确地说242需要的是时间……我给你的242是n<242的情况，对n=242..250，只能用时间慢慢熬。用的内存并不多，真正找到n=242只需要10G内存……但需要把全部10G数据的循环节重复两万多次（PS.我也是笔记本）  发表于 2020-8-9 09:47
mathe
赞，算242需要用多大的内存？我现在在173左右基本上卡住了，笔记本内存比较小。  发表于 2020-8-9 05:54
.·.·.
242:4828299556190106737188708726420164405880642740182586600077808144002  发表于 2020-8-9 02:54
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

.·.·.
发表于 2020-8-9 00:52:56 | 显示全部楼层
本帖最后由 .·.·. 于 2020-8-9 09:48 编辑
mathe 发表于 2020-8-8 17:20
153~156
28466105341303483745606123156025578668368002
157
rayon.7z (10.27 KB, 下载次数: 0)
  1. 00:46:49> g=(a,b,c)->d=a*2^128+b*2^64+c;for(i=3,900,if(!isprime(d%i),print(i);break));d
  2. %21 = (a,b,c)->d=a*2^128+b*2^64+c;for(i=3,900,if(!isprime(d%i),print(i);break));d
  3. 00:47:01> g(1040147161867, 7560342529706118980, 11446842006473251970)
  4. 179
  5. %22 = 353943738186338730051340043852386052151622936272002
  6. 00:47:03> g(343275800605, 11767202774273793771, 15199516501634173186)
  7. 178
  8. %23 = 116810701936766586361368933161051719437728630688002
  9. (BigUInt=g)
  10. 01:40:11> BigUInt(336184657781948, 13060152521397031879, 17401726287141301250)
  11. 193
  12. %57 = 114397711072547200623926739913773332504663121492864002
  13. 01:40:22> BigUInt(76640775490436, 17224944753369267051, 5535650887625968770)
  14. 191
  15. %58 = 26079504486542128214527139484976208504732884352208002
  16. 01:40:27> BigUInt(21921671246381, 11662777460910458884, 7012004375286606722)
  17. 181
  18. %59 = 7459558178581420991908368303782280420035186413104002
  19. (194:)655569072883475643276379698332630870445125049195696002(code is incorrect thus do not generate the BigUInt form.)
  20. 01:40:35> BigUInt(21550470068748838, 14667185391198351420, 18069870029154129154)
  21. 197
  22. %60 = 7333244963252694316979523001920058246398799258689312002
  23. 01:43:43> BigUInt(49238389357311262, 5374406407451916197, 11540656834366258178)
  24. 199
  25. %61 = 16754955673880622369079802324257242816195831706070400002
  26. 01:48:23> BigUInt(3649368858081476934, 14762377635946019554, 17114688005815144834)
  27. 206
  28. %68 = 1241815872795527340920909004524886711949273374627222000002
  29. 02:23:53> BigU256=(a,b,c,d)->e=a*2^192+b*2^128+c*2^64+d;for(i=3,900,if(!isprime(e%i),print(i);break));e
  30. %102 = (a,b,c,d)->e=a*2^192+b*2^128+c*2^64+d;for(i=3,900,if(!isprime(e%i),print(i);break));e
  31. 02:24:15> BigU256(11, 9338117007605686109, 5914508867865278435, 9449427700573572482)
  32. 211
  33. %103 = 72225715647186222395152227158525640349057726424522471280002
  34. 02:24:25> BigU256(13, 11922583201728322026, 11442997097915309871, 16504593912194840962)
  35. 214
  36. %104 = 85659367391722784092607464197468049651961443566063782640002
  37. 02:24:34> BigU256(5045, 14915641366288941122, 12556338656733202238, 1357278714895837442)
  38. 218
  39. %105 = 31673053784774069114917859005213870009008990233082429871008002
  40. 02:32:50> BigU256(105642, 4594879267310787348, 12542645452379590053, 6593728445292498434)
  41. 223
  42. %107 = 663127145086112525715369034835863236326107289562909156940992002
  43. 02:33:13> BigU256(324382, 16707202402379446201, 2441149314094187990, 17344994933329711234)
  44. 226
  45. %108 = 2036184500294580388401873354629853515994924364902165172748112002
  46. 02:35:06> BigU256(29594670, 3914874787019208054, 5083363177805329805, 9126329000077058178)
  47. 233
  48. %111 = 185768755747358998327069097333443876936859437235420585132525904002
  49. 02:38:55> BigU256(769192496, 13818213026569080142, 10363200697496292489, 12843986744144596610)
  50. 242
  51. %115 = 4828299556190106737188708726420164405880642740182586600077808144002
  52. 09:38:56> BigU256(229247836159, 2678296511289632618, 6941544924194096003, 919448886373386882)
  53. 251
  54. %2 = 1439011990188211741334841754244394476887612560371605459101394720656002
复制代码

(Pinyin IME is broken.. cannot type Pinyin, sorry..)
$ rustc main.rs -O && time ./main
i=87,len=12,rep=BigUInt(33, 17315042437149894138, 5041259723618722944)
i=88,len=12,rep=BigUInt(33, 17315042437149894138, 5041259723618722944)
i=89,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=90,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=91,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=92,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=93,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=94,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=95,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=96,len=276,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=97,len=6624,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=98,len=6624,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=99,len=6624,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=100,len=6624,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=101,len=165600,rep=BigUInt(29592229, 3677664573221068002, 2962757942317257344)
i=102,len=165600,rep=BigUInt(29592229, 3677664573221068002, 2962757942317257344)
i=103,len=4305600,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=104,len=4305600,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=105,len=4305600,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=106,len=4305600,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=107,len=116251200,rep=BigUInt(326135958006, 4044531529505551460, 1818271812586827904)
break at i=107,TO=108
SHOULD check `TO` and `i` carefully!
loop0 finished
found number= BigUInt(343275800605, 11767202774273793771, 15199516501634173186) for n<178!
loop1 finished
loop2 finished
found number= BigUInt(1040147161867, 7560342529706118980, 11446842006473251970) for n<179!

real    0m20.571s
user    0m20.024s
sys     0m0.546s
  1. #![feature(const_int_pow)]
  2. /*
  3. LENGTH=500
  4. a=[True]*(LENGTH+1)
  5. a[0]=a[1]=False
  6. for i in range(2,LENGTH+1):
  7.   if a[i]:
  8.     for j in range(2,(LENGTH//i)+1):
  9.       a[i*j]=False

  11. print(("const ISPRIME:[bool;%d]= "%(LENGTH+1))+str(a).lower().replace(" ","")+";")
  12. [n for n,b in enumerate(a) if b]
  13. aa=[a for a in a]
  14. for i in [n for n,b in enumerate(a) if b]:
  15.   j=i*i;
  16.   while j<=LENGTH:
  17.     aa[j]=True
  18.     j*=i

  20. for i in range(1,200):
  21.     aa[i]=True

  23. #for u32
  24. print("\n".join(["N=>(self.5%N+N1*(self.4%N)+N2*(self.3%N)+N3*(self.2%N)+N4*(self.1%N)+N5*(self.0%N))%N,".replace("N5",str(2**(32*5)%n)).replace("N4",str(2**(32*4)%n)).replace("N3",str(2**(32*3)%n)).replace("N2",str(2**(32*2)%n)).replace("N1",str(2**32%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
  25. #for u64 array
  26. print("\n".join(["            N=>(N2*((self.0)[0]%N)+N1*((self.0)[1]%N)+(self.0)[2]%N)%N,".replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
  27. #for u64
  28. print("\n".join(["            N=>(N2*(self.0%N)+N1*(self.1%N)+self.2%N)%N,".replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
  29. print("\n".join(["            N=>(N3*(self.0%N)+N2*(self.1%N)+N1*(self.2%N)+self.3%N)%N,".replace("N3",str(2**(64*3)%n)).replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))

  31. */
  32. const ISPRIME:[bool;501]= [false,false,true,true,false,true,false,true,false,false,false,true,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,true,false];
  33. const UPPER:u32=173;
  34. const HALF:u32=(UPPER>>1)+1;
  35. const TO:u32=108;
  36. fn main(){
  37.     let mut lcm=BigUInt(0,0,2);
  38.     for i in 3..HALF{
  39.         lcm=lcm.mul((i/gcd(i,lcm)) as u128)
  40.     }
  41.     let mut x=(vec![BigUInt(0,0,2)],lcm);
  42.     //x=search_roll(x.0,81,x.1);//3
  43.     //x=search_roll(x.0,49,x.1);//7
  44.     x=search_roll(x.0,121,x.1);//11
  45.     x=search_roll(x.0,125,x.1);//2
  46.     x=search_roll(x.0,128,x.1);//5
  47.     x=search_roll(x.0,169,x.1);//13
  48.     //x=search_roll(x.0,243,x.1);//3
  49.     //x=search_roll(x.0,289,x.1);//17
  50.     //x=search_roll(x.0,343,x.1);//7
  51.     for i in HALF..=TO{
  52.         x=search_roll(x.0,i,x.1);
  53.         println!("i={},len={},rep={:?}",i,(x.0).len(),x.1);
  54.         if (x.0).len()>10000000{println!("break at i={},TO={}",i,TO);break}
  55.     }
  56.     println!("SHOULD check `TO` and `i` carefully!");
  57.     let (mut b,lcm)=x;
  58.     b.sort_unstable();
  59.     let mut upper=search_once(&b,167);
  60.     for i in 0..3{
  61.         println!("loop{} finished",i);
  62.         b.iter_mut().for_each(|x|*x=x.add(lcm));
  63.         upper=search_once(&b,upper);
  64.     }
  65. }
  66. #[derive(Clone,Copy,Debug,Ord,Eq,PartialEq,PartialOrd)]
  67. struct BigUInt(u64,u64,u64);
  68. impl BigUInt{
  69.     #[inline]
  70.     pub fn add(self,other:Self)->Self{
  71.         //self+other
  72.         let l0=self.2 as u128  + other.2 as u128;
  73.         let (l0,g)=(l0 as u64,l0>>64);
  74.         let l1=self.1 as u128+g+other.1 as u128;
  75.         let (l1,g)=(l1 as u64,l1>>64);
  76.         BigUInt(self.0+g as u64+other.0 as u64,l1,l0)
  77.     }
  78.     #[inline]
  79.     pub fn expand(self,other:Self,b:u128)->Self{
  80.         //self+other*b
  81.         let l0=self.2 as u128  +(other.2 as u128)*b;
  82.         let (l0,g)=(l0 as u64,l0>>64);
  83.         let l1=self.1 as u128+g+(other.1 as u128)*b;
  84.         let (l1,g)=(l1 as u64,l1>>64);
  85.         BigUInt(self.0+g as u64+other.0*b as u64,l1,l0)
  86.     }
  87.     #[inline]
  88.     pub fn mul(self,b:u128)->Self{
  89.         //self*b
  90.         let l0=  (self.2 as u128)*b;
  91.         let (l0,g)=(l0 as u64,l0>>64);
  92.         let l1=g+(self.1 as u128)*b;
  93.         let (l1,g)=(l1 as u64,l1>>64);
  94.         BigUInt(g as u64+self.0*b as u64,l1,l0)
  95.     }
  96.     #[inline]
  97.     pub fn rem(self,b:u32)->usize{//match(x){...N=>t%N,...}is much faster than t%x if N is a constant.
  98.         (match b{
  99.             1=>0,
  100.             2=>(0*(self.0%2)+0*(self.1%2)+self.2%2)%2,
  101.             3=>(1*(self.0%3)+1*(self.1%3)+self.2%3)%3,
  102.             4=>(0*(self.0%4)+0*(self.1%4)+self.2%4)%4,
  103.             5=>(1*(self.0%5)+1*(self.1%5)+self.2%5)%5,
  104.             6=>(4*(self.0%6)+4*(self.1%6)+self.2%6)%6,
  105.             7=>(4*(self.0%7)+2*(self.1%7)+self.2%7)%7,
  106.             8=>(0*(self.0%8)+0*(self.1%8)+self.2%8)%8,
  107.             9=>(4*(self.0%9)+7*(self.1%9)+self.2%9)%9,
  108.             10=>(6*(self.0%10)+6*(self.1%10)+self.2%10)%10,
  109.             11=>(3*(self.0%11)+5*(self.1%11)+self.2%11)%11,
  110.             12=>(4*(self.0%12)+4*(self.1%12)+self.2%12)%12,
  111.             13=>(9*(self.0%13)+3*(self.1%13)+self.2%13)%13,
  112.             14=>(4*(self.0%14)+2*(self.1%14)+self.2%14)%14,
  113.             15=>(1*(self.0%15)+1*(self.1%15)+self.2%15)%15,
  114.             16=>(0*(self.0%16)+0*(self.1%16)+self.2%16)%16,
  115.             17=>(1*(self.0%17)+1*(self.1%17)+self.2%17)%17,
  116.             18=>(4*(self.0%18)+16*(self.1%18)+self.2%18)%18,
  117.             19=>(4*(self.0%19)+17*(self.1%19)+self.2%19)%19,
  118.             20=>(16*(self.0%20)+16*(self.1%20)+self.2%20)%20,
  119.             21=>(4*(self.0%21)+16*(self.1%21)+self.2%21)%21,
  120.             22=>(14*(self.0%22)+16*(self.1%22)+self.2%22)%22,
  121.             23=>(13*(self.0%23)+6*(self.1%23)+self.2%23)%23,
  122.             24=>(16*(self.0%24)+16*(self.1%24)+self.2%24)%24,
  123.             25=>(6*(self.0%25)+16*(self.1%25)+self.2%25)%25,
  124.             26=>(22*(self.0%26)+16*(self.1%26)+self.2%26)%26,
  125.             27=>(4*(self.0%27)+25*(self.1%27)+self.2%27)%27,
  126.             28=>(4*(self.0%28)+16*(self.1%28)+self.2%28)%28,
  127.             29=>(25*(self.0%29)+24*(self.1%29)+self.2%29)%29,
  128.             30=>(16*(self.0%30)+16*(self.1%30)+self.2%30)%30,
  129.             31=>(8*(self.0%31)+16*(self.1%31)+self.2%31)%31,
  130.             32=>(0*(self.0%32)+0*(self.1%32)+self.2%32)%32,
  131.             33=>(25*(self.0%33)+16*(self.1%33)+self.2%33)%33,
  132.             34=>(18*(self.0%34)+18*(self.1%34)+self.2%34)%34,
  133.             35=>(11*(self.0%35)+16*(self.1%35)+self.2%35)%35,
  134.             36=>(4*(self.0%36)+16*(self.1%36)+self.2%36)%36,
  135.             37=>(33*(self.0%37)+12*(self.1%37)+self.2%37)%37,
  136.             38=>(4*(self.0%38)+36*(self.1%38)+self.2%38)%38,
  137.             39=>(22*(self.0%39)+16*(self.1%39)+self.2%39)%39,
  138.             40=>(16*(self.0%40)+16*(self.1%40)+self.2%40)%40,
  139.             41=>(10*(self.0%41)+16*(self.1%41)+self.2%41)%41,
  140.             42=>(4*(self.0%42)+16*(self.1%42)+self.2%42)%42,
  141.             43=>(4*(self.0%43)+41*(self.1%43)+self.2%43)%43,
  142.             44=>(36*(self.0%44)+16*(self.1%44)+self.2%44)%44,
  143.             45=>(31*(self.0%45)+16*(self.1%45)+self.2%45)%45,
  144.             46=>(36*(self.0%46)+6*(self.1%46)+self.2%46)%46,
  145.             47=>(14*(self.0%47)+25*(self.1%47)+self.2%47)%47,
  146.             48=>(16*(self.0%48)+16*(self.1%48)+self.2%48)%48,
  147.             49=>(4*(self.0%49)+2*(self.1%49)+self.2%49)%49,
  148.             50=>(6*(self.0%50)+16*(self.1%50)+self.2%50)%50,
  149.             51=>(1*(self.0%51)+1*(self.1%51)+self.2%51)%51,
  150.             52=>(48*(self.0%52)+16*(self.1%52)+self.2%52)%52,
  151.             53=>(13*(self.0%53)+15*(self.1%53)+self.2%53)%53,
  152.             54=>(4*(self.0%54)+52*(self.1%54)+self.2%54)%54,
  153.             55=>(36*(self.0%55)+16*(self.1%55)+self.2%55)%55,
  154.             56=>(32*(self.0%56)+16*(self.1%56)+self.2%56)%56,
  155.             57=>(4*(self.0%57)+55*(self.1%57)+self.2%57)%57,
  156.             58=>(54*(self.0%58)+24*(self.1%58)+self.2%58)%58,
  157.             59=>(25*(self.0%59)+5*(self.1%59)+self.2%59)%59,
  158.             60=>(16*(self.0%60)+16*(self.1%60)+self.2%60)%60,
  159.             61=>(12*(self.0%61)+16*(self.1%61)+self.2%61)%61,
  160.             62=>(8*(self.0%62)+16*(self.1%62)+self.2%62)%62,
  161.             63=>(4*(self.0%63)+16*(self.1%63)+self.2%63)%63,
  162.             64=>(0*(self.0%64)+0*(self.1%64)+self.2%64)%64,
  163.             65=>(61*(self.0%65)+16*(self.1%65)+self.2%65)%65,
  164.             66=>(58*(self.0%66)+16*(self.1%66)+self.2%66)%66,
  165.             67=>(21*(self.0%67)+17*(self.1%67)+self.2%67)%67,
  166.             68=>(52*(self.0%68)+52*(self.1%68)+self.2%68)%68,
  167.             69=>(13*(self.0%69)+52*(self.1%69)+self.2%69)%69,
  168.             70=>(46*(self.0%70)+16*(self.1%70)+self.2%70)%70,
  169.             71=>(29*(self.0%71)+10*(self.1%71)+self.2%71)%71,
  170.             72=>(40*(self.0%72)+16*(self.1%72)+self.2%72)%72,
  171.             73=>(4*(self.0%73)+2*(self.1%73)+self.2%73)%73,
  172.             74=>(70*(self.0%74)+12*(self.1%74)+self.2%74)%74,
  173.             75=>(31*(self.0%75)+16*(self.1%75)+self.2%75)%75,
  174.             76=>(4*(self.0%76)+36*(self.1%76)+self.2%76)%76,
  175.             77=>(25*(self.0%77)+16*(self.1%77)+self.2%77)%77,
  176.             78=>(22*(self.0%78)+16*(self.1%78)+self.2%78)%78,
  177.             79=>(73*(self.0%79)+51*(self.1%79)+self.2%79)%79,
  178.             80=>(16*(self.0%80)+16*(self.1%80)+self.2%80)%80,
  179.             81=>(31*(self.0%81)+52*(self.1%81)+self.2%81)%81,
  180.             82=>(10*(self.0%82)+16*(self.1%82)+self.2%82)%82,
  181.             83=>(51*(self.0%83)+36*(self.1%83)+self.2%83)%83,
  182.             84=>(4*(self.0%84)+16*(self.1%84)+self.2%84)%84,
  183.             85=>(1*(self.0%85)+1*(self.1%85)+self.2%85)%85,
  184.             86=>(4*(self.0%86)+84*(self.1%86)+self.2%86)%86,
  185.             87=>(25*(self.0%87)+82*(self.1%87)+self.2%87)%87,
  186.             88=>(80*(self.0%88)+16*(self.1%88)+self.2%88)%88,
  187.             89=>(39*(self.0%89)+67*(self.1%89)+self.2%89)%89,
  188.             90=>(76*(self.0%90)+16*(self.1%90)+self.2%90)%90,
  189.             91=>(74*(self.0%91)+16*(self.1%91)+self.2%91)%91,
  190.             92=>(36*(self.0%92)+52*(self.1%92)+self.2%92)%92,
  191.             93=>(70*(self.0%93)+16*(self.1%93)+self.2%93)%93,
  192.             94=>(14*(self.0%94)+72*(self.1%94)+self.2%94)%94,
  193.             95=>(61*(self.0%95)+36*(self.1%95)+self.2%95)%95,
  194.             96=>(64*(self.0%96)+64*(self.1%96)+self.2%96)%96,
  195.             97=>(35*(self.0%97)+61*(self.1%97)+self.2%97)%97,
  196.             98=>(4*(self.0%98)+2*(self.1%98)+self.2%98)%98,
  197.             99=>(58*(self.0%99)+16*(self.1%99)+self.2%99)%99,
  198.             100=>(56*(self.0%100)+16*(self.1%100)+self.2%100)%100,
  199.             101=>(80*(self.0%101)+79*(self.1%101)+self.2%101)%101,
  200.             102=>(52*(self.0%102)+52*(self.1%102)+self.2%102)%102,
  201.             103=>(38*(self.0%103)+55*(self.1%103)+self.2%103)%103,
  202.             104=>(48*(self.0%104)+16*(self.1%104)+self.2%104)%104,
  203.             105=>(46*(self.0%105)+16*(self.1%105)+self.2%105)%105,
  204.             106=>(66*(self.0%106)+68*(self.1%106)+self.2%106)%106,
  205.             107=>(11*(self.0%107)+92*(self.1%107)+self.2%107)%107,
  206.             108=>(4*(self.0%108)+52*(self.1%108)+self.2%108)%108,
  207.             109=>(105*(self.0%109)+66*(self.1%109)+self.2%109)%109,
  208.             110=>(36*(self.0%110)+16*(self.1%110)+self.2%110)%110,
  209.             111=>(70*(self.0%111)+49*(self.1%111)+self.2%111)%111,
  210.             112=>(32*(self.0%112)+16*(self.1%112)+self.2%112)%112,
  211.             113=>(109*(self.0%113)+30*(self.1%113)+self.2%113)%113,
  212.             114=>(4*(self.0%114)+112*(self.1%114)+self.2%114)%114,
  213.             115=>(36*(self.0%115)+6*(self.1%115)+self.2%115)%115,
  214.             116=>(112*(self.0%116)+24*(self.1%116)+self.2%116)%116,
  215.             117=>(22*(self.0%117)+16*(self.1%117)+self.2%117)%117,
  216.             118=>(84*(self.0%118)+64*(self.1%118)+self.2%118)%118,
  217.             119=>(18*(self.0%119)+86*(self.1%119)+self.2%119)%119,
  218.             120=>(16*(self.0%120)+16*(self.1%120)+self.2%120)%120,
  219.             121=>(58*(self.0%121)+93*(self.1%121)+self.2%121)%121,
  220.             122=>(12*(self.0%122)+16*(self.1%122)+self.2%122)%122,
  221.             123=>(10*(self.0%123)+16*(self.1%123)+self.2%123)%123,
  222.             124=>(8*(self.0%124)+16*(self.1%124)+self.2%124)%124,
  223.             125=>(81*(self.0%125)+116*(self.1%125)+self.2%125)%125,
  224.             126=>(4*(self.0%126)+16*(self.1%126)+self.2%126)%126,
  225.             127=>(4*(self.0%127)+2*(self.1%127)+self.2%127)%127,
  226.             128=>(0*(self.0%128)+0*(self.1%128)+self.2%128)%128,
  227.             129=>(4*(self.0%129)+127*(self.1%129)+self.2%129)%129,
  228.             130=>(126*(self.0%130)+16*(self.1%130)+self.2%130)%130,
  229.             131=>(33*(self.0%131)+65*(self.1%131)+self.2%131)%131,
  230.             132=>(124*(self.0%132)+16*(self.1%132)+self.2%132)%132,
  231.             133=>(4*(self.0%133)+93*(self.1%133)+self.2%133)%133,
  232.             134=>(88*(self.0%134)+84*(self.1%134)+self.2%134)%134,
  233.             135=>(31*(self.0%135)+106*(self.1%135)+self.2%135)%135,
  234.             136=>(120*(self.0%136)+120*(self.1%136)+self.2%136)%136,
  235.             137=>(38*(self.0%137)+60*(self.1%137)+self.2%137)%137,
  236.             138=>(82*(self.0%138)+52*(self.1%138)+self.2%138)%138,
  237.             139=>(30*(self.0%139)+13*(self.1%139)+self.2%139)%139,
  238.             140=>(116*(self.0%140)+16*(self.1%140)+self.2%140)%140,
  239.             141=>(61*(self.0%141)+25*(self.1%141)+self.2%141)%141,
  240.             142=>(100*(self.0%142)+10*(self.1%142)+self.2%142)%142,
  241.             143=>(113*(self.0%143)+16*(self.1%143)+self.2%143)%143,
  242.             144=>(112*(self.0%144)+16*(self.1%144)+self.2%144)%144,
  243.             145=>(141*(self.0%145)+111*(self.1%145)+self.2%145)%145,
  244.             146=>(4*(self.0%146)+2*(self.1%146)+self.2%146)%146,
  245.             147=>(4*(self.0%147)+100*(self.1%147)+self.2%147)%147,
  246.             148=>(144*(self.0%148)+12*(self.1%148)+self.2%148)%148,
  247.             149=>(123*(self.0%149)+102*(self.1%149)+self.2%149)%149,
  248.             150=>(106*(self.0%150)+16*(self.1%150)+self.2%150)%150,
  249.             151=>(105*(self.0%151)+16*(self.1%151)+self.2%151)%151,
  250.             152=>(80*(self.0%152)+112*(self.1%152)+self.2%152)%152,
  251.             153=>(103*(self.0%153)+52*(self.1%153)+self.2%153)%153,
  252.             154=>(102*(self.0%154)+16*(self.1%154)+self.2%154)%154,
  253.             155=>(101*(self.0%155)+16*(self.1%155)+self.2%155)%155,
  254.             156=>(100*(self.0%156)+16*(self.1%156)+self.2%156)%156,
  255.             157=>(39*(self.0%157)+14*(self.1%157)+self.2%157)%157,
  256.             158=>(152*(self.0%158)+130*(self.1%158)+self.2%158)%158,
  257.             159=>(13*(self.0%159)+121*(self.1%159)+self.2%159)%159,
  258.             160=>(96*(self.0%160)+96*(self.1%160)+self.2%160)%160,
  259.             161=>(151*(self.0%161)+121*(self.1%161)+self.2%161)%161,
  260.             162=>(112*(self.0%162)+52*(self.1%162)+self.2%162)%162,
  261.             163=>(152*(self.0%163)+57*(self.1%163)+self.2%163)%163,
  262.             164=>(92*(self.0%164)+16*(self.1%164)+self.2%164)%164,
  263.             165=>(91*(self.0%165)+16*(self.1%165)+self.2%165)%165,
  264.             166=>(134*(self.0%166)+36*(self.1%166)+self.2%166)%166,
  265.             167=>(63*(self.0%167)+49*(self.1%167)+self.2%167)%167,
  266.             168=>(88*(self.0%168)+16*(self.1%168)+self.2%168)%168,
  267.             169=>(48*(self.0%169)+94*(self.1%169)+self.2%169)%169,
  268.             170=>(86*(self.0%170)+86*(self.1%170)+self.2%170)%170,
  269.             171=>(4*(self.0%171)+169*(self.1%171)+self.2%171)%171,
  270.             172=>(4*(self.0%172)+84*(self.1%172)+self.2%172)%172,
  271.             173=>(133*(self.0%173)+47*(self.1%173)+self.2%173)%173,
  272.             174=>(112*(self.0%174)+82*(self.1%174)+self.2%174)%174,
  273.             175=>(81*(self.0%175)+16*(self.1%175)+self.2%175)%175,
  274.             176=>(80*(self.0%176)+16*(self.1%176)+self.2%176)%176,
  275.             177=>(25*(self.0%177)+64*(self.1%177)+self.2%177)%177,
  276.             178=>(128*(self.0%178)+156*(self.1%178)+self.2%178)%178,
  277.             179=>(161*(self.0%179)+124*(self.1%179)+self.2%179)%179,
  278.             180=>(76*(self.0%180)+16*(self.1%180)+self.2%180)%180,
  279.             181=>(126*(self.0%181)+44*(self.1%181)+self.2%181)%181,
  280.             182=>(74*(self.0%182)+16*(self.1%182)+self.2%182)%182,
  281.             183=>(73*(self.0%183)+16*(self.1%183)+self.2%183)%183,
  282.             184=>(128*(self.0%184)+144*(self.1%184)+self.2%184)%184,
  283.             185=>(181*(self.0%185)+86*(self.1%185)+self.2%185)%185,
  284.             186=>(70*(self.0%186)+16*(self.1%186)+self.2%186)%186,
  285.             187=>(69*(self.0%187)+137*(self.1%187)+self.2%187)%187,
  286.             188=>(108*(self.0%188)+72*(self.1%188)+self.2%188)%188,
  287.             189=>(4*(self.0%189)+79*(self.1%189)+self.2%189)%189,
  288.             190=>(156*(self.0%190)+36*(self.1%190)+self.2%190)%190,
  289.             191=>(103*(self.0%191)+26*(self.1%191)+self.2%191)%191,
  290.             192=>(64*(self.0%192)+64*(self.1%192)+self.2%192)%192,
  291.             193=>(108*(self.0%193)+84*(self.1%193)+self.2%193)%193,
  292.             194=>(132*(self.0%194)+158*(self.1%194)+self.2%194)%194,
  293.             195=>(61*(self.0%195)+16*(self.1%195)+self.2%195)%195,
  294.             196=>(4*(self.0%196)+100*(self.1%196)+self.2%196)%196,
  295.             197=>(175*(self.0%197)+61*(self.1%197)+self.2%197)%197,
  296.             198=>(58*(self.0%198)+16*(self.1%198)+self.2%198)%198,
  297.             199=>(155*(self.0%199)+126*(self.1%199)+self.2%199)%199,
  298.             211=>(119*(self.0%211)+69*(self.1%211)+self.2%211)%211,
  299.             223=>(171*(self.0%223)+49*(self.1%223)+self.2%223)%223,
  300.             227=>(147*(self.0%227)+104*(self.1%227)+self.2%227)%227,
  301.             229=>(104*(self.0%229)+44*(self.1%229)+self.2%229)%229,
  302.             233=>(135*(self.0%233)+64*(self.1%233)+self.2%233)%233,
  303.             239=>(34*(self.0%239)+150*(self.1%239)+self.2%239)%239,
  304.             241=>(15*(self.0%241)+225*(self.1%241)+self.2%241)%241,
  305.             243=>(193*(self.0%243)+133*(self.1%243)+self.2%243)%243,
  306.             251=>(243*(self.0%251)+69*(self.1%251)+self.2%251)%251,
  307.             256=>(0*(self.0%256)+0*(self.1%256)+self.2%256)%256,
  308.             257=>(1*(self.0%257)+1*(self.1%257)+self.2%257)%257,
  309.             263=>(33*(self.0%263)+104*(self.1%263)+self.2%263)%263,
  310.             269=>(21*(self.0%269)+57*(self.1%269)+self.2%269)%269,
  311.             271=>(36*(self.0%271)+265*(self.1%271)+self.2%271)%271,
  312.             277=>(155*(self.0%277)+175*(self.1%277)+self.2%277)%277,
  313.             281=>(85*(self.0%281)+101*(self.1%281)+self.2%281)%281,
  314.             283=>(151*(self.0%283)+240*(self.1%283)+self.2%283)%283,
  315.             289=>(35*(self.0%289)+18*(self.1%289)+self.2%289)%289,
  316.             293=>(161*(self.0%293)+109*(self.1%293)+self.2%293)%293,
  317.             307=>(199*(self.0%307)+97*(self.1%307)+self.2%307)%307,
  318.             311=>(35*(self.0%311)+208*(self.1%311)+self.2%311)%311,
  319.             313=>(132*(self.0%313)+142*(self.1%313)+self.2%313)%313,
  320.             317=>(235*(self.0%317)+251*(self.1%317)+self.2%317)%317,
  321.             331=>(256*(self.0%331)+16*(self.1%331)+self.2%331)%331,
  322.             337=>(4*(self.0%337)+2*(self.1%337)+self.2%337)%337,
  323.             343=>(151*(self.0%343)+296*(self.1%343)+self.2%343)%343,
  324.             347=>(129*(self.0%347)+167*(self.1%347)+self.2%347)%347,
  325.             349=>(148*(self.0%349)+219*(self.1%349)+self.2%349)%349,
  326.             353=>(22*(self.0%353)+187*(self.1%353)+self.2%353)%353,
  327.             359=>(264*(self.0%359)+303*(self.1%359)+self.2%359)%359,
  328.             361=>(156*(self.0%361)+321*(self.1%361)+self.2%361)%361,
  329.             367=>(129*(self.0%367)+297*(self.1%367)+self.2%367)%367,
  330.             373=>(68*(self.0%373)+21*(self.1%373)+self.2%373)%373,
  331.             379=>(171*(self.0%379)+277*(self.1%379)+self.2%379)%379,
  332.             383=>(150*(self.0%383)+143*(self.1%383)+self.2%383)%383,
  333.             389=>(164*(self.0%389)+169*(self.1%389)+self.2%389)%389,
  334.             397=>(273*(self.0%397)+99*(self.1%397)+self.2%397)%397,
  335.             401=>(360*(self.0%401)+63*(self.1%401)+self.2%401)%401,
  336.             409=>(265*(self.0%409)+80*(self.1%409)+self.2%409)%409,
  337.             419=>(100*(self.0%419)+409*(self.1%419)+self.2%419)%419,
  338.             421=>(255*(self.0%421)+26*(self.1%421)+self.2%421)%421,
  339.             431=>(216*(self.0%431)+337*(self.1%431)+self.2%431)%431,
  340.             433=>(150*(self.0%433)+296*(self.1%433)+self.2%433)%433,
  341.             439=>(36*(self.0%439)+433*(self.1%439)+self.2%439)%439,
  342.             443=>(153*(self.0%443)+215*(self.1%443)+self.2%443)%443,
  343.             449=>(18*(self.0%449)+359*(self.1%449)+self.2%449)%449,
  344.             457=>(68*(self.0%457)+215*(self.1%457)+self.2%457)%457,
  345.             461=>(444*(self.0%461)+370*(self.1%461)+self.2%461)%461,
  346.             463=>(60*(self.0%463)+261*(self.1%463)+self.2%463)%463,
  347.             467=>(264*(self.0%467)+369*(self.1%467)+self.2%467)%467,
  348.             479=>(28*(self.0%479)+403*(self.1%479)+self.2%479)%479,
  349.             487=>(467*(self.0%487)+286*(self.1%487)+self.2%487)%487,
  350.             491=>(429*(self.0%491)+263*(self.1%491)+self.2%491)%491,
  351.             499=>(462*(self.0%499)+31*(self.1%499)+self.2%499)%499,
  352.             _=>2
  353.         }) as usize
  354.     }
  355. }
  356. type BIG=BigUInt;
  357. #[inline]
  358. fn gcd(i:u32,j:BIG)->u32{//ensure i<j for better performance
  359.     let (mut i,mut j)=(j.rem(i as u32) as u32,i);
  360.     while i != 0{
  361.         let t=j%i;
  362.         j=i;
  363.         i=t;
  364.     }
  365.     j
  366. }
  367. fn search_roll(b:Vec<BIG>,ix:u32,mut repeats:BIG)->(Vec<BIG>,BIG){
  368.     let i=ix/gcd(ix,repeats);
  369.     let b=if i>1{b.into_iter().map(|x|(0..i).map(|c|x.expand(repeats,c as u128)).filter(|x|ISPRIME[x.rem(ix)]).collect::<Vec<_>>()).flatten().collect::<Vec<_>>()}else{b};
  370.     if i>1 {repeats=repeats.mul(i as u128)}
  371.     (b,repeats)
  372. }
  373. fn search_once(b:&[BIG],mut upper:u32)->u32{
  374.     let mut c=b.into_iter();
  375.     c.next();
  376.     let mut gg=vec![109,113,127,131,137,139,149,151,157,163,167];
  377.     let mut rem=vec![173,178,179,181,191,193,194,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293];
  378.     let mut h=rem.drain(..);
  379.     while let Some(hh)=h.next(){
  380.         gg.push(hh);
  381.         if hh>=upper{break}
  382.     }
  383.     for i in c{
  384.         while gg.iter().copied().all(|t|ISPRIME[i.rem(t)]){
  385.             upper=h.next().unwrap();
  386.             println!("found number= {:?} for n<{}!",i,upper);
  387.             gg.push(upper);
  388.         }
  389.     }
  390.     upper
  391. }
复制代码

tuneing const
  1. #![feature(const_int_pow)]
  2. /*
  3. LENGTH=500
  4. a=[True]*(LENGTH+1)
  5. a[0]=a[1]=False
  6. for i in range(2,LENGTH+1):
  7.   if a[i]:
  8.     for j in range(2,(LENGTH//i)+1):
  9.       a[i*j]=False

  11. print(("const ISPRIME:[bool;%d]= "%(LENGTH+1))+str(a).lower().replace(" ","")+";")
  12. [n for n,b in enumerate(a) if b]
  13. aa=[a for a in a]
  14. for i in [n for n,b in enumerate(a) if b]:
  15.   j=i*i;
  16.   while j<=LENGTH:
  17.     aa[j]=True
  18.     j*=i

  20. for i in range(1,200):
  21.     aa[i]=True

  23. #for u32
  24. print("\n".join(["N=>(self.5%N+N1*(self.4%N)+N2*(self.3%N)+N3*(self.2%N)+N4*(self.1%N)+N5*(self.0%N))%N,".replace("N5",str(2**(32*5)%n)).replace("N4",str(2**(32*4)%n)).replace("N3",str(2**(32*3)%n)).replace("N2",str(2**(32*2)%n)).replace("N1",str(2**32%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
  25. #for u64 array
  26. print("\n".join(["            N=>(N2*((self.0)[0]%N)+N1*((self.0)[1]%N)+(self.0)[2]%N)%N,".replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
  27. #for u64
  28. print("\n".join(["            N=>(N2*(self.0%N)+N1*(self.1%N)+self.2%N)%N,".replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
  29. print("\n".join(["            N=>(N3*(self.0%N)+N2*(self.1%N)+N1*(self.2%N)+self.3%N)%N,".replace("N3",str(2**(64*3)%n)).replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))

  31. */
  32. const ISPRIME:[bool;501]= [false,false,true,true,false,true,false,true,false,false,false,true,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,true,false];
  33. const UPPER:u32=180;
  34. const HALF:u32=(UPPER>>1)+1;
  35. const TO:u32=109;
  36. fn main(){
  37.     let mut lcm=BigUInt(0,0,2);
  38.     for i in 3..HALF{
  39.         lcm=lcm.mul((i/gcd(i,lcm)) as u128)
  40.     }
  41.     let mut x=(vec![BigUInt(0,0,2)],lcm);
  42.     //x=search_roll(x.0,81,x.1);//3
  43.     //x=search_roll(x.0,49,x.1);//7
  44.     x=search_roll(x.0,121,x.1);//11
  45.     x=search_roll(x.0,125,x.1);//2
  46.     x=search_roll(x.0,128,x.1);//5
  47.     x=search_roll(x.0,169,x.1);//13
  48.     //x=search_roll(x.0,243,x.1);//3
  49.     //x=search_roll(x.0,289,x.1);//17
  50.     //x=search_roll(x.0,343,x.1);//7
  51.     for i in HALF..=TO{
  52.         x=search_roll(x.0,i,x.1);
  53.         println!("i={},len={},rep={:?}",i,(x.0).len(),x.1);
  54.         if (x.0).len()>10000000{println!("break at i={},TO={}",i,TO);break}
  55.     }
  56.     println!("SHOULD check `TO` and `i` carefully!");
  57.     let (mut b,lcm)=x;
  58.     b.sort_unstable();
  59.     let mut upper=search_once(&b,179);
  60.     for i in 0..10{
  61.         println!("loop{} finished",i);
  62.         b.iter_mut().for_each(|x|*x=x.add(lcm));
  63.         upper=search_once(&b,upper);
  64.     }
  65. }
  66. #[derive(Clone,Copy,Debug,Ord,Eq,PartialEq,PartialOrd)]
  67. struct BigUInt(u64,u64,u64);
  68. impl BigUInt{
  69.     #[inline]
  70.     pub fn add(self,other:Self)->Self{
  71.         //self+other
  72.         let l0=self.2 as u128  + other.2 as u128;
  73.         let (l0,g)=(l0 as u64,l0>>64);
  74.         let l1=self.1 as u128+g+other.1 as u128;
  75.         let (l1,g)=(l1 as u64,l1>>64);
  76.         BigUInt(self.0+g as u64+other.0 as u64,l1,l0)
  77.     }
  78.     #[inline]
  79.     pub fn expand(self,other:Self,b:u128)->Self{
  80.         //self+other*b
  81.         let l0=self.2 as u128  +(other.2 as u128)*b;
  82.         let (l0,g)=(l0 as u64,l0>>64);
  83.         let l1=self.1 as u128+g+(other.1 as u128)*b;
  84.         let (l1,g)=(l1 as u64,l1>>64);
  85.         BigUInt(self.0+g as u64+other.0*b as u64,l1,l0)
  86.     }
  87.     #[inline]
  88.     pub fn mul(self,b:u128)->Self{
  89.         //self*b
  90.         let l0=  (self.2 as u128)*b;
  91.         let (l0,g)=(l0 as u64,l0>>64);
  92.         let l1=g+(self.1 as u128)*b;
  93.         let (l1,g)=(l1 as u64,l1>>64);
  94.         BigUInt(g as u64+self.0*b as u64,l1,l0)
  95.     }
  96.     #[inline]
  97.     pub fn rem(self,b:u32)->usize{
  98.         (match b{
  99.             1=>0,
  100.             2=>(0*(self.0%2)+0*(self.1%2)+self.2%2)%2,
  101.             3=>(1*(self.0%3)+1*(self.1%3)+self.2%3)%3,
  102.             4=>(0*(self.0%4)+0*(self.1%4)+self.2%4)%4,
  103.             5=>(1*(self.0%5)+1*(self.1%5)+self.2%5)%5,
  104.             6=>(4*(self.0%6)+4*(self.1%6)+self.2%6)%6,
  105.             7=>(4*(self.0%7)+2*(self.1%7)+self.2%7)%7,
  106.             8=>(0*(self.0%8)+0*(self.1%8)+self.2%8)%8,
  107.             9=>(4*(self.0%9)+7*(self.1%9)+self.2%9)%9,
  108.             10=>(6*(self.0%10)+6*(self.1%10)+self.2%10)%10,
  109.             11=>(3*(self.0%11)+5*(self.1%11)+self.2%11)%11,
  110.             12=>(4*(self.0%12)+4*(self.1%12)+self.2%12)%12,
  111.             13=>(9*(self.0%13)+3*(self.1%13)+self.2%13)%13,
  112.             14=>(4*(self.0%14)+2*(self.1%14)+self.2%14)%14,
  113.             15=>(1*(self.0%15)+1*(self.1%15)+self.2%15)%15,
  114.             16=>(0*(self.0%16)+0*(self.1%16)+self.2%16)%16,
  115.             17=>(1*(self.0%17)+1*(self.1%17)+self.2%17)%17,
  116.             18=>(4*(self.0%18)+16*(self.1%18)+self.2%18)%18,
  117.             19=>(4*(self.0%19)+17*(self.1%19)+self.2%19)%19,
  118.             20=>(16*(self.0%20)+16*(self.1%20)+self.2%20)%20,
  119.             21=>(4*(self.0%21)+16*(self.1%21)+self.2%21)%21,
  120.             22=>(14*(self.0%22)+16*(self.1%22)+self.2%22)%22,
  121.             23=>(13*(self.0%23)+6*(self.1%23)+self.2%23)%23,
  122.             24=>(16*(self.0%24)+16*(self.1%24)+self.2%24)%24,
  123.             25=>(6*(self.0%25)+16*(self.1%25)+self.2%25)%25,
  124.             26=>(22*(self.0%26)+16*(self.1%26)+self.2%26)%26,
  125.             27=>(4*(self.0%27)+25*(self.1%27)+self.2%27)%27,
  126.             28=>(4*(self.0%28)+16*(self.1%28)+self.2%28)%28,
  127.             29=>(25*(self.0%29)+24*(self.1%29)+self.2%29)%29,
  128.             30=>(16*(self.0%30)+16*(self.1%30)+self.2%30)%30,
  129.             31=>(8*(self.0%31)+16*(self.1%31)+self.2%31)%31,
  130.             32=>(0*(self.0%32)+0*(self.1%32)+self.2%32)%32,
  131.             33=>(25*(self.0%33)+16*(self.1%33)+self.2%33)%33,
  132.             34=>(18*(self.0%34)+18*(self.1%34)+self.2%34)%34,
  133.             35=>(11*(self.0%35)+16*(self.1%35)+self.2%35)%35,
  134.             36=>(4*(self.0%36)+16*(self.1%36)+self.2%36)%36,
  135.             37=>(33*(self.0%37)+12*(self.1%37)+self.2%37)%37,
  136.             38=>(4*(self.0%38)+36*(self.1%38)+self.2%38)%38,
  137.             39=>(22*(self.0%39)+16*(self.1%39)+self.2%39)%39,
  138.             40=>(16*(self.0%40)+16*(self.1%40)+self.2%40)%40,
  139.             41=>(10*(self.0%41)+16*(self.1%41)+self.2%41)%41,
  140.             42=>(4*(self.0%42)+16*(self.1%42)+self.2%42)%42,
  141.             43=>(4*(self.0%43)+41*(self.1%43)+self.2%43)%43,
  142.             44=>(36*(self.0%44)+16*(self.1%44)+self.2%44)%44,
  143.             45=>(31*(self.0%45)+16*(self.1%45)+self.2%45)%45,
  144.             46=>(36*(self.0%46)+6*(self.1%46)+self.2%46)%46,
  145.             47=>(14*(self.0%47)+25*(self.1%47)+self.2%47)%47,
  146.             48=>(16*(self.0%48)+16*(self.1%48)+self.2%48)%48,
  147.             49=>(4*(self.0%49)+2*(self.1%49)+self.2%49)%49,
  148.             50=>(6*(self.0%50)+16*(self.1%50)+self.2%50)%50,
  149.             51=>(1*(self.0%51)+1*(self.1%51)+self.2%51)%51,
  150.             52=>(48*(self.0%52)+16*(self.1%52)+self.2%52)%52,
  151.             53=>(13*(self.0%53)+15*(self.1%53)+self.2%53)%53,
  152.             54=>(4*(self.0%54)+52*(self.1%54)+self.2%54)%54,
  153.             55=>(36*(self.0%55)+16*(self.1%55)+self.2%55)%55,
  154.             56=>(32*(self.0%56)+16*(self.1%56)+self.2%56)%56,
  155.             57=>(4*(self.0%57)+55*(self.1%57)+self.2%57)%57,
  156.             58=>(54*(self.0%58)+24*(self.1%58)+self.2%58)%58,
  157.             59=>(25*(self.0%59)+5*(self.1%59)+self.2%59)%59,
  158.             60=>(16*(self.0%60)+16*(self.1%60)+self.2%60)%60,
  159.             61=>(12*(self.0%61)+16*(self.1%61)+self.2%61)%61,
  160.             62=>(8*(self.0%62)+16*(self.1%62)+self.2%62)%62,
  161.             63=>(4*(self.0%63)+16*(self.1%63)+self.2%63)%63,
  162.             64=>(0*(self.0%64)+0*(self.1%64)+self.2%64)%64,
  163.             65=>(61*(self.0%65)+16*(self.1%65)+self.2%65)%65,
  164.             66=>(58*(self.0%66)+16*(self.1%66)+self.2%66)%66,
  165.             67=>(21*(self.0%67)+17*(self.1%67)+self.2%67)%67,
  166.             68=>(52*(self.0%68)+52*(self.1%68)+self.2%68)%68,
  167.             69=>(13*(self.0%69)+52*(self.1%69)+self.2%69)%69,
  168.             70=>(46*(self.0%70)+16*(self.1%70)+self.2%70)%70,
  169.             71=>(29*(self.0%71)+10*(self.1%71)+self.2%71)%71,
  170.             72=>(40*(self.0%72)+16*(self.1%72)+self.2%72)%72,
  171.             73=>(4*(self.0%73)+2*(self.1%73)+self.2%73)%73,
  172.             74=>(70*(self.0%74)+12*(self.1%74)+self.2%74)%74,
  173.             75=>(31*(self.0%75)+16*(self.1%75)+self.2%75)%75,
  174.             76=>(4*(self.0%76)+36*(self.1%76)+self.2%76)%76,
  175.             77=>(25*(self.0%77)+16*(self.1%77)+self.2%77)%77,
  176.             78=>(22*(self.0%78)+16*(self.1%78)+self.2%78)%78,
  177.             79=>(73*(self.0%79)+51*(self.1%79)+self.2%79)%79,
  178.             80=>(16*(self.0%80)+16*(self.1%80)+self.2%80)%80,
  179.             81=>(31*(self.0%81)+52*(self.1%81)+self.2%81)%81,
  180.             82=>(10*(self.0%82)+16*(self.1%82)+self.2%82)%82,
  181.             83=>(51*(self.0%83)+36*(self.1%83)+self.2%83)%83,
  182.             84=>(4*(self.0%84)+16*(self.1%84)+self.2%84)%84,
  183.             85=>(1*(self.0%85)+1*(self.1%85)+self.2%85)%85,
  184.             86=>(4*(self.0%86)+84*(self.1%86)+self.2%86)%86,
  185.             87=>(25*(self.0%87)+82*(self.1%87)+self.2%87)%87,
  186.             88=>(80*(self.0%88)+16*(self.1%88)+self.2%88)%88,
  187.             89=>(39*(self.0%89)+67*(self.1%89)+self.2%89)%89,
  188.             90=>(76*(self.0%90)+16*(self.1%90)+self.2%90)%90,
  189.             91=>(74*(self.0%91)+16*(self.1%91)+self.2%91)%91,
  190.             92=>(36*(self.0%92)+52*(self.1%92)+self.2%92)%92,
  191.             93=>(70*(self.0%93)+16*(self.1%93)+self.2%93)%93,
  192.             94=>(14*(self.0%94)+72*(self.1%94)+self.2%94)%94,
  193.             95=>(61*(self.0%95)+36*(self.1%95)+self.2%95)%95,
  194.             96=>(64*(self.0%96)+64*(self.1%96)+self.2%96)%96,
  195.             97=>(35*(self.0%97)+61*(self.1%97)+self.2%97)%97,
  196.             98=>(4*(self.0%98)+2*(self.1%98)+self.2%98)%98,
  197.             99=>(58*(self.0%99)+16*(self.1%99)+self.2%99)%99,
  198.             100=>(56*(self.0%100)+16*(self.1%100)+self.2%100)%100,
  199.             101=>(80*(self.0%101)+79*(self.1%101)+self.2%101)%101,
  200.             102=>(52*(self.0%102)+52*(self.1%102)+self.2%102)%102,
  201.             103=>(38*(self.0%103)+55*(self.1%103)+self.2%103)%103,
  202.             104=>(48*(self.0%104)+16*(self.1%104)+self.2%104)%104,
  203.             105=>(46*(self.0%105)+16*(self.1%105)+self.2%105)%105,
  204.             106=>(66*(self.0%106)+68*(self.1%106)+self.2%106)%106,
  205.             107=>(11*(self.0%107)+92*(self.1%107)+self.2%107)%107,
  206.             108=>(4*(self.0%108)+52*(self.1%108)+self.2%108)%108,
  207.             109=>(105*(self.0%109)+66*(self.1%109)+self.2%109)%109,
  208.             110=>(36*(self.0%110)+16*(self.1%110)+self.2%110)%110,
  209.             111=>(70*(self.0%111)+49*(self.1%111)+self.2%111)%111,
  210.             112=>(32*(self.0%112)+16*(self.1%112)+self.2%112)%112,
  211.             113=>(109*(self.0%113)+30*(self.1%113)+self.2%113)%113,
  212.             114=>(4*(self.0%114)+112*(self.1%114)+self.2%114)%114,
  213.             115=>(36*(self.0%115)+6*(self.1%115)+self.2%115)%115,
  214.             116=>(112*(self.0%116)+24*(self.1%116)+self.2%116)%116,
  215.             117=>(22*(self.0%117)+16*(self.1%117)+self.2%117)%117,
  216.             118=>(84*(self.0%118)+64*(self.1%118)+self.2%118)%118,
  217.             119=>(18*(self.0%119)+86*(self.1%119)+self.2%119)%119,
  218.             120=>(16*(self.0%120)+16*(self.1%120)+self.2%120)%120,
  219.             121=>(58*(self.0%121)+93*(self.1%121)+self.2%121)%121,
  220.             122=>(12*(self.0%122)+16*(self.1%122)+self.2%122)%122,
  221.             123=>(10*(self.0%123)+16*(self.1%123)+self.2%123)%123,
  222.             124=>(8*(self.0%124)+16*(self.1%124)+self.2%124)%124,
  223.             125=>(81*(self.0%125)+116*(self.1%125)+self.2%125)%125,
  224.             126=>(4*(self.0%126)+16*(self.1%126)+self.2%126)%126,
  225.             127=>(4*(self.0%127)+2*(self.1%127)+self.2%127)%127,
  226.             128=>(0*(self.0%128)+0*(self.1%128)+self.2%128)%128,
  227.             129=>(4*(self.0%129)+127*(self.1%129)+self.2%129)%129,
  228.             130=>(126*(self.0%130)+16*(self.1%130)+self.2%130)%130,
  229.             131=>(33*(self.0%131)+65*(self.1%131)+self.2%131)%131,
  230.             132=>(124*(self.0%132)+16*(self.1%132)+self.2%132)%132,
  231.             133=>(4*(self.0%133)+93*(self.1%133)+self.2%133)%133,
  232.             134=>(88*(self.0%134)+84*(self.1%134)+self.2%134)%134,
  233.             135=>(31*(self.0%135)+106*(self.1%135)+self.2%135)%135,
  234.             136=>(120*(self.0%136)+120*(self.1%136)+self.2%136)%136,
  235.             137=>(38*(self.0%137)+60*(self.1%137)+self.2%137)%137,
  236.             138=>(82*(self.0%138)+52*(self.1%138)+self.2%138)%138,
  237.             139=>(30*(self.0%139)+13*(self.1%139)+self.2%139)%139,
  238.             140=>(116*(self.0%140)+16*(self.1%140)+self.2%140)%140,
  239.             141=>(61*(self.0%141)+25*(self.1%141)+self.2%141)%141,
  240.             142=>(100*(self.0%142)+10*(self.1%142)+self.2%142)%142,
  241.             143=>(113*(self.0%143)+16*(self.1%143)+self.2%143)%143,
  242.             144=>(112*(self.0%144)+16*(self.1%144)+self.2%144)%144,
  243.             145=>(141*(self.0%145)+111*(self.1%145)+self.2%145)%145,
  244.             146=>(4*(self.0%146)+2*(self.1%146)+self.2%146)%146,
  245.             147=>(4*(self.0%147)+100*(self.1%147)+self.2%147)%147,
  246.             148=>(144*(self.0%148)+12*(self.1%148)+self.2%148)%148,
  247.             149=>(123*(self.0%149)+102*(self.1%149)+self.2%149)%149,
  248.             150=>(106*(self.0%150)+16*(self.1%150)+self.2%150)%150,
  249.             151=>(105*(self.0%151)+16*(self.1%151)+self.2%151)%151,
  250.             152=>(80*(self.0%152)+112*(self.1%152)+self.2%152)%152,
  251.             153=>(103*(self.0%153)+52*(self.1%153)+self.2%153)%153,
  252.             154=>(102*(self.0%154)+16*(self.1%154)+self.2%154)%154,
  253.             155=>(101*(self.0%155)+16*(self.1%155)+self.2%155)%155,
  254.             156=>(100*(self.0%156)+16*(self.1%156)+self.2%156)%156,
  255.             157=>(39*(self.0%157)+14*(self.1%157)+self.2%157)%157,
  256.             158=>(152*(self.0%158)+130*(self.1%158)+self.2%158)%158,
  257.             159=>(13*(self.0%159)+121*(self.1%159)+self.2%159)%159,
  258.             160=>(96*(self.0%160)+96*(self.1%160)+self.2%160)%160,
  259.             161=>(151*(self.0%161)+121*(self.1%161)+self.2%161)%161,
  260.             162=>(112*(self.0%162)+52*(self.1%162)+self.2%162)%162,
  261.             163=>(152*(self.0%163)+57*(self.1%163)+self.2%163)%163,
  262.             164=>(92*(self.0%164)+16*(self.1%164)+self.2%164)%164,
  263.             165=>(91*(self.0%165)+16*(self.1%165)+self.2%165)%165,
  264.             166=>(134*(self.0%166)+36*(self.1%166)+self.2%166)%166,
  265.             167=>(63*(self.0%167)+49*(self.1%167)+self.2%167)%167,
  266.             168=>(88*(self.0%168)+16*(self.1%168)+self.2%168)%168,
  267.             169=>(48*(self.0%169)+94*(self.1%169)+self.2%169)%169,
  268.             170=>(86*(self.0%170)+86*(self.1%170)+self.2%170)%170,
  269.             171=>(4*(self.0%171)+169*(self.1%171)+self.2%171)%171,
  270.             172=>(4*(self.0%172)+84*(self.1%172)+self.2%172)%172,
  271.             173=>(133*(self.0%173)+47*(self.1%173)+self.2%173)%173,
  272.             174=>(112*(self.0%174)+82*(self.1%174)+self.2%174)%174,
  273.             175=>(81*(self.0%175)+16*(self.1%175)+self.2%175)%175,
  274.             176=>(80*(self.0%176)+16*(self.1%176)+self.2%176)%176,
  275.             177=>(25*(self.0%177)+64*(self.1%177)+self.2%177)%177,
  276.             178=>(128*(self.0%178)+156*(self.1%178)+self.2%178)%178,
  277.             179=>(161*(self.0%179)+124*(self.1%179)+self.2%179)%179,
  278.             180=>(76*(self.0%180)+16*(self.1%180)+self.2%180)%180,
  279.             181=>(126*(self.0%181)+44*(self.1%181)+self.2%181)%181,
  280.             182=>(74*(self.0%182)+16*(self.1%182)+self.2%182)%182,
  281.             183=>(73*(self.0%183)+16*(self.1%183)+self.2%183)%183,
  282.             184=>(128*(self.0%184)+144*(self.1%184)+self.2%184)%184,
  283.             185=>(181*(self.0%185)+86*(self.1%185)+self.2%185)%185,
  284.             186=>(70*(self.0%186)+16*(self.1%186)+self.2%186)%186,
  285.             187=>(69*(self.0%187)+137*(self.1%187)+self.2%187)%187,
  286.             188=>(108*(self.0%188)+72*(self.1%188)+self.2%188)%188,
  287.             189=>(4*(self.0%189)+79*(self.1%189)+self.2%189)%189,
  288.             190=>(156*(self.0%190)+36*(self.1%190)+self.2%190)%190,
  289.             191=>(103*(self.0%191)+26*(self.1%191)+self.2%191)%191,
  290.             192=>(64*(self.0%192)+64*(self.1%192)+self.2%192)%192,
  291.             193=>(108*(self.0%193)+84*(self.1%193)+self.2%193)%193,
  292.             194=>(132*(self.0%194)+158*(self.1%194)+self.2%194)%194,
  293.             195=>(61*(self.0%195)+16*(self.1%195)+self.2%195)%195,
  294.             196=>(4*(self.0%196)+100*(self.1%196)+self.2%196)%196,
  295.             197=>(175*(self.0%197)+61*(self.1%197)+self.2%197)%197,
  296.             198=>(58*(self.0%198)+16*(self.1%198)+self.2%198)%198,
  297.             199=>(155*(self.0%199)+126*(self.1%199)+self.2%199)%199,
  298.             211=>(119*(self.0%211)+69*(self.1%211)+self.2%211)%211,
  299.             223=>(171*(self.0%223)+49*(self.1%223)+self.2%223)%223,
  300.             227=>(147*(self.0%227)+104*(self.1%227)+self.2%227)%227,
  301.             229=>(104*(self.0%229)+44*(self.1%229)+self.2%229)%229,
  302.             233=>(135*(self.0%233)+64*(self.1%233)+self.2%233)%233,
  303.             239=>(34*(self.0%239)+150*(self.1%239)+self.2%239)%239,
  304.             241=>(15*(self.0%241)+225*(self.1%241)+self.2%241)%241,
  305.             243=>(193*(self.0%243)+133*(self.1%243)+self.2%243)%243,
  306.             251=>(243*(self.0%251)+69*(self.1%251)+self.2%251)%251,
  307.             256=>(0*(self.0%256)+0*(self.1%256)+self.2%256)%256,
  308.             257=>(1*(self.0%257)+1*(self.1%257)+self.2%257)%257,
  309.             263=>(33*(self.0%263)+104*(self.1%263)+self.2%263)%263,
  310.             269=>(21*(self.0%269)+57*(self.1%269)+self.2%269)%269,
  311.             271=>(36*(self.0%271)+265*(self.1%271)+self.2%271)%271,
  312.             277=>(155*(self.0%277)+175*(self.1%277)+self.2%277)%277,
  313.             281=>(85*(self.0%281)+101*(self.1%281)+self.2%281)%281,
  314.             283=>(151*(self.0%283)+240*(self.1%283)+self.2%283)%283,
  315.             289=>(35*(self.0%289)+18*(self.1%289)+self.2%289)%289,
  316.             293=>(161*(self.0%293)+109*(self.1%293)+self.2%293)%293,
  317.             307=>(199*(self.0%307)+97*(self.1%307)+self.2%307)%307,
  318.             311=>(35*(self.0%311)+208*(self.1%311)+self.2%311)%311,
  319.             313=>(132*(self.0%313)+142*(self.1%313)+self.2%313)%313,
  320.             317=>(235*(self.0%317)+251*(self.1%317)+self.2%317)%317,
  321.             331=>(256*(self.0%331)+16*(self.1%331)+self.2%331)%331,
  322.             337=>(4*(self.0%337)+2*(self.1%337)+self.2%337)%337,
  323.             343=>(151*(self.0%343)+296*(self.1%343)+self.2%343)%343,
  324.             347=>(129*(self.0%347)+167*(self.1%347)+self.2%347)%347,
  325.             349=>(148*(self.0%349)+219*(self.1%349)+self.2%349)%349,
  326.             353=>(22*(self.0%353)+187*(self.1%353)+self.2%353)%353,
  327.             359=>(264*(self.0%359)+303*(self.1%359)+self.2%359)%359,
  328.             361=>(156*(self.0%361)+321*(self.1%361)+self.2%361)%361,
  329.             367=>(129*(self.0%367)+297*(self.1%367)+self.2%367)%367,
  330.             373=>(68*(self.0%373)+21*(self.1%373)+self.2%373)%373,
  331.             379=>(171*(self.0%379)+277*(self.1%379)+self.2%379)%379,
  332.             383=>(150*(self.0%383)+143*(self.1%383)+self.2%383)%383,
  333.             389=>(164*(self.0%389)+169*(self.1%389)+self.2%389)%389,
  334.             397=>(273*(self.0%397)+99*(self.1%397)+self.2%397)%397,
  335.             401=>(360*(self.0%401)+63*(self.1%401)+self.2%401)%401,
  336.             409=>(265*(self.0%409)+80*(self.1%409)+self.2%409)%409,
  337.             419=>(100*(self.0%419)+409*(self.1%419)+self.2%419)%419,
  338.             421=>(255*(self.0%421)+26*(self.1%421)+self.2%421)%421,
  339.             431=>(216*(self.0%431)+337*(self.1%431)+self.2%431)%431,
  340.             433=>(150*(self.0%433)+296*(self.1%433)+self.2%433)%433,
  341.             439=>(36*(self.0%439)+433*(self.1%439)+self.2%439)%439,
  342.             443=>(153*(self.0%443)+215*(self.1%443)+self.2%443)%443,
  343.             449=>(18*(self.0%449)+359*(self.1%449)+self.2%449)%449,
  344.             457=>(68*(self.0%457)+215*(self.1%457)+self.2%457)%457,
  345.             461=>(444*(self.0%461)+370*(self.1%461)+self.2%461)%461,
  346.             463=>(60*(self.0%463)+261*(self.1%463)+self.2%463)%463,
  347.             467=>(264*(self.0%467)+369*(self.1%467)+self.2%467)%467,
  348.             479=>(28*(self.0%479)+403*(self.1%479)+self.2%479)%479,
  349.             487=>(467*(self.0%487)+286*(self.1%487)+self.2%487)%487,
  350.             491=>(429*(self.0%491)+263*(self.1%491)+self.2%491)%491,
  351.             499=>(462*(self.0%499)+31*(self.1%499)+self.2%499)%499,
  352.             _=>2
  353.         }) as usize
  354.     }
  355. }
  356. type BIG=BigUInt;
  357. #[inline]
  358. fn gcd(i:u32,j:BIG)->u32{//ensure i<j for better performance
  359.     let (mut i,mut j)=(j.rem(i as u32) as u32,i);
  360.     while i != 0{
  361.         let t=j%i;
  362.         j=i;
  363.         i=t;
  364.     }
  365.     j
  366. }
  367. fn search_roll(b:Vec<BIG>,ix:u32,mut repeats:BIG)->(Vec<BIG>,BIG){
  368.     let i=ix/gcd(ix,repeats);
  369.     let b=if i>1{b.into_iter().map(|x|(0..i).map(|c|x.expand(repeats,c as u128)).filter(|x|ISPRIME[x.rem(ix)]).collect::<Vec<_>>()).flatten().collect::<Vec<_>>()}else{b};
  370.     if i>1 {repeats=repeats.mul(i as u128)}
  371.     (b,repeats)
  372. }
  373. fn search_once(b:&[BIG],mut upper:u32)->u32{
  374.     let mut c=b.into_iter();
  375.     c.next();
  376.     let mut gg=vec![113,127,131,137,139,149,151,157,163,167];
  377.     let mut rem=vec![173,178,179,181,191,193,194,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293];
  378.     let mut h=rem.drain(..);
  379.     while let Some(hh)=h.next(){
  380.         gg.push(hh);
  381.         if hh>=upper{break}
  382.     }
  383.     for i in c{
  384.         while gg.iter().copied().all(|t|ISPRIME[i.rem(t)]){
  385.             upper=h.next().unwrap();
  386.             println!("found number= {:?} for n<{}!",i,upper);
  387.             gg.push(upper);
  388.         }
  389.     }
  390.     upper
  391. }

复制代码


i=91,len=12,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=92,len=12,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=93,len=12,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=94,len=12,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=95,len=12,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=96,len=12,rep=BigUInt(3020, 9959018788447794178, 5950257633037103232)
i=97,len=288,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=98,len=288,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=99,len=288,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=100,len=288,rep=BigUInt(292992, 6794130646539351265, 5325924119602913408)
i=101,len=7200,rep=BigUInt(29592229, 3677664573221068002, 2962757942317257344)
i=102,len=7200,rep=BigUInt(29592229, 3677664573221068002, 2962757942317257344)
i=103,len=187200,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=104,len=187200,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=105,len=187200,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=106,len=187200,rep=BigUInt(3047999607, 9864569567578971902, 10016162879324680576)
i=107,len=5054400,rep=BigUInt(326135958006, 4044531529505551460, 1818271812586827904)
i=108,len=5054400,rep=BigUInt(326135958006, 4044531529505551460, 1818271812586827904)
i=109,len=141523200,rep=BigUInt(35548819422677, 16578823020785421982, 13724186834868725376)
break at i=109,TO=109
SHOULD check `TO` and `i` carefully!
found number= BigUInt(21921671246381, 11662777460910458884, 7012004375286606722) for n<181!
loop0 finished
loop1 finished
found number= BigUInt(76640775490436, 17224944753369267051, 5535650887625968770) for n<191!
loop2 finished
loop3 finished
loop4 finished
loop5 finished
loop6 finished
loop7 finished
loop8 finished
found number= BigUInt(336184657781948, 13060152521397031879, 17401726287141301250) for n<193!
loop9 finished

real    0m37.568s
user    0m36.894s
sys     0m0.674s

点评

.·.·.
因为算东西没有重启系统，其实只要重启就好了。  发表于 2020-8-9 09:48
wayne
rime pinyin也安装不了吗， ^_^  发表于 2020-8-9 08:51
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

.·.·.
发表于 2020-8-9 01:32:13 | 显示全部楼层
using Rayon to the 194 gap(n%97 thus = 2)
header
  1. /*
  2. LENGTH=500
  3. a=[True]*(LENGTH+1)
  4. a[0]=a[1]=False
  5. for i in range(2,LENGTH+1):
  6.   if a[i]:
  7.     for j in range(2,(LENGTH//i)+1):
  8.       a[i*j]=False

  10. print(("const ISPRIME:[bool;%d]= "%(LENGTH+1))+str(a).lower().replace(" ","")+";")
  11. [n for n,b in enumerate(a) if b]
  12. aa=[a for a in a]
  13. for i in [n for n,b in enumerate(a) if b]:
  14.   j=i*i;
  15.   while j<=LENGTH:
  16.     aa[j]=True
  17.     j*=i

  19. for i in range(1,200):
  20.     aa[i]=True

  22. #for u32
  23. print("\n".join(["N=>(self.5%N+N1*(self.4%N)+N2*(self.3%N)+N3*(self.2%N)+N4*(self.1%N)+N5*(self.0%N))%N,".replace("N5",str(2**(32*5)%n)).replace("N4",str(2**(32*4)%n)).replace("N3",str(2**(32*3)%n)).replace("N2",str(2**(32*2)%n)).replace("N1",str(2**32%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
  24. #for u64 array
  25. print("\n".join(["            N=>(N2*((self.0)[0]%N)+N1*((self.0)[1]%N)+(self.0)[2]%N)%N,".replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
  26. #for u64
  27. print("\n".join(["            N=>(N2*(self.0%N)+N1*(self.1%N)+self.2%N)%N,".replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))
  28. print("\n".join(["            N=>(N3*(self.0%N)+N2*(self.1%N)+N1*(self.2%N)+self.3%N)%N,".replace("N3",str(2**(64*3)%n)).replace("N2",str(2**(64*2)%n)).replace("N1",str(2**64%n)).replace("N",str(n)) for n,b in enumerate(aa) if b]))

  30. */
  31. const ISPRIME:[bool;501]= [false,false,true,true,false,true,false,true,false,false,false,true,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,false,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,true,false];
  32. #[derive(Clone,Copy,Debug,Ord,Eq,PartialEq,PartialOrd)]
  33. struct BigUInt(u64,u64,u64);
  34. impl BigUInt{
  35.     #[inline]
  36.     pub fn add(self,other:Self)->Self{
  37.         //self+other
  38.         let l0=self.2 as u128  + other.2 as u128;
  39.         let (l0,g)=(l0 as u64,l0>>64);
  40.         let l1=self.1 as u128+g+other.1 as u128;
  41.         let (l1,g)=(l1 as u64,l1>>64);
  42.         BigUInt(self.0+g as u64+other.0 as u64,l1,l0)
  43.     }
  44.     #[inline]
  45.     pub fn expand(self,other:Self,b:u128)->Self{
  46.         //self+other*b
  47.         let l0=self.2 as u128  +(other.2 as u128)*b;
  48.         let (l0,g)=(l0 as u64,l0>>64);
  49.         let l1=self.1 as u128+g+(other.1 as u128)*b;
  50.         let (l1,g)=(l1 as u64,l1>>64);
  51.         BigUInt(self.0+g as u64+other.0*b as u64,l1,l0)
  52.     }
  53.     #[inline]
  54.     pub fn mul(self,b:u128)->Self{
  55.         //self*b
  56.         let l0=  (self.2 as u128)*b;
  57.         let (l0,g)=(l0 as u64,l0>>64);
  58.         let l1=g+(self.1 as u128)*b;
  59.         let (l1,g)=(l1 as u64,l1>>64);
  60.         BigUInt(g as u64+self.0*b as u64,l1,l0)
  61.     }
  62.     #[inline]
  63.     pub fn rem(self,b:u32)->usize{
  64.         (match b{
  65.             1=>0,
  66.             2=>(0*(self.0%2)+0*(self.1%2)+self.2%2)%2,
  67.             3=>(1*(self.0%3)+1*(self.1%3)+self.2%3)%3,
  68.             4=>(0*(self.0%4)+0*(self.1%4)+self.2%4)%4,
  69.             5=>(1*(self.0%5)+1*(self.1%5)+self.2%5)%5,
  70.             6=>(4*(self.0%6)+4*(self.1%6)+self.2%6)%6,
  71.             7=>(4*(self.0%7)+2*(self.1%7)+self.2%7)%7,
  72.             8=>(0*(self.0%8)+0*(self.1%8)+self.2%8)%8,
  73.             9=>(4*(self.0%9)+7*(self.1%9)+self.2%9)%9,
  74.             10=>(6*(self.0%10)+6*(self.1%10)+self.2%10)%10,
  75.             11=>(3*(self.0%11)+5*(self.1%11)+self.2%11)%11,
  76.             12=>(4*(self.0%12)+4*(self.1%12)+self.2%12)%12,
  77.             13=>(9*(self.0%13)+3*(self.1%13)+self.2%13)%13,
  78.             14=>(4*(self.0%14)+2*(self.1%14)+self.2%14)%14,
  79.             15=>(1*(self.0%15)+1*(self.1%15)+self.2%15)%15,
  80.             16=>(0*(self.0%16)+0*(self.1%16)+self.2%16)%16,
  81.             17=>(1*(self.0%17)+1*(self.1%17)+self.2%17)%17,
  82.             18=>(4*(self.0%18)+16*(self.1%18)+self.2%18)%18,
  83.             19=>(4*(self.0%19)+17*(self.1%19)+self.2%19)%19,
  84.             20=>(16*(self.0%20)+16*(self.1%20)+self.2%20)%20,
  85.             21=>(4*(self.0%21)+16*(self.1%21)+self.2%21)%21,
  86.             22=>(14*(self.0%22)+16*(self.1%22)+self.2%22)%22,
  87.             23=>(13*(self.0%23)+6*(self.1%23)+self.2%23)%23,
  88.             24=>(16*(self.0%24)+16*(self.1%24)+self.2%24)%24,
  89.             25=>(6*(self.0%25)+16*(self.1%25)+self.2%25)%25,
  90.             26=>(22*(self.0%26)+16*(self.1%26)+self.2%26)%26,
  91.             27=>(4*(self.0%27)+25*(self.1%27)+self.2%27)%27,
  92.             28=>(4*(self.0%28)+16*(self.1%28)+self.2%28)%28,
  93.             29=>(25*(self.0%29)+24*(self.1%29)+self.2%29)%29,
  94.             30=>(16*(self.0%30)+16*(self.1%30)+self.2%30)%30,
  95.             31=>(8*(self.0%31)+16*(self.1%31)+self.2%31)%31,
  96.             32=>(0*(self.0%32)+0*(self.1%32)+self.2%32)%32,
  97.             33=>(25*(self.0%33)+16*(self.1%33)+self.2%33)%33,
  98.             34=>(18*(self.0%34)+18*(self.1%34)+self.2%34)%34,
  99.             35=>(11*(self.0%35)+16*(self.1%35)+self.2%35)%35,
  100.             36=>(4*(self.0%36)+16*(self.1%36)+self.2%36)%36,
  101.             37=>(33*(self.0%37)+12*(self.1%37)+self.2%37)%37,
  102.             38=>(4*(self.0%38)+36*(self.1%38)+self.2%38)%38,
  103.             39=>(22*(self.0%39)+16*(self.1%39)+self.2%39)%39,
  104.             40=>(16*(self.0%40)+16*(self.1%40)+self.2%40)%40,
  105.             41=>(10*(self.0%41)+16*(self.1%41)+self.2%41)%41,
  106.             42=>(4*(self.0%42)+16*(self.1%42)+self.2%42)%42,
  107.             43=>(4*(self.0%43)+41*(self.1%43)+self.2%43)%43,
  108.             44=>(36*(self.0%44)+16*(self.1%44)+self.2%44)%44,
  109.             45=>(31*(self.0%45)+16*(self.1%45)+self.2%45)%45,
  110.             46=>(36*(self.0%46)+6*(self.1%46)+self.2%46)%46,
  111.             47=>(14*(self.0%47)+25*(self.1%47)+self.2%47)%47,
  112.             48=>(16*(self.0%48)+16*(self.1%48)+self.2%48)%48,
  113.             49=>(4*(self.0%49)+2*(self.1%49)+self.2%49)%49,
  114.             50=>(6*(self.0%50)+16*(self.1%50)+self.2%50)%50,
  115.             51=>(1*(self.0%51)+1*(self.1%51)+self.2%51)%51,
  116.             52=>(48*(self.0%52)+16*(self.1%52)+self.2%52)%52,
  117.             53=>(13*(self.0%53)+15*(self.1%53)+self.2%53)%53,
  118.             54=>(4*(self.0%54)+52*(self.1%54)+self.2%54)%54,
  119.             55=>(36*(self.0%55)+16*(self.1%55)+self.2%55)%55,
  120.             56=>(32*(self.0%56)+16*(self.1%56)+self.2%56)%56,
  121.             57=>(4*(self.0%57)+55*(self.1%57)+self.2%57)%57,
  122.             58=>(54*(self.0%58)+24*(self.1%58)+self.2%58)%58,
  123.             59=>(25*(self.0%59)+5*(self.1%59)+self.2%59)%59,
  124.             60=>(16*(self.0%60)+16*(self.1%60)+self.2%60)%60,
  125.             61=>(12*(self.0%61)+16*(self.1%61)+self.2%61)%61,
  126.             62=>(8*(self.0%62)+16*(self.1%62)+self.2%62)%62,
  127.             63=>(4*(self.0%63)+16*(self.1%63)+self.2%63)%63,
  128.             64=>(0*(self.0%64)+0*(self.1%64)+self.2%64)%64,
  129.             65=>(61*(self.0%65)+16*(self.1%65)+self.2%65)%65,
  130.             66=>(58*(self.0%66)+16*(self.1%66)+self.2%66)%66,
  131.             67=>(21*(self.0%67)+17*(self.1%67)+self.2%67)%67,
  132.             68=>(52*(self.0%68)+52*(self.1%68)+self.2%68)%68,
  133.             69=>(13*(self.0%69)+52*(self.1%69)+self.2%69)%69,
  134.             70=>(46*(self.0%70)+16*(self.1%70)+self.2%70)%70,
  135.             71=>(29*(self.0%71)+10*(self.1%71)+self.2%71)%71,
  136.             72=>(40*(self.0%72)+16*(self.1%72)+self.2%72)%72,
  137.             73=>(4*(self.0%73)+2*(self.1%73)+self.2%73)%73,
  138.             74=>(70*(self.0%74)+12*(self.1%74)+self.2%74)%74,
  139.             75=>(31*(self.0%75)+16*(self.1%75)+self.2%75)%75,
  140.             76=>(4*(self.0%76)+36*(self.1%76)+self.2%76)%76,
  141.             77=>(25*(self.0%77)+16*(self.1%77)+self.2%77)%77,
  142.             78=>(22*(self.0%78)+16*(self.1%78)+self.2%78)%78,
  143.             79=>(73*(self.0%79)+51*(self.1%79)+self.2%79)%79,
  144.             80=>(16*(self.0%80)+16*(self.1%80)+self.2%80)%80,
  145.             81=>(31*(self.0%81)+52*(self.1%81)+self.2%81)%81,
  146.             82=>(10*(self.0%82)+16*(self.1%82)+self.2%82)%82,
  147.             83=>(51*(self.0%83)+36*(self.1%83)+self.2%83)%83,
  148.             84=>(4*(self.0%84)+16*(self.1%84)+self.2%84)%84,
  149.             85=>(1*(self.0%85)+1*(self.1%85)+self.2%85)%85,
  150.             86=>(4*(self.0%86)+84*(self.1%86)+self.2%86)%86,
  151.             87=>(25*(self.0%87)+82*(self.1%87)+self.2%87)%87,
  152.             88=>(80*(self.0%88)+16*(self.1%88)+self.2%88)%88,
  153.             89=>(39*(self.0%89)+67*(self.1%89)+self.2%89)%89,
  154.             90=>(76*(self.0%90)+16*(self.1%90)+self.2%90)%90,
  155.             91=>(74*(self.0%91)+16*(self.1%91)+self.2%91)%91,
  156.             92=>(36*(self.0%92)+52*(self.1%92)+self.2%92)%92,
  157.             93=>(70*(self.0%93)+16*(self.1%93)+self.2%93)%93,
  158.             94=>(14*(self.0%94)+72*(self.1%94)+self.2%94)%94,
  159.             95=>(61*(self.0%95)+36*(self.1%95)+self.2%95)%95,
  160.             96=>(64*(self.0%96)+64*(self.1%96)+self.2%96)%96,
  161.             97=>(35*(self.0%97)+61*(self.1%97)+self.2%97)%97,
  162.             98=>(4*(self.0%98)+2*(self.1%98)+self.2%98)%98,
  163.             99=>(58*(self.0%99)+16*(self.1%99)+self.2%99)%99,
  164.             100=>(56*(self.0%100)+16*(self.1%100)+self.2%100)%100,
  165.             101=>(80*(self.0%101)+79*(self.1%101)+self.2%101)%101,
  166.             102=>(52*(self.0%102)+52*(self.1%102)+self.2%102)%102,
  167.             103=>(38*(self.0%103)+55*(self.1%103)+self.2%103)%103,
  168.             104=>(48*(self.0%104)+16*(self.1%104)+self.2%104)%104,
  169.             105=>(46*(self.0%105)+16*(self.1%105)+self.2%105)%105,
  170.             106=>(66*(self.0%106)+68*(self.1%106)+self.2%106)%106,
  171.             107=>(11*(self.0%107)+92*(self.1%107)+self.2%107)%107,
  172.             108=>(4*(self.0%108)+52*(self.1%108)+self.2%108)%108,
  173.             109=>(105*(self.0%109)+66*(self.1%109)+self.2%109)%109,
  174.             110=>(36*(self.0%110)+16*(self.1%110)+self.2%110)%110,
  175.             111=>(70*(self.0%111)+49*(self.1%111)+self.2%111)%111,
  176.             112=>(32*(self.0%112)+16*(self.1%112)+self.2%112)%112,
  177.             113=>(109*(self.0%113)+30*(self.1%113)+self.2%113)%113,
  178.             114=>(4*(self.0%114)+112*(self.1%114)+self.2%114)%114,
  179.             115=>(36*(self.0%115)+6*(self.1%115)+self.2%115)%115,
  180.             116=>(112*(self.0%116)+24*(self.1%116)+self.2%116)%116,
  181.             117=>(22*(self.0%117)+16*(self.1%117)+self.2%117)%117,
  182.             118=>(84*(self.0%118)+64*(self.1%118)+self.2%118)%118,
  183.             119=>(18*(self.0%119)+86*(self.1%119)+self.2%119)%119,
  184.             120=>(16*(self.0%120)+16*(self.1%120)+self.2%120)%120,
  185.             121=>(58*(self.0%121)+93*(self.1%121)+self.2%121)%121,
  186.             122=>(12*(self.0%122)+16*(self.1%122)+self.2%122)%122,
  187.             123=>(10*(self.0%123)+16*(self.1%123)+self.2%123)%123,
  188.             124=>(8*(self.0%124)+16*(self.1%124)+self.2%124)%124,
  189.             125=>(81*(self.0%125)+116*(self.1%125)+self.2%125)%125,
  190.             126=>(4*(self.0%126)+16*(self.1%126)+self.2%126)%126,
  191.             127=>(4*(self.0%127)+2*(self.1%127)+self.2%127)%127,
  192.             128=>(0*(self.0%128)+0*(self.1%128)+self.2%128)%128,
  193.             129=>(4*(self.0%129)+127*(self.1%129)+self.2%129)%129,
  194.             130=>(126*(self.0%130)+16*(self.1%130)+self.2%130)%130,
  195.             131=>(33*(self.0%131)+65*(self.1%131)+self.2%131)%131,
  196.             132=>(124*(self.0%132)+16*(self.1%132)+self.2%132)%132,
  197.             133=>(4*(self.0%133)+93*(self.1%133)+self.2%133)%133,
  198.             134=>(88*(self.0%134)+84*(self.1%134)+self.2%134)%134,
  199.             135=>(31*(self.0%135)+106*(self.1%135)+self.2%135)%135,
  200.             136=>(120*(self.0%136)+120*(self.1%136)+self.2%136)%136,
  201.             137=>(38*(self.0%137)+60*(self.1%137)+self.2%137)%137,
  202.             138=>(82*(self.0%138)+52*(self.1%138)+self.2%138)%138,
  203.             139=>(30*(self.0%139)+13*(self.1%139)+self.2%139)%139,
  204.             140=>(116*(self.0%140)+16*(self.1%140)+self.2%140)%140,
  205.             141=>(61*(self.0%141)+25*(self.1%141)+self.2%141)%141,
  206.             142=>(100*(self.0%142)+10*(self.1%142)+self.2%142)%142,
  207.             143=>(113*(self.0%143)+16*(self.1%143)+self.2%143)%143,
  208.             144=>(112*(self.0%144)+16*(self.1%144)+self.2%144)%144,
  209.             145=>(141*(self.0%145)+111*(self.1%145)+self.2%145)%145,
  210.             146=>(4*(self.0%146)+2*(self.1%146)+self.2%146)%146,
  211.             147=>(4*(self.0%147)+100*(self.1%147)+self.2%147)%147,
  212.             148=>(144*(self.0%148)+12*(self.1%148)+self.2%148)%148,
  213.             149=>(123*(self.0%149)+102*(self.1%149)+self.2%149)%149,
  214.             150=>(106*(self.0%150)+16*(self.1%150)+self.2%150)%150,
  215.             151=>(105*(self.0%151)+16*(self.1%151)+self.2%151)%151,
  216.             152=>(80*(self.0%152)+112*(self.1%152)+self.2%152)%152,
  217.             153=>(103*(self.0%153)+52*(self.1%153)+self.2%153)%153,
  218.             154=>(102*(self.0%154)+16*(self.1%154)+self.2%154)%154,
  219.             155=>(101*(self.0%155)+16*(self.1%155)+self.2%155)%155,
  220.             156=>(100*(self.0%156)+16*(self.1%156)+self.2%156)%156,
  221.             157=>(39*(self.0%157)+14*(self.1%157)+self.2%157)%157,
  222.             158=>(152*(self.0%158)+130*(self.1%158)+self.2%158)%158,
  223.             159=>(13*(self.0%159)+121*(self.1%159)+self.2%159)%159,
  224.             160=>(96*(self.0%160)+96*(self.1%160)+self.2%160)%160,
  225.             161=>(151*(self.0%161)+121*(self.1%161)+self.2%161)%161,
  226.             162=>(112*(self.0%162)+52*(self.1%162)+self.2%162)%162,
  227.             163=>(152*(self.0%163)+57*(self.1%163)+self.2%163)%163,
  228.             164=>(92*(self.0%164)+16*(self.1%164)+self.2%164)%164,
  229.             165=>(91*(self.0%165)+16*(self.1%165)+self.2%165)%165,
  230.             166=>(134*(self.0%166)+36*(self.1%166)+self.2%166)%166,
  231.             167=>(63*(self.0%167)+49*(self.1%167)+self.2%167)%167,
  232.             168=>(88*(self.0%168)+16*(self.1%168)+self.2%168)%168,
  233.             169=>(48*(self.0%169)+94*(self.1%169)+self.2%169)%169,
  234.             170=>(86*(self.0%170)+86*(self.1%170)+self.2%170)%170,
  235.             171=>(4*(self.0%171)+169*(self.1%171)+self.2%171)%171,
  236.             172=>(4*(self.0%172)+84*(self.1%172)+self.2%172)%172,
  237.             173=>(133*(self.0%173)+47*(self.1%173)+self.2%173)%173,
  238.             174=>(112*(self.0%174)+82*(self.1%174)+self.2%174)%174,
  239.             175=>(81*(self.0%175)+16*(self.1%175)+self.2%175)%175,
  240.             176=>(80*(self.0%176)+16*(self.1%176)+self.2%176)%176,
  241.             177=>(25*(self.0%177)+64*(self.1%177)+self.2%177)%177,
  242.             178=>(128*(self.0%178)+156*(self.1%178)+self.2%178)%178,
  243.             179=>(161*(self.0%179)+124*(self.1%179)+self.2%179)%179,
  244.             180=>(76*(self.0%180)+16*(self.1%180)+self.2%180)%180,
  245.             181=>(126*(self.0%181)+44*(self.1%181)+self.2%181)%181,
  246.             182=>(74*(self.0%182)+16*(self.1%182)+self.2%182)%182,
  247.             183=>(73*(self.0%183)+16*(self.1%183)+self.2%183)%183,
  248.             184=>(128*(self.0%184)+144*(self.1%184)+self.2%184)%184,
  249.             185=>(181*(self.0%185)+86*(self.1%185)+self.2%185)%185,
  250.             186=>(70*(self.0%186)+16*(self.1%186)+self.2%186)%186,
  251.             187=>(69*(self.0%187)+137*(self.1%187)+self.2%187)%187,
  252.             188=>(108*(self.0%188)+72*(self.1%188)+self.2%188)%188,
  253.             189=>(4*(self.0%189)+79*(self.1%189)+self.2%189)%189,
  254.             190=>(156*(self.0%190)+36*(self.1%190)+self.2%190)%190,
  255.             191=>(103*(self.0%191)+26*(self.1%191)+self.2%191)%191,
  256.             192=>(64*(self.0%192)+64*(self.1%192)+self.2%192)%192,
  257.             193=>(108*(self.0%193)+84*(self.1%193)+self.2%193)%193,
  258.             194=>(132*(self.0%194)+158*(self.1%194)+self.2%194)%194,
  259.             195=>(61*(self.0%195)+16*(self.1%195)+self.2%195)%195,
  260.             196=>(4*(self.0%196)+100*(self.1%196)+self.2%196)%196,
  261.             197=>(175*(self.0%197)+61*(self.1%197)+self.2%197)%197,
  262.             198=>(58*(self.0%198)+16*(self.1%198)+self.2%198)%198,
  263.             199=>(155*(self.0%199)+126*(self.1%199)+self.2%199)%199,
  264.             211=>(119*(self.0%211)+69*(self.1%211)+self.2%211)%211,
  265.             223=>(171*(self.0%223)+49*(self.1%223)+self.2%223)%223,
  266.             227=>(147*(self.0%227)+104*(self.1%227)+self.2%227)%227,
  267.             229=>(104*(self.0%229)+44*(self.1%229)+self.2%229)%229,
  268.             233=>(135*(self.0%233)+64*(self.1%233)+self.2%233)%233,
  269.             239=>(34*(self.0%239)+150*(self.1%239)+self.2%239)%239,
  270.             241=>(15*(self.0%241)+225*(self.1%241)+self.2%241)%241,
  271.             243=>(193*(self.0%243)+133*(self.1%243)+self.2%243)%243,
  272.             251=>(243*(self.0%251)+69*(self.1%251)+self.2%251)%251,
  273.             256=>(0*(self.0%256)+0*(self.1%256)+self.2%256)%256,
  274.             257=>(1*(self.0%257)+1*(self.1%257)+self.2%257)%257,
  275.             263=>(33*(self.0%263)+104*(self.1%263)+self.2%263)%263,
  276.             269=>(21*(self.0%269)+57*(self.1%269)+self.2%269)%269,
  277.             271=>(36*(self.0%271)+265*(self.1%271)+self.2%271)%271,
  278.             277=>(155*(self.0%277)+175*(self.1%277)+self.2%277)%277,
  279.             281=>(85*(self.0%281)+101*(self.1%281)+self.2%281)%281,
  280.             283=>(151*(self.0%283)+240*(self.1%283)+self.2%283)%283,
  281.             289=>(35*(self.0%289)+18*(self.1%289)+self.2%289)%289,
  282.             293=>(161*(self.0%293)+109*(self.1%293)+self.2%293)%293,
  283.             307=>(199*(self.0%307)+97*(self.1%307)+self.2%307)%307,
  284.             311=>(35*(self.0%311)+208*(self.1%311)+self.2%311)%311,
  285.             313=>(132*(self.0%313)+142*(self.1%313)+self.2%313)%313,
  286.             317=>(235*(self.0%317)+251*(self.1%317)+self.2%317)%317,
  287.             331=>(256*(self.0%331)+16*(self.1%331)+self.2%331)%331,
  288.             337=>(4*(self.0%337)+2*(self.1%337)+self.2%337)%337,
  289.             343=>(151*(self.0%343)+296*(self.1%343)+self.2%343)%343,
  290.             347=>(129*(self.0%347)+167*(self.1%347)+self.2%347)%347,
  291.             349=>(148*(self.0%349)+219*(self.1%349)+self.2%349)%349,
  292.             353=>(22*(self.0%353)+187*(self.1%353)+self.2%353)%353,
  293.             359=>(264*(self.0%359)+303*(self.1%359)+self.2%359)%359,
  294.             361=>(156*(self.0%361)+321*(self.1%361)+self.2%361)%361,
  295.             367=>(129*(self.0%367)+297*(self.1%367)+self.2%367)%367,
  296.             373=>(68*(self.0%373)+21*(self.1%373)+self.2%373)%373,
  297.             379=>(171*(self.0%379)+277*(self.1%379)+self.2%379)%379,
  298.             383=>(150*(self.0%383)+143*(self.1%383)+self.2%383)%383,
  299.             389=>(164*(self.0%389)+169*(self.1%389)+self.2%389)%389,
  300.             397=>(273*(self.0%397)+99*(self.1%397)+self.2%397)%397,
  301.             401=>(360*(self.0%401)+63*(self.1%401)+self.2%401)%401,
  302.             409=>(265*(self.0%409)+80*(self.1%409)+self.2%409)%409,
  303.             419=>(100*(self.0%419)+409*(self.1%419)+self.2%419)%419,
  304.             421=>(255*(self.0%421)+26*(self.1%421)+self.2%421)%421,
  305.             431=>(216*(self.0%431)+337*(self.1%431)+self.2%431)%431,
  306.             433=>(150*(self.0%433)+296*(self.1%433)+self.2%433)%433,
  307.             439=>(36*(self.0%439)+433*(self.1%439)+self.2%439)%439,
  308.             443=>(153*(self.0%443)+215*(self.1%443)+self.2%443)%443,
  309.             449=>(18*(self.0%449)+359*(self.1%449)+self.2%449)%449,
  310.             457=>(68*(self.0%457)+215*(self.1%457)+self.2%457)%457,
  311.             461=>(444*(self.0%461)+370*(self.1%461)+self.2%461)%461,
  312.             463=>(60*(self.0%463)+261*(self.1%463)+self.2%463)%463,
  313.             467=>(264*(self.0%467)+369*(self.1%467)+self.2%467)%467,
  314.             479=>(28*(self.0%479)+403*(self.1%479)+self.2%479)%479,
  315.             487=>(467*(self.0%487)+286*(self.1%487)+self.2%487)%487,
  316.             491=>(429*(self.0%491)+263*(self.1%491)+self.2%491)%491,
  317.             499=>(462*(self.0%499)+31*(self.1%499)+self.2%499)%499,
  318.             _=>2
  319.         }) as usize
  320.     }
  321. }

复制代码



main
  1. #![feature(const_int_pow)]
  2. include!("main.header");
  3. extern crate rayon;
  4. use rayon::prelude::*;
  5. const UPPER:u32=193;
  6. const HALF:u32=(UPPER>>1)+1;
  7. const TO:u32=109;
  8. fn main(){
  9.     let mut lcm=BigUInt(0,0,2);
  10.     for i in 3..HALF{
  11.         lcm=lcm.mul((i/gcd(i,lcm)) as u128)
  12.     }
  13.     let mut x=(vec![BigUInt(0,0,2)],lcm);
  14.     //x=search_roll(x.0,81,x.1);//3
  15.     //x=search_roll(x.0,49,x.1);//7
  16.     x=search_roll(x.0,121,x.1);//11
  17.     x=search_roll(x.0,125,x.1);//2
  18.     x=search_roll(x.0,128,x.1);//5
  19.     x=search_roll(x.0,169,x.1);//13
  20.     //x=search_roll(x.0,243,x.1);//3
  21.     //x=search_roll(x.0,289,x.1);//17
  22.     //x=search_roll(x.0,343,x.1);//7
  23.     for i in HALF..=TO{
  24.         x=search_roll(x.0,i,x.1);
  25.         println!("i={},len={},rep={:?}",i,(x.0).len(),x.1);
  26.         if (x.0).len()>10000000{println!("break at i={},TO={}",i,TO);break}
  27.     }
  28.     let (mut b,lcm)=x;
  29.     b.sort_unstable();
  30.     println!("SHOULD check `TO` and `i` carefully!");
  31.     (0..100).into_par_iter().for_each(|i|{
  32.         search_rayon(&b,193,lcm.mul(i as u128));
  33.     });
  34. }
  35. type BIG=BigUInt;
  36. #[inline]
  37. fn gcd(i:u32,j:BIG)->u32{//ensure i<j for better performance
  38.     let (mut i,mut j)=(j.rem(i as u32) as u32,i);
  39.     while i != 0{
  40.         let t=j%i;
  41.         j=i;
  42.         i=t;
  43.     }
  44.     j
  45. }
  46. fn search_roll(b:Vec<BIG>,ix:u32,mut repeats:BIG)->(Vec<BIG>,BIG){
  47.     let i=ix/gcd(ix,repeats);
  48.     let b=if i>1{b.into_iter().map(|x|(0..i).map(|c|x.expand(repeats,c as u128)).filter(|x|ISPRIME[x.rem(ix)]).collect::<Vec<_>>()).flatten().collect::<Vec<_>>()}else{b};
  49.     if i>1 {repeats=repeats.mul(i as u128)}
  50.     (b,repeats)
  51. }
  52. fn search_rayon(b:&[BIG],mut upper:u32,mp:BIG)->u32{
  53.     let mut c=b.into_iter();
  54.     c.next();
  55.     let mut gg=vec![113,127,131,137,139,149,151,157,163,167];
  56.     let mut rem=vec![173,178,179,181,191,193,194,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293];
  57.     let mut h=rem.drain(..);
  58.     while let Some(hh)=h.next(){
  59.         gg.push(hh);
  60.         if hh>=upper{break}
  61.     }
  62.     for i in c{
  63.         while gg.iter().copied().all(|t|ISPRIME[i.add(mp).rem(t)]){
  64.             upper=h.next().unwrap();
  65.             println!("found number= {:?} for n<{}!",i.add(mp),upper);
  66.             gg.push(upper);
  67.         }
  68.     }
  69.     upper
  70. }

复制代码

finally found 655569072883475643276379698332630870445125049195696002
using gp:
ff=(d)->for(i=3,900,if(!isprime(d%i),print(i);break))
ff(655569072883475643276379698332630870445125049195696002)
194

to calculate a BigUInt:
BigUInt=(a,b,c)->d=a*2^128+b*2^64+c;for(i=3,900,if(!isprime(d%i),print(i);break));d
verify and calculate the BigUInt

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2020-8-9 07:27:55 | 显示全部楼层
今天把63以前结果补充一下：
? getlast(1395515070407)
56
? getlast(2345173940567)
58
? getlast(3018245755367)
60
? getlast(7985415341207)
62

点评

wayne
赞。望尘莫及  发表于 2020-8-9 09:40
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

123
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-23 16:20 , Processed in 0.031286 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表