a prime question

无心人

发现再向上穷举，似乎很困难了 在穷举10万内的 希望时间少些 下个数量级就只能用mathe的分解算法了

kofeffect

13#的数据限制p和q在Prime(100)=541的范围内，所以漏掉了一些，如 5,[1151,2,1153),(1151,3,577),(1151,7,193),(1151,13,97),(1151,17,73)])

无心人

穷举的在10万内素数的程序就运行了两个小时无结果 放弃了 现在在考虑如何表示N的全部的因子p * p <= N如何表示 如果是C可能用个迭代函数就OK了 但Haskell似乎有点问题 还是不精通啊

无心人

Prelude> let prodl l r = foldl (++) [] \$ map (\x -> map (x*) r) l Prelude> let l = [1..3] Prelude> let r = [1..4] Prelude> prodl l r [1,2,3,4,2,4,6,8,3,6,9,12] =================================================== 笛卡尔乘

无心人

3. import Primes
4. import Factoring
5. import List
7. cartProd l r = foldl (++) [] \$ map (\x -> map (x*) r) l
8. powerList (a, b) = take (b + 1) \$ iterate (a*) 1
9. factorsList n = sort \$ foldl1 cartProd \$ map powerList \$ primePowerFactorsL n
10. factorPairs n = map (\x -> (x, div n x)) \$ filter (\x -> x * x <= n) \$ factorsList n
11. factorPairValid (a, b) = (isPrime (a + 1)) && (isPrime (b + 1)) && (a < b)
13. main = do
14. let pp6 = primesTo1000000
15. let a = sort [(n, p, l) | p <- pp6, let l = map (\(a, b) -> (a + 1, b + 1)) \$ filter (\(a, b) -> factorPairValid (a, b)) \$ factorPairs (p + 1), let n = length l]
16. let max = (\(n, _, _) -> n) \$ last a
17. let r = [x | i <- [1..max], let y = filter (\(n, _, _) -> n == i) a, not (null y), let x = head y]
18. print \$ show r

复制代码

测试100万内的结果 "[(1,3,[(2,5)]), (2,11,[(2,13),(3,7)]), (3,59,[(2,61),(3,31),(7,11)]), (4,71,[(2,73),(3,37),(5,19),(7,13)]), (5,1151,[(2,1153),(3,577),(7,193),(13,97),(17,73)]), (6,2399,[(3,1201),(5,601),(7,401),(11,241),(17,151),(41,61)]), (7,9719,[(2,9721),(3,4861),(7,1621),(13,811),(19,541),(37,271),(61,163)]), (8,19319,[(3,9661),(5,4831),(7,3221),(11,1933),(29,691),(43,461),(47,421),(71,277)]), (9,7559,[(2,7561),(11,757),(13,631),(19,421),(29,271),(37,211),(43,181),(61,127),(71,109)]), (10,42839,[(2,42841),(5,10711),(13,3571),(19,2381),(29,1531),(31,1429),(43,1021),(71,613),(103,421),(181,239)]), (11,110879,[(2,110881),(3,55441),(7,18481),(13,9241),(31,3697),(113,991),(127,881),(181,617),(241,463),(281,397),(331,337)]), (12,181439,[(5,45361),(7,30241),(13,15121),(29,6481),(71,2593),(73,2521),(113,1621),(181,1009),(241,757),(271,673),(337,541),(421,433)]), (13,347759,[(29,12421),(31,11593),(37,9661),(47,7561),(71,4969),(73,4831),(109,3221),(139,2521),(181,1933),(211,1657),(271,1289),(421,829),(461,757)]), (14,241919,[(2,241921),(13,20161),(17,15121),(19,13441),(29,8641),(71,3457),(73,3361),(97,2521),(113,2161),(211,1153),(241,1009),(379,641),(421,577),(449,541)]), (15,385559,[(3,192781),(11,38557),(31,12853),(37,10711),(43,9181),(61,6427),(109,3571),(127,3061),(163,2381),(181,2143),(239,1621),(271,1429),(379,1021),(421,919),(613,631)]), (16,262079,[(3,131041),(5,65521),(11,26209),(13,21841),(17,16381),(19,14561),(31,8737),(41,6553),(79,3361),(97,2731),(113,2341),(127,2081),(131,2017),(211,1249),(241,1093),(281,937)]),(17,453599,[(2,453601),(11,45361), (17,28351),(31,15121),(37,12601),(61,7561),(71,6481),(73,6301),(109,4201),(113,4051),(163,2801),(181,2521),(211,2161),(281,1621),(379,1201),(433,1051),(601,757)]), (19,665279,[(3,332641),(7,110881),(11,66529),(13,55441),(23,30241),(29,23761),(37,18481),(41,16633),(73,9241),(89,7561),(127,5281),(181,3697),(199,3361),(211,3169),(281,2377),(331,2017),(661,1009),(673,991),(757,881)])]" 这次运算速度很快， 呵呵

无心人

这次搜索出来的可以确定是最小的了 1 3 2 11 3 59 4 71 5 1151 6 2399 7 9719 8 19319 9 7559 10 42839 11 110879 12 181439 13 347759 14 241919 15 385559 16 262079 17 453599 19 665279

无心人

更大的10^7内 (18,1441439,[(13,120121),(23,65521),(29,51481),(31,48049),(41,36037),(67,21841),(71,20593),(73,20021),(79,18481),(89,16381),(157,9241),(181,8009),(241,6007),(313,4621),(421,3433),(463,3121),(617,2341),(1093,1321)]), (19,665279,[(3,332641),(7,110881),(11,66529),(13,55441),(23,30241),(29,23761),(37,18481),(41,16633),(73,9241),(89,7561),(127,5281),(181,3697),(199,3361),(211,3169),(281,2377),(331,2017),(661,1009),(673,991),(757,881)]), (20,1713599,[(2,1713601),(5,428401),(17,107101),(41,42841),(43,40801),(71,24481),(73,23801),(97,17851),(101,17137),(137,12601),(181,9521),(211,8161),(281,6121),(337,5101),(409,4201),(601,2857),(613,2801),(673,2551),(953,1801),(1201,1429)]), (21,4804799,[(3,2402401),(5,1201201),(7,800801),(17,300301),(23,218401),(41,120121),(53,92401),(89,54601),(97,50051),(101,48049),(113,42901),(241,20021),(313,15401),(331,14561),(521,9241),(601,8009),(673,7151),(911,5281),(1249,3851),(1301,3697),(2081,2311)]), (22,2827439,[(7,471241),(13,235621),(19,157081),(23,128521),(29,100981),(37,78541),(41,70687),(67,42841),(127,22441),(199,14281),(281,10099),(307,9241),(379,7481),(421,6733),(463,6121),(541,5237),(613,4621),(617,4591),(953,2971),(991,2857),(1123,2521),(1321,2143)]), (23,6425999,[(2,6426001),(37,178501),(41,160651),(43,153001),(61,107101),(71,91801),(127,51001),(137,47251),(151,42841),(271,23801),(307,21001),(601,10711),(613,10501),(701,9181),(757,8501),(919,7001),(1021,6301),(1051,6121),(1531,4201),(1801,3571),(2143,3001),(2251,2857),(2521,2551)]), (24,6652799,[(2,6652801),(7,1108801),(17,415801),(61,110881),(67,100801),(73,92401),(101,66529),(193,34651),(199,33601),(281,23761 ),(331,20161),(337,19801),(401,16633),(433,15401),(449,14851),(463,14401),(577,11551),(673,9901),(881,7561),(1051,6337),(1601,4159),(1801,3697),(2017,3301),(2377,2801)]), (25,9827999,[(2,9828001),(5,2457001),(11,982801),(13,819001),(19,546001),(37,273001),(71,140401),(73,136501),(79,126001),(113,87751),(151,65521),(181,54601),(251,39313),(337,29251),(401,24571),(433,22751),(601,16381),(631,15601),(757,13001),(937,10501),(1093,9001),(1201,8191),(1301,7561),(2341,4201),(2801,3511)])

无心人

这次找了个强悍的素数筛程序 ONeillPrimes.hs (6.53 KB, 下载次数: 2)

2009-3-10 17:07 上传

点击文件名下载附件

在筛10^8内的 筛完就不再做这个题目了

无心人

继续 10^8 内 (26,12700799,[(7,2116801),(29,453601),(61,211681),(73,176401),(127,100801),(151,84673),(163,78401),(271,47041),(281,45361),(379,33601),(421,30241),(433,29401),(449,28351),(577,22051),(601,21169),(631,20161),(883,14401),(1009,12601),(1051,12097),(1471,8641),(1621,7841),(1801,7057),(2017,6301),(2161,5881),(2647,4801),(3137,4051)]), (27,14137199,[(3,7068601),(13,1178101),(29,504901),(31,471241),(61,235621),(71,201961),(89,160651),(137,103951),(181,78541),(271,52361),(331,42841),(409,34651),(601,23563),(631,22 441),(757,18701),(919,15401),(953,14851),(991,14281),(1123,12601),(1321,10711),(1429,9901),(1531,9241),(1871,7561),(2311,6121),(2857,4951),(3061,4621),(3673,3851)]), (28,25280639,[(17,1580041),(67,383041),(73,351121),(89,287281),(113,225721),(181,140449),(193,131671),(199,127681),(229,110881),(241,105337),(281,90289),(353,71821),(397,63841),(449,56431),(457,55441),(463,54721),(541,46817),(577,43891),(631,40129),(881,28729),(991,25537),(2017,12541),(2113,11971),(2927,8641),(2971,8513),(3041,8317),(3697,6841),(4789,5281)]), (29,46388159,[(2,46388161),(5,11597041),(17,2899261),(31,1546273),(71,662689),(79,594721),(97,483211),(109,429521),(181,257713),(211,220897),(281,165673),(521,89209),(547,84961),(673,69031),(709,65521),(1009,46021),(1181,39313),(1249,37171),(1873,24781),(1889,24571),(2017,23011),(2081,22303),(2731,16993),(2833,16381),(3121,14869),(3187,14561),(3361,13807),(3511,13217),(4721,9829)]), (30,22276799,[(7,3712801),(29,795601),(43,530401),(53,428401),(61,371281),(97,232051),(103,218401),(113,198901),(151,148513),(239,93601),(241,92821),(281,79561),(337,66301),(409,54601),(521,42841),(547,40801),(673,33151),(911,24481),(937,23801),(1021,21841),(1249,17851),(1301,17137),(1361,16381),(1429,15601),(1531,14561),(1801,12377),(2081,10711),(2341,9521),(2551,8737),(2731,8161)]), (31,16707599,[(3,8353801),(11,1670761),(41,417691),(53,321301),(71,238681),(73,232051),(101,167077),(131,128521),(157,107101),(181,92821),(211,79561),(239,70201),(281,59671),(307,54601),(313,53551),(379,44201),(541,30941),(601,27847),(701,23869),(937,17851),(953,17551),(1021,16381),(1051,15913),(1171,14281),(1301,12853),(1327,12601),(1429,11701),(1801,9283),(2551,6553),(2731,6121),(2857,5851)]), (32,25945919,[(7,4324321),(17,1621621),(41,648649),(43,617761),(53,498961),(61,432433),(67,393121),(79,332641),(97,270271),(113,231661),(199,131041),(211,123553),(241,108109),(271,96097),(397,65521),(541,48049),(547,47521),(661,39313),(673,38611),(859,30241),(911,28513),(991,26209),(1009,25741),(1093,23761),(1297,20021),(1783,14561),(2971,8737),(3121,8317),(3169,8191),(3361,7723),(3433,7561),(3511,7393)]), (33,45239039,[(19,2513281),(71,646273),(89,514081),(97,471241),(127,359041),(137,332641),(193,235621),(281,161569),(331,137089),(353,128521),(409,110881),(421,107713),(449,100981),(541,83777),(577,78541),(631,71809),(641,70687),(953,47521),(991,45697),(1321,34273),(1531,29569),(2017,22441),(2143,21121),(2381,19009),(2689,16831),(2971,15233),(3169,14281),(3697,12241),(4481,10099),(4591,9857),(5237,8641),(5441,8317),(6121,7393)]), (34,64864799,[(41,1621621),(53,1247401),(67,982801),(101,648649),(109,600601),(131,498961),(151,432433),(157,415801),(241,270271),(281,231661),(331,196561),(337,193051),(433,150151),(463,140401),(541,120121),(547,118801),(601,108109),(991,65521),(1171,55441),(1297,50051),(1801,36037),(1873,34651),(2003,32401),(2311,28081),(2521,25741),(2731,23761),(2801,23167),(2971,21841),(3511,18481),(3697,17551),(4159 ,15601),(6553,9901),(7561,8581),(8009,8101)]), (35,77111999,[(2,77112001),(7,12852001),(11,7711201),(13,6426001),(17,4819501),(29,2754001),(31,2570401),(37,2142001),(97,803251),(151,514081),(181,428401),(211,367201),(241,321301),(307,252001),(401,192781),(433,178501),(601,128521),(613,126001),(631,122401),(701,110161),(757,102001),(953,81001),(1361,56701),(1429,54001),(1801,42841),(2251,34273),(2381,32401),(2551,30241),(2801,27541),(3571,21601),(3673,21001),(5101,15121),(6121,12601),(6301,12241),(8101,9521)] ), (36,82882799,[(3,41441401),(7,13813801),(29,2960101),(31,2762761),(37,2302301),(61,1381381),(67,1255801),(79,1062601),(101,828829),(139,600601),(151,552553),(199,418601),(277,300301),(281,296011),(421,197341),(461,180181),(601,138139),(631,131561),(691,120121),(859,96601),(911,91081),(1013,81901),(1151,72073),(1171,70841),(1321,62791),(1657,50051),(1933,42901),(2393,34651),(3221,25741),(3301,25117),(3433,24151),(3851,21529),(7151,11593),(7177,11551),(8581,9661),(8971,9241)]), (37,82162079,[(3,41081041),(13,6846841),(17,5135131),(29,2934361),(37,2282281),(53,1580041),(61,1369369),(79,1053361),(113,733591),(127,652081),(157,526681),(181,456457),(191,432433),(211,391249),(241,342343),(379,217361),(397,207481),(419,196561),(457,180181),(463,177841),(661,124489),(761,108109),(911,90289),(1483,55441),(1597,51481),(1873,43891),(2129,38611),(2161,38039),(2281,36037),(2311,35569),(2731,30097),(2861,28729),(2927,28081),(4447,18481),(6007,13681),(6553,12541),(8893,9241)]), (40,99459359,[(3,49729681),(5,24864841),(7,16576561),(11,9945937),(23,4520881),(37,2762761),(53,1912681),(73,1381381),(79,1275121),(109,920921),(181,552553),(199,502321),(211,473617),(271,368369),(313,318781),(337,296011),(461,216217),(617,161461),(661,150697),(757,131561),(829,120121),(881,113023),(911,109297),(937,106261),(1093,91081),(1171,85009),(1381,72073),(1933,51481),(2003,49681),(2531,39313),(2731,36433),(4049,24571),(4621,21529),(4831,20593),(4969,20021),(5981,16633),(6007,16561),(6073,16381),(8009,12421),(8581,11593)]), (42,86486399,[(3,43243201),(7,14414401),(29,3088801),(37,2402401),(73,1201201),(79,1108801),(89,982801),(109,800801),(151,576577),(193,450451),(199,436801),(211,411841),(337,257401),(397,218401),(401,216217),(433,200201),(449,193051),(577,150151),(617,140401),(661,131041),(701,123553),(859,100801),(937,92401),(1093,79201),(1201,72073),(1301,66529),(1321,65521),(1801,48049),(2003,43201),(2017,42901),(2311,37441),(2861,30241),(3301,26209),(3361,25741),(4201,20593),(5281,16381),(6007,14401),(6301,13729),(7151,12097),(7393,11701),(7489,11551),(8737,9901)]), (45,93562559,[(2,93562561),(5,23390641),(11,9356257),(13,7796881),(17,5847661),(79,1199521),(103,917281),(131,719713),(137,687961),(181,519793),(197,477361),(211,445537),(239,393121),(271,346529),(307,305761),(313,299881),(409,229321),(443,211681),(631,148513),(919,101921),(937,99961),(1009,92821),(1429,65521),(1471,63649),(1531,61153),(2017,46411),(2081,44983),(2381,39313),(2549,36721),(2731,34273),(3061,30577),(3121,29989),(3361,27847),(3571,26209),(3823,24481),(4421,21169),(5881,15913),(6121,15289),(6427,14561),(6553,14281),(7561,12377),(8161,11467),(8737,10711),(9181,10193),(9521,9829)]) 中间的间隔各位有兴趣的来补齐（38, 39, 41, 43, 44，都在10^8以上了）

无心人

(2^9*3^5*5^2*7^2*11^2*13*17*19*23*29-1 = 5164 9890 1446 5279 9)是个素数！！！！ 对应该题目的数值是1013组！！！！