Mathematica轻松解素数相关民间问题

本文主要是介绍Mathematica轻松解素数相关民间问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题的来源

顺便说一下，CSDN markdown编辑器的改版带来诸多不爽。

言归正传，网上有人以征婚名义出了两道素数题，虽然八成又是一个做微商、卖茶叶或其他山货的营销手段，必然带有欺骗性（如果是愚人节玩笑，算我没说），但是其中的问题还是有好事者用各种工具给出答案的。实际上，看遍各种工具，mathematica最为强大。
在这里插入图片描述
问题直接抽象出来就是两道简单的素数问题：

分解出 7140229933 的两个素数因子；
找出只有两个素数因子的形如： 6541367xxx 的素数，并分解它(们)的素数因子

求解

直接跳过网络上其它任何求解方法，用mathematica:

直接输入代码如下得到第一个问题答案：
FactorInteger[7140229933] // Flatten[Delete[#, Position[#, 1]]] &
秒出结果：
{83777, 85229}
第二个问题的答案不妨稍作分析
形如“6541367xxx”的数，其实就是“6541367000~6541367999”之间（包含两端）的1000个数字，暴力穷举方式逐个验证素数因子的个数，然后对个数为2的逐个拿出来即可，答案不唯一、而且技术难度跟第一题类似，这是让我觉得这“征婚”可能是微商卖茶叶或山货的重要原因。

${\color{red}{评论区“土肥圆”网友给出了一个更好的解法，总之我眼睛为之一亮，我找的那些代码尽可以扔垃圾堆里里。}}$

Select[Range[1000] + 6541367*1000 - 1,  DivisorSigma[0, #] == 4 &] // Timing

在我电脑上0.05秒不到找出所有的这151个整数。主要是用到了Mathematica中内置的整数和数论有关的特殊函数。DivisorSigma[k,n] 可以从帮助文档中查看，可以找出整数n的全部因子（包括1和自身及其它可能存在的素因子）的k次幂的和。如果k=0, 找到的就是不同素数因子的个数加2. 点到这里就可以为止了。

先统计满足条件的数有多少个：

((PrimeNu /@ Range[6541367000, 6541367999]) //Count[#, x_ /; x == 2] &) - ((((FactorInteger /@ numList) // Flatten[#, 1] &)[[;; , 2]]) // Count[#, x_ /; x >= 2] &)

得到 151；

再找出这些数（实际上上面统计代码是先找到这些数，不过输出的形式不同而已）在整个自然数列中的位置：

index=((First@Dimensions@FactorInteger@#) & /@ Range[6541367000, 6541367999]) // Position[#, 2] &

使用计算出的位置索引，找出这些数

numList=Range[6541367000, 6541367999] // Extract[#, index] &

结果是：

{6541367003, 6541367005, 6541367011, 6541367017, 6541367023, \
6541367037, 6541367038, 6541367039, 6541367043, 6541367053, \
6541367059, 6541367061, 6541367071, 6541367077, 6541367113, \
6541367114, 6541367117, 6541367127, 6541367135, 6541367137, \
6541367141, 6541367153, 6541367159, 6541367167, 6541367169, \
6541367171, 6541367173, 6541367177, 6541367179, 6541367186, \
6541367189, 6541367201, 6541367207, 6541367218, 6541367239, \
6541367241, 6541367254, 6541367257, 6541367258, 6541367267, \
6541367277, 6541367289, 6541367293, 6541367297, 6541367309, \
6541367311, 6541367317, 6541367323, 6541367341, 6541367353, \
6541367359, 6541367369, 6541367374, 6541367379, 6541367402, \
6541367413, 6541367419, 6541367421, 6541367429, 6541367431, \
6541367433, 6541367438, 6541367439, 6541367446, 6541367447, \
6541367451, 6541367459, 6541367461, 6541367471, 6541367473, \
6541367477, 6541367479, 6541367483, 6541367485, 6541367489, \
6541367491, 6541367497, 6541367501, 6541367503, 6541367521, \
6541367523, 6541367531, 6541367541, 6541367545, 6541367551, \
6541367554, 6541367557, 6541367563, 6541367577, 6541367597, \
6541367599, 6541367603, 6541367605, 6541367609, 6541367611, \
6541367617, 6541367619, 6541367626, 6541367627, 6541367649, \
6541367654, 6541367662, 6541367663, 6541367669, 6541367674, \
6541367681, 6541367689, 6541367707, 6541367719, 6541367727, \
6541367731, 6541367738, 6541367743, 6541367747, 6541367758, \
6541367761, 6541367765, 6541367771, 6541367773, 6541367782, \
6541367793, 6541367795, 6541367806, 6541367829, 6541367843, \
6541367845, 6541367851, 6541367857, 6541367871, 6541367873, \
6541367879, 6541367883, 6541367887, 6541367901, 6541367906, \
6541367909, 6541367915, 6541367921, 6541367923, 6541367926, \
6541367927, 6541367929, 6541367933, 6541367942, 6541367951, \
6541367959, 6541367962, 6541367963, 6541367971, 6541367989, \
6541367995}

分解它们的素数因子：

Sort /@ ((numList // FactorInteger) // Delete[#, Position[#, 1]] & // Flatten // ArrayReshape[#, {194, 2}] &) // MatrixForm

得到结果如下：
$\left[ \begin{array}{ll} 23 & 284407261 \\ 5 & 1308273401 \\ 37 & 176793703 \\ 41 & 159545537 \\ 5419 & 1207117 \\ 3 & 2180455679 \\ 2 & 3270683519 \\ 14177 & 461407 \\ 3 & 2180455681 \\ 13 & 503182081 \\ 20359 & 321301 \\ 3 & 2180455687 \\ 31 & 211011841 \\ 7 & 934481011 \\ 53 & 123422021 \\ 2 & 3270683557 \\ 17 & 384786301 \\ 3 & 2180455709 \\ 5 & 1308273427 \\ 73 & 89607769 \\ 23 & 284407267 \\ 11839 & 552527 \\ 37 & 176793707 \\ 4231 & 1546057 \\ 3 & 2180455723 \\ 2089 & 3131339 \\ 11 & 594669743 \\ 19 & 344282483 \\ 24439 & 267661 \\ 2 & 3270683593 \\ 7 & 934481027 \\ 2857 & 2289593 \\ 40819 & 160253 \\ 2 & 3270683609 \\ 11 & 594669749 \\ 3 & 2180455747 \\ 2 & 3270683627 \\ 31 & 211011847 \\ 2 & 3270683629 \\ 409 & 15993563 \\ 3 & 2180455759 \\ 3 & 2180455763 \\ 32707 & 199999 \\ 263 & 24872119 \\ 331 & 19762439 \\ 883 & 7408117 \\ 55901 & 117017 \\ 241 & 27142603 \\ 5107 & 1280863 \\ 52901 & 123653 \\ 137 & 47747207 \\ 97 & 67436777 \\ 2 & 3270683687 \\ 3 & 2180455793 \\ 2 & 3270683701 \\ 7 & 934481059 \\ 269 & 24317351 \\ 3 & 2180455807 \\ 73 & 89607773 \\ 53 & 123422027 \\ 3 & 2180455811 \\ 2 & 3270683719 \\ 3 & 2180455813 \\ 2 & 3270683723 \\ 6203 & 1054549 \\ 3 & 2180455817 \\ 11 & 594669769 \\ 947 & 6907463 \\ 5839 & 1120289 \\ 1013 & 6457421 \\ 157 & 41664761 \\ 89 & 73498511 \\ 7 & 934481069 \\ 5 & 1308273497 \\ 67049 & 97561 \\ 17 & 384786323 \\ 7 & 934481071 \\ 19081 & 342821 \\ 11 & 594669773 \\ 13 & 503182117 \\ 3 & 2180455841 \\ 83 & 78811657 \\ 3 & 2180455847 \\ 5 & 1308273509 \\ 47 & 139178033 \\ 2 & 3270683777 \\ 19 & 344282503 \\ 97 & 67436779 \\ 3 & 2180455859 \\ 431 & 15177187 \\ 13 & 503182123 \\ 37 & 176793719 \\ 5 & 1308273521 \\ 7 & 934481087 \\ 11497 & 568963 \\ 113 & 57888209 \\ 3 & 2180455873 \\ 2 & 3270683813 \\ 17 & 384786331 \\ 3 & 2180455883 \\ 2 & 3270683827 \\ 2 & 3270683831 \\ 58049 & 112687 \\ 71 & 92131939 \\ 2 & 3270683837 \\ 443 & 14766067 \\ 1693 & 3863773 \\ 7 & 934481101 \\ 9421 & 694339 \\ 3 & 2180455909 \\ 9887 & 661613 \\ 2 & 3270683869 \\ 971 & 6736733 \\ 19 & 344282513 \\ 2 & 3270683879 \\ 10709 & 610829 \\ 5 & 1308273553 \\ 79801 & 81971 \\ 211 & 31001743 \\ 2 & 3270683891 \\ 3 & 2180455931 \\ 5 & 1308273559 \\ 2 & 3270683903 \\ 3 & 2180455943 \\ 113 & 57888211 \\ 5 & 1308273569 \\ 1567 & 4174453 \\ 19309 & 338773 \\ 3 & 2180455957 \\ 541 & 12091253 \\ 61 & 107235539 \\ 3 & 2180455961 \\ 8681 & 753527 \\ 3 & 2180455967 \\ 2 & 3270683953 \\ 49109 & 133201 \\ 5 & 1308273583 \\ 11 & 594669811 \\ 23 & 284407301 \\ 2 & 3270683963 \\ 47 & 139178041 \\ 487 & 13431967 \\ 17 & 384786349 \\ 2 & 3270683971 \\ 97 & 67436783 \\ 7 & 934481137 \\ 2 & 3270683981 \\ 13 & 503182151 \\ 331 & 19762441 \\ 13 & 503182153 \\ 5 & 1308273599 \\ \end{array} \right]$
在这里插入图片描述
看到答案之后，您可以尝试拿着这里的数据去加微信、购买茶叶或山货了。注意别买得比市场价高太多，同时也要监控产品质量，别买一堆假冒伪劣产品。——特别指出的是，我给出这里正确答案的代码，并不是贴在此处的代码。Mathematica数组操作没有matlab思维那么直观；要不断尝试不同的函数，如果不常使用也不太熟悉，挺繁琐。大概思路，找出1000个10位数字中的素数，排除；找出三个以上不同素因子的，排除；还得找出虽然刚好两个独立素因子，但某个素因子指数大于1的，排除（如果不排除这种则有194个）；剩下的就是刚好2个素因子的了（151个）；
在这里插入图片描述