[½»Á÷] 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 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:
        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 ...