应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第廿三题：
北京石油化工学院2026年研究生招生接收调剂公告
172/2返回列表上一页12
查看: 2313  |  回复: 16
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 4 个 程序强帖 ，点击这里进行查看

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+2): 辛苦了 2011-06-07 15:08:35
按上面的算法重写了下,6s多,看看python还能提高效率不

代码
CODE:
#! usr/bin/env python
# coding: cp936

from mytictoc import tic, toc
from math import sqrt

def sumdivisors(n):
    sumdiv = sum([i+n/i for i in xrange(2,int(sqrt(n))+1) if n%i==0])+1
    if int(sqrt(n))*int(sqrt(n))==n:
        sumdiv -= int(sqrt(n))
    return sumdiv

def euler23():
    n = 28123
    tic()
    abn_list = [c for c in xrange(12,n+1) if sumdivisors(c)>c] # 生成富数列表
   
    # 生成所有可表示成2个富数之和的数,并剔除重复项
    num_list = set([abn_list[i]+j for i in xrange(0,len(abn_list)) for j in abn_list[i:] if abn_list[i]+j    
    # 1-28123求和减去num_list求和即为结果
    print sum(xrange(1,n))-sum(num_list)
    toc()

if __name__=='__main__':
    euler23()

结果
CODE:
C:\WINDOWS\system32\cmd.exe /c python test.py
4179871
Elapsed time: 6.37453140 seconds

Hit any key to close this window...

[ Last edited by libralibra on 2011-6-7 at 02:08 ]
赞一下(2人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
11楼2011-06-07 02:05:17
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★
jjdg(金币+1): 感谢参与 2011-06-07 15:08:22
如果两两富数的和没重复，就可以在O(n)时间里计算出来了。可惜不只有重复，而且还有很多的重复，看来怎么也在O(n^2)这个量级上了。
赞一下(1人) 回复此楼
12楼2011-06-07 09:05:18
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+2): 辛苦了 2011-06-07 15:08:04
直觉告诉我不会有比O(N^2)更快的算法了，不过仍然的我们可以空间换时间：
CODE:
#include

#define MAGIC 28124

int fsum[MAGIC];
unsigned char tag[MAGIC];

int main(){
    int sum=0;
    int i, j;

    for(i=1; i         for(j=i+i; j             fsum[j] += i;
        }
    } //计算因子和表

    for(i=1; i         if(fsum[i]<=i) continue;
        for(j=i; i+j             if(fsum[j]>j){
                tag[i+j] = 1;
            }
        }
    } //标记所有能表示为两个富数和的数

    for(i=1; i         if(!tag[i]) sum += i;
    }

    printf("%d\n", sum);

    return 0;
}

输出：
CODE:
4179871

Process returned 0 (0x0)   execution time : 0.269 s
Press any key to continue.

PS:
仔细翻了一下前面的帖子发现思想和huycwork的差不多...就当上面什么也没写吧...（咳，怎么找不到删帖的选项呢...）

[ Last edited by sudo on 2011-6-7 at 09:36 ]
赞一下(2人) 回复此楼
13楼2011-06-07 09:12:25
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★
jjdg(金币+1): 感谢参与 2011-06-07 15:07:47
引用回帖:
Originally posted by sudo at 2011-06-07 09:12:25:
直觉告诉我不会有比O(N^2)更快的算法了，不过仍然的我们可以空间换时间：

[code]
#include <stdio.h>

#define MAGIC 28124

int fsum[MAGIC];
unsigned char tag[MAGIC];

int main(){
    in ...

没事，挂着吧。

感觉这种组合法要比那种分解法要快。
赞一下(1人) 回复此楼
14楼2011-06-07 12:08:57
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+1): 感谢参与 2011-06-07 15:07:36
引用回帖:
Originally posted by holmescn at 2011-06-07 12:08:57:
没事，挂着吧。

感觉这种组合法要比那种分解法要快。

其实应该是比huywork的稍微慢一点~因为如果生成富数表的话，规模就变小不少吧~我这个是直接暴力试

PS：咳，刚开始没理解你的意思...呃，huywork就是这种方法啊，在前面大家都没看见？这个肯定比分解法快的，因为既没有重复计算，也不涉及除法

[ Last edited by sudo on 2011-6-7 at 14:06 ]
赞一下(2人) 回复此楼
15楼2011-06-07 12:33:27
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

蓝水卫士

木虫 (著名写手)
★
jjdg(金币+1): 感谢参与 2011-06-07 15:08:44
都是高手啊！
回复此楼
16楼2011-06-07 12:56:22
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 欢迎讨论 2011-06-07 22:46:22
引用回帖:
Originally posted by sudo at 2011-06-07 12:33:27:
其实应该是比huywork的稍微慢一点~因为如果生成富数表的话，规模就变小不少吧~我这个是直接暴力试

PS：咳，刚开始没理解你的意思...呃，huywork就是这种方法啊，在前面大家都没看见？这个肯定比分解法 ...

兄台太过谦虚了呃~人月神话里面不是说嘛，世界上没有两个一样的软件，而且你的意见一向精炼且带文艺美的说，用前人的话说，就是前面的脖子和肩膀啊

我觉得如果把筛选出来的富数应用组合的话，时间应该还可以再优化的，我给的代码里面有一些冗余计算，比直接组合所有富数和要慢，但是比暴力穷举要快。慢的原因就在于每次都要从第一个开始试算，直接组合就没有这种失败了。
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
17楼2011-06-07 16:13:48
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
172/2返回列表上一页12
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 085600材料与化工301分求调剂院校 +9 刺痛jk 2026-04-06 10/500 2026-04-06 08:12 by melodiousnow
[考研] 一志愿河北工业大学材料工程，初试344求专硕调剂 +4 15933906766 2026-04-05 4/200 2026-04-06 07:22 by hmn_wj
[考研] 071000生物学调剂 +3 拉提桃 2026-04-06 3/150 2026-04-06 05:41 by 天道酬勤girl
[考研] 272分求调剂 +4 wangyile2233 2026-04-02 4/200 2026-04-05 22:21 by 286640313
[考研] 08专硕275调剂 +5 AaAa7420 2026-04-05 5/250 2026-04-05 18:01 by jkddd
[考研] 求调剂 +4 wos666 2026-04-03 4/200 2026-04-05 11:48 by arrow8852
[考研] 313求调剂 +3 海日海日 2026-04-04 3/150 2026-04-05 07:48 by 544594351
[考研] 342求调剂 +3 Liang7111 2026-04-04 5/250 2026-04-04 19:47 by dongzh2009
[考研] 一志愿085404，总分291，四级已过，求调剂 +5 阿俊阿俊阿俊 2026-04-04 7/350 2026-04-04 13:23 by 莲菜就是藕吧
[考研] 求调剂，一志愿南京航空航天大学 ，080500材料科学与工程学硕 +10 @taotao 2026-04-03 10/500 2026-04-04 09:01 by T可可西里T
[考研] 材料科学与工程考研 +10 拯救皮特托先生 2026-04-02 10/500 2026-04-03 23:57 by userper
[考研] 求调剂不挑专业 +3 xrh030412 2026-04-01 3/150 2026-04-03 14:40 by 氮气气气
[硕博家园] 求老师收留 +9 lllq123 2026-04-03 9/450 2026-04-03 13:48 by 呼吸都是减肥
[考研] 316求调剂 +14 舟自梗 2026-04-01 18/900 2026-04-03 10:28 by linyelide
[考研] 286求调剂 +7 Faune 2026-03-30 7/350 2026-04-03 10:14 by linyelide
[考研] 273求调剂 +20 李芷新1 2026-03-31 20/1000 2026-04-03 09:58 by linyelide
[考研] 0856初试324分求调剂 +6 想上学求调 2026-04-01 6/300 2026-04-02 11:42 by 星空星月
[硕博家园] 博一被送出联培感觉不适应怎么办 +3 全村的狗 2026-03-31 3/150 2026-04-01 10:44 by 328838485
[考研] 求调剂，一志愿北林食品与营养095500，301分，已过六级，有科研经历 +4 快乐储蓄罐 2026-03-31 4/200 2026-04-01 09:26 by JourneyLucky
[考研] 材料专硕 085600求调剂 +7 BBQ233 2026-03-30 7/350 2026-03-30 17:44 by oooqiao
信息提示
关闭
请填处理意见
关闭