与任何一个九位数都互质的最小整数（原题：1-9组成的九位数不含有的最小的因数）

lulijie

引子：
N为一个正整数，假如对于任何一个 N以内的整数m，都至少存在一个九位数可以整除m。
                       （这个九位数由1-9九个数字各用一次组成的，2<=m<=N）
那么N的最大值是多少？
-------------------------------------------------------------------------------------------------------------
上述题目金眼睛火眼金睛，答案手到擒来。
下面换一个难点的：
N为一个正整数，假如对于任何一个 N以内的整数m，都至少存在一个十位数可以整除m。
                       （这个十位数由0-9十个数字各用一次组成的，2<=m<=N）
那么N的最大值是多少？
假如100的倍数不算，又是多少？
--------------------------------------------------------------------------------------------------------------
高潮篇：
求与任何一个（由1-9九个数字各用一次组成的）九位数都互质的最小整数（大于1）。

[ 本帖最后由 lulijie 于 2009-3-15 21:49 编辑 ]

kexin_xiao

坐沙发学习!LZ喜欢数学问题啊

金眼睛

很显然啊，N=10。任意按题意构成的数都不能整除10。

美景

楼上真是金眼睛！

Cielo

原帖由 金眼睛 于 2009-3-15 19:56 发表
很显然啊，N=10。任意按题意构成的数都不能整除10。

哈哈我一开始还以为也得编程才行……

金眼睛果然厉害！

lulijie

果然厉害，一眼就看出了。没有上当。
但如果10，20，30等10的倍数不算，那又是多少呢？这就费脑了。

金眼睛

人脑不累电脑累，呵呵！1~9除去10的倍数N=5555，其他的改天算。

骰迷

這種九位數共362880個，答案太變態了，樓主弄壞幾部電腦就算出答案啦

金眼睛

这道题不编程体会不到乐趣，呵呵！

白天没时间，所以思考了很多，反而是好事，如果暴力破解，估计要半天吧！

1：采用9！或10！做总次数比多重for循环效率高。
2：依次验证每个数是否能整除然后break，不如分解出9位数或10位数的所有因数来得快。
3：边分解边对长时间没有出现的数值进行验证，呵呵！等着分解完也是很耗时的。
4：第三问的解很可能是满足第一问的质数，否则它的因数之前应该验证过整除某个9位数，即不满足互质条件。
     这个结论虽没精确证明，但可以对找到的第一问解加以验证即可。
     其实最好是对因数分解中长时间不出现的质数依次验证，找到满足第一问的第一个质数即可，这样最快。

可以看到，上述想法不用将可能情况都求出来，一个五十多行的程序，改改跑跑，两个小时就可以搞定了，呵呵！

第二问答案：37037=7*11*13*37，怪不得跟这么多数格格不入。
第三问答案：44449，曾想过能是个什么数呢，居然是它！

lulijie

哈哈，不错，第一问和第三问跟我算的一样，交流以下程序设计经验很不错。我谈谈我的心得：
我用的是最简单易懂的VB6.0程序设计，我的想法是：
    1：先设计一个子函数next9()，从1-9组成的任何一个九位数通过子函数next9（），可获得下一个1-9的九位数。
这样可以从初始九位数123456789，通过子函数next9()，遍举所有的1-9组成的九位数。
    2：然后用一个for   next  循环   检验整数m是否满足条件。
       第一题：m从整数2开始逐渐增加，对于每个m检查是否存在一个九位数整除它。九位数从最小开始检验，遇到有一个九位数能整除，就跳到下一个m。直到发现所有的九位数都不能整除为止。记下m即可。其实对于每个m，大部分都不需要检验很多的九位数，因为遇到一个九位数能整除，余下的九位数就不用检验，跳到下一个m。
               但在计算第二题10位数时，经常等了很久都没反应（因为我在每检验一定长度的m时，就会生成一个文件，记录下计算到哪个数字了。）经过调试和思考，发现每当m=10的倍数时，就要等很久，原来，按照我的遍举十位数的方法，要整除m（m是10的倍数）一定要遍举到0在个位时，0从最前位经过我的Next10函数，位置变到个位，花费大量的时间。后来就让遇到10的倍数就跳过，速度快多了。因为0在个位，前九位数就是1-9组成的九位数，按照第一题的结果，在计算m=5555*10=55550之前根本不用理会10的倍数。但由于时间原因，我还暂时只计算到14000之内，没有发现满足要求的结果。还有一个影响速度的原因是vb6.0中的整数最大只能是2147483647，所以对于大于它的十位数，只能通过一个转换来计算，影响了速度。用VB2005来变程就没这个问题了。
    第三题：检查两个整数是否互质，设计一个函数来判断两个整数是否互质。利用辗转相除法，就可以判断，最后得到0就是含有公因数，得到1，就是互质。再利用Next9函数，检验方法同第一题。
------------------------------------------------------------------------------------------------------
在计算第一题和第三题都花不了多少时间，第二题费时间明显增加，按照金眼睛的答案，我可能还要继续运行1、2个小时或2、3个小时才能算出这个结果。