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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第廿三题：
171/2返回列表12下一页
查看: 2214  |  回复: 16
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 4 个 程序强帖 ，点击这里进行查看

holmescn

金虫 (正式写手)

[交流] Euler 工程 第廿三题： 已有5人参与

完美数是指一个数的所有因子的和还是这个数。比如28＝1+2+4+7+14.
如果所有因子的和小于这个数，就称它为“贫数”。反之，如果所有因子的和大于这个数，则称之为“富数”。

比如12是最小的“富数”，因为 1+2+3+4+6=16>12. 最小的可以写为两个“富数”的和的数是24. 由数学分析可知，任何大于28123的整数都可以写成一个两个“富数”的和。但是，这个上限不能继续缩小了，显然已经知道最大的不能写成两个“富数”的和的数要比这个数小。

那么，所有不能写成两个“富数”的和的正整数的和是多少呢？

[ Last edited by holmescn on 2011-6-5 at 23:34 ]
回复此楼

» 猜你喜欢
1楼 2011-06-05 22:13:04
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★
dubo(金币+1): 多谢交流 2011-06-06 14:41:22
微尘、梦想(程序强帖+1): 鼓励多交流！ 2011-06-06 20:16:22
修改版1
CODE:
# -*- coding: utf-8 -*-

from math import sqrt
from timeit import timeit

def abundantGen():
    "生成一个富数列表"
    abundant = []
    n = 12

    while n < 28123:
        factors = [1]
        sqrtn = int(sqrt(n))
        for i in range(2,sqrtn+1):
            if n % i == 0:
                factors.append(i)
                if n / i != i:
                    factors.append(n/i)

        if sqrtn*sqrtn == n:
            factors.remove(sqrtn)

        if sum(factors) > n:
            abundant.append(n)
        n += 1

    return abundant

def euler23():
    # 一个“富数”列表
    abundant = abundantGen()
    n = 1
    s = 0

    while n < 28123:
        flag = False
        for i in abundant:
            if i > n: break
            try:
                # 如果n-i在列表内，那么n就可以分成两个
                # “富数”的和
                abundant.index(n-i)
                flag = True
                break
            except:
                continue

        if flag == 0:
            s += n

        n += 1

    print s

if __name__ == "__main__":
    print timeit("euler23.euler23()", "import euler23", number=3)

修改以后，结果好像正常了，但时间太长了。
引用回帖:
result = 4179871
takes 1098.32 s

[ Last edited by holmescn on 2011-6-6 at 11:11 ]
赞一下(2人) 回复此楼
2楼2011-06-05 23:40:25
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+2): 辛苦了 2011-06-06 03:24:33
jjdg(金币+1): 端午节快乐 2011-06-06 03:24:40
微尘、梦想(程序强帖+1): 鼓励多交流！ 2011-06-06 20:16:48
你那个富数列表生成判断有问题,不能判断到sqrt(n),必须从1-n-1
例如int(sqrt(12))==3,但是4也整除12;int(sqrt(28))==5,但是14也整除28

这个用matlab速度太慢了,改c了
CODE:
#include
#include

// compute the sum of all factors
int d(int n)
{
        int s=0;
        int i;
        for(i=2;i                 if(n%i==0)
                        s += i;
       
        return s+1; // 加上1
}

// euler23
int main(int args, char* argv[])
{
        int i, j, sum = 0;
        bool flag = false;
        for(i=1;i<28123;i++)
        {
                flag = false;
                for(j=1;j                 {
                        if(j<(i-j)) // j+(i-j)==i,只判断一次
            {
                if(d(j)>j && d(i-j)>(i-j)) // 如果j和i-j都是abundant number,改变flag结束本次循环
                {
                    flag = true;
                    break;
                }
            }               
                }

                if(!flag) // 不能表示为2个abundant number之和
                {
                        sum += i;
                        printf("%d added.\n",i); // 以为死机了,加这句看输出的
                }
        }
       
        printf("\nResult: %d\n",sum); // 打印结果

        system("PAUSE");
        return 0;
}

结果
CODE:
4179871

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

holmescn

金虫 (正式写手)
★
dubo(金币+1): 多谢交流 2011-06-06 14:44:16
引用回帖:
Originally posted by libralibra at 2011-06-06 01:43:30:
你那个富数列表生成判断有问题,不能判断到sqrt(n),必须从1-n-1
例如int(sqrt(12))==3,但是4也整除12;int(sqrt(28))==5,但是14也整除28

这个用matlab速度太慢了,改c了
[code] #include <stdio.h>
#inc ...

我知道你的意思啊，但我有两个append的啊。也就是说

sqrt(12)=3

i 取了 1 2 3
同时
n/i 取了 12 6 4

晕，我说我的和这么小呢, 原来我取了12了
赞一下(1人) 回复此楼
4楼2011-06-06 08:43:16
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 多谢交流 2011-06-06 14:43:01
余泽成(程序强帖+1): 鼓励交流！ 2011-06-18 15:56:47
C++代码：
CODE:
#include
enum {BUFSZ = 28124};
size_t buf[BUFSZ];   //存放所有约数和
size_t buf2[BUFSZ];  //存放富数值

size_t eular23(){
        for(size_t i = 1; i < BUFSZ; ++i){
                for(size_t j = i+i; j < BUFSZ; j+=i){
                        buf[j] += i;
                }
        }//生成所有数的约数和，这里的复杂度小于O(n*n)，第二步的步数要小于调和级数的那个和
        size_t *p = buf2;
        for(size_t i = 12; i < BUFSZ; ++i){
                if(buf[i] > i)
                        *p++ = i;
        }//提取富数，复杂度是O(n)
        size_t s = 0;
        int t;
        size_t *pt;
        //这里复杂度挺高，上限是O(n*n)，具体也不清楚啥个破东西
        for(size_t i = 1; i < BUFSZ; ++i){
                pt = buf2;
                while(pt < p){
                        t = i;
                        t -= *pt++;
                        if(t <= 0){
                                s += i;
                                break;
                        }
                        if(buf[t] <= t){
                                if(pt == p)
                                        s += i;
                                continue;
                        }
                        break;
                }
        }
        return s;
}
int main(){
        std::cout< }

时间复杂度是不错，就是有点浪费空间，奢侈了。富数的个数是个什么规律也不清楚，清楚的话就可以节省空间了。

[ Last edited by huycwork on 2011-6-6 at 22:48 ]
赞一下(3人) 回复此楼
漩涡的中心有一块空地，空空的。
5楼2011-06-06 09:38:44
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

wangww2011

木虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 多谢交流 2011-06-06 14:43:16
微尘、梦想(程序强帖+1): 鼓励多交流！ 2011-06-06 20:17:26
c 语言版本
先计算出小于28123的所有abundant number，然后再组合出所有可分解成两个富数的整数，最后再求和
用 time ./euler23的运行结果
CODE:
4179871

real        0m0.137s
user        0m0.132s
sys        0m0.000s

代码
CODE:
#include
#include
#include


int sumdivisors(int n){
        int i,sum=1,sqrtn=sqrt(n);
        for(i=2;i                 if(n%i==0)sum+=i+n/i;
        }
        if(sqrtn*sqrtn==n)sum-=sqrtn;
        return sum;
}

long euler23(int n){
        int i,j,tmp,abn_index=0;
        int abn[n];
        for(i=12;i                 if(sumdivisors(i)>i)abn[abn_index++]=i;
        }
  
        int num[n];
        memset(num,0,sizeof(num));
        for(i=0;i                 for(j=i;j                         tmp=abn[i]+abn[j];
                        if(tmp                         else break;
                }
        }

        long sum=0;
        for(i=1;i                 if(num[i]==0){
                        sum+=i;
                }
        }
        return sum;
}


int main(void){

        printf("%ld\n",euler23(28123));

        return 0;
}

[ Last edited by wangww2011 on 2011-6-6 at 11:45 ]
赞一下(3人) 回复此楼
6楼2011-06-06 11:14:05
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★ ★ ★ ★ ★
dubo(金币+1): 多谢交流 2011-06-06 14:43:28
微尘、梦想(金币+4): 2011-06-06 20:17:53
用二分查找代替了线性查找，效率提高了很多。这个版本大概用时30秒
CODE:
# -*- coding: utf-8 -*-

from math import sqrt
from timeit import timeit

def abundantGen():
    "生成一个富数列表"
    abundant = []
    n = 12

    while n < 28123:
        factors = [1]
        sqrtn = int(sqrt(n))
        for i in range(2,sqrtn+1):
            if n % i == 0:
                factors.append(i)
                if n / i != i:
                    factors.append(n/i)

        if sum(factors) > n:
            abundant.append(n)
        n += 1

    return abundant

def find(self, num):
    first = 0
    end = len(self) - 1
    mid = 0

    if len(self) == 0:
        return False

    while first < end:
        if self[mid] == num:
            return True
        mid = (end + first)/2
        if num > self[mid]:
            first = mid + 1
        elif num < self[mid]:
            end = mid - 1

    if first == end and self[first] == num:
        return True
    return False

def euler23():
    # 一个“富数”列表
    abundant = abundantGen()
    n = 1
    s = 0

    while n < 28123:
        flag = True
        for i in abundant:
            if i > n: break
            # 如果n-i在列表内，那么n就可以分成两个
            # “富数”的和
            if find(abundant, n-i):
                flag = False
                break

        if flag:
            s += n

        n += 1

    print s

if __name__ == "__main__":
    print timeit("euler23.euler23()", "import euler23", number=3) / 3

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

holmescn

金虫 (正式写手)
★ ★ ★ ★
dubo(金币+1): 多谢交流 2011-06-06 14:44:05
微尘、梦想(金币+3): 2011-06-06 20:18:10
使用了wangww2011的算法，现在还是需要14秒多。
CODE:
# -*- coding: utf-8 -*-

from math import sqrt
from timeit import timeit

def abundantGen():
    "生成一个富数列表"
    abundant = []
    n = 12

    while n < 28123:
        s = 0
        sqrtn = int(sqrt(n))
        for i in range(2,sqrtn+1):
            if n % i == 0:
                s += i
                if n / i != i:
                    s += n/i

        if s > n:
            abundant.append(n)
        n += 1

    return abundant

def euler23():
    # 一个“富数”列表
    abundant = abundantGen()
    sumOfAbundants = set()

    for i in abundant:
        for j in abundant:
            sumOfAbundants.add(i+j)
    s = 0
    for i in range(1, 28123):
        if i not in sumOfAbundants:
            s += i
    print s

if __name__ == "__main__":
    print timeit("euler23.euler23()", "import euler23", number=3) / 3
赞一下(2人) 回复此楼
8楼2011-06-06 13:32:43
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

wangww2011

木虫 (著名写手)
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+3): 鼓励交流！ 2011-06-06 20:18:24
引用回帖:
Originally posted by holmescn at 2011-06-06 13:32:43:
使用了wangww2011的算法，现在还是需要14秒多。

CODE:
for i in abundant:
        for j in abundant:
            sumOfAbundants.add(i+j)
    s = 0
    for i in range(1, 28123):
        if i not in sumOfAbundants:
            s += i

这几行就要十几秒，不知道有什么快速的办法没
关键上面三句 要O(N^2)，下面三句可以改成O(N)
赞一下(2人) 回复此楼
9楼2011-06-06 17:48:33
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 欢迎讨论 2011-06-07 22:45:56
引用回帖:
Originally posted by holmescn at 2011-06-06 13:32:43:
使用了wangww2011的算法，现在还是需要14秒多。
[code]

# -*- coding: utf-8 -*-

from math import sqrt
from timeit import timeit

def abundantGen():
    "生成一个富数列表"
    abun ...

用自己仿matlab的tic/toc计时看了下,主要时间都浪费在中间的双重循环了
赞一下(2人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
10楼2011-06-07 00:26:46
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
171/2返回列表12下一页
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
信息提示
关闭
请填处理意见
关闭