Project Euler Problem 357 : 找1亿以内所有合数符合它任意积为本身的二因数之和都是

[复制链接]
查看11 | 回复9 | 2012-5-21 10:19:41 | 显示全部楼层 |阅读模式
本帖最后由 〇〇 于 2012-1-2 11:50 编辑
Problem 357
05 November 2011

Consider the divisors of 30: 1,2,3,5,6,10,15,30.
It can be seen that for every divisor d of 30, d+30/d is prime.
Find the sum of all positive integers n not exceeding 100 000 000
such that for every divisor d of n, d+n/d is prime.


回复

使用道具 举报

千问 | 2012-5-21 10:19:41 | 显示全部楼层
显然
这个合数只能由各不相同的质因数连乘组成,而且必须包含因数2
因为:
若不包含2,任意二因数之和为偶数
若包含多个相同的质因数,如18=2*3*3,那么必定有一对质因数都包含3,他们之和也有因数3

回复

使用道具 举报

千问 | 2012-5-21 10:19:41 | 显示全部楼层
而且n=1*n那么 n+1必须是质数
回复

使用道具 举报

千问 | 2012-5-21 10:19:41 | 显示全部楼层
从3楼的结论就是对每个质数-1进行质因数分解,但明显的可预先筛除,如4的倍数,9的倍数,25。。。
回复

使用道具 举报

千问 | 2012-5-21 10:19:41 | 显示全部楼层
〇〇 发表于 2012-1-1 16:54
显然
这个合数只能由各不相同的质因数连乘组成,而且必须包含因数2
因为:

何必这么麻烦
因为1也是可整除的数,d+n/d是质数,当d=1时,1+n为质数,所以n必然为偶数
另外,能不能在追加内容时编辑一下原帖?不要经常一段话分开在几个帖里说
回复

使用道具 举报

千问 | 2012-5-21 10:19:41 | 显示全部楼层
lastwinner 发表于 2012-1-2 01:35
何必这么麻烦
因为1也是可整除的数,d+n/d是质数,当d=1时,1+n为质数,所以n必然为偶数

可以,不过这样时间就错乱了,象你说的,2楼也说了
回复

使用道具 举报

千问 | 2012-5-21 10:19:41 | 显示全部楼层
记得以前有过一题分解质因子的?
即使加上前面的推理,计算量还是很大.
回复

使用道具 举报

千问 | 2012-5-21 10:19:41 | 显示全部楼层
newkid 发表于 2012-1-2 10:02
记得以前有过一题分解质因子的?
即使加上前面的推理,计算量还是很大.

记得tnb写过,今天他出现了
http://www.itpub.net/thread-1561873-1-1.html 19楼
回复

使用道具 举报

千问 | 2012-5-21 10:19:41 | 显示全部楼层
tree_new_bee的精华贴和我的质数贴




tnb+00.rar(61.11 KB, 下载次数: 8)2012-1-2 11:50 上传点击文件名下载附件

回复

使用道具 举报

千问 | 2012-5-21 10:19:41 | 显示全部楼层
〇〇 发表于 2012-1-2 07:56
可以,不过这样时间就错乱了,象你说的,2楼也说了

我是说你2楼证明必须为偶数的合数才可能是候选数的证明比较麻烦,拿除数1来看就很简单,也就是你3楼所说的(到现在才看明白,呵呵)
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

主题

0

回帖

4882万

积分

论坛元老

Rank: 8Rank: 8

积分
48824836
热门排行