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

# -*- 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

#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;
}

4179871

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 ...

#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< }

4179871

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

#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;
}

# -*- 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

# -*- 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

Originally posted by holmescn at 2011-06-06 13:32:43:
使用了wangww2011的算法，现在还是需要14秒多。

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

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 ...