题目23：算出所有不能写成两个过剩数之和的正整数之和,欧拉计划（Project Euler）,数据结构与算法,鱼C论坛

欧拉计划 发表于 2015-4-23 16:30:20

题目23：算出所有不能写成两个过剩数之和的正整数之和

Non-abundant sums

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
题目：

如果一个数的所有真因子之和等于这个数，那么这个数被称为完全数。例如，28 的所有真因子之和为 1 + 2 + 4 + 7 + 14 = 28，所以 28 是一个完全数。

如果一个数的所有真因子之和小于这个数，称其为不足数，如果大于这个数，称其为过剩数。

12 是最小的过剩数，1 + 2 + 3 + 4 + 6 = 16。因此最小的能够写成两个过剩数之和的数字是 24。经过分析，可以证明所有大于 28123 的数字都可以被写成两个过剩数之和。但是这个上界并不能被进一步缩小，即使我们知道最大的不能表示为两个过剩数之和的数字要比这个上界小。

找出所有不能表示为两个过剩数之和的正整数之和。

Plusenxue 发表于 2016-8-27 19:28:57

def isguoshen(x):
n = 0
for i in range(1,x):
   if x%i == 0:
         n += i

if n > x:
   return True
else:
   return False

guoshen = []
guoshenhe = {0}

for i in range(12,14062):
if isguoshen(i):
   guoshen.append(i)

for i in range(3490):
for j in range(i,3490):
   guoshenhe.add(guoshen+guoshen)

愤怒的大头菇 发表于 2016-8-29 22:07:42

import math

def Full(x):
list1 =
for i in range(2,int(math.sqrt(x)+1)):
   if x % i == 0:
         list1.append(i)
         if x/i not in list1:
            list1.append(x/i)

if sum(list1) > x:
   return True
else:
   return False
list1 = []
for i in range(1,28111):
if Full(i):
   list1.append(i)
list2 = {0}
for i in range(6961):
for n in range(i,6961):
   list2.add(list1+list1)
list3=[]
for i in range(1,28123):
if i not in list2:
   list3.append(i)

print(sum(list3))
结果是4179871，10秒不到出结果

jerryxjr1220 发表于 2016-9-20 17:18:28

本帖最后由 jerryxjr1220 于 2016-10-11 23:17 编辑

优化了算法，用标记法，只要2秒多就出结果
4179871

def y(n):
lst =
for i in range(2,int(n**0.5+1)):
if n%i == 0:
lst.append(i)
lst.append(int(n//i))
lst = list(set(lst))
return lst

master =
for j in range(1,28124):
if j == 1:
master = 1
elif j == 2:
master = 1
else:
master = sum(y(j))
abundant = []
for k in range(1,28124):
if k < master:
abundant.append(k)
not_abundant =
for i, a in enumerate(abundant):
for b in abundant:
if a+b < 28124:
not_abundant = 0
else:
break # no need to go further
print sum(not_abundant)

芒果加黄桃 发表于 2017-1-11 22:05:59

本帖最后由芒果加黄桃于 2017-1-11 22:08 编辑

# encoding:utf-8
# 过剩数
from time import time
N = 28123
def getFactorsSum(N):
l_result =
for t in range(2, int(N ** 0.5) + 1):
   if N % t == 0:
         l_result.append(t)
         l_result.append(N // t);
return sum(list(set(l_result)))
def findAbns():
l_abns = []
for i in range(1, N):
   if getFactorsSum(i) > i:
         l_abns.append(i)
return l_abns
def euler022():
l_temp = []
l_abns = findAbns()
for i in range(0, len(l_abns)):
   for j in range(i, len(l_abns)):
         tmp = l_abns + l_abns
         if tmp > N:
            break
         l_temp.append(tmp)
s_abns = set(l_temp)
s_all = set(i for i in range(1, N + 1))
l_result = list(s_all - s_abns)
l_result.sort()
return l_result

if __name__ == '__main__':
start = time()
print(sum(euler022()))
print('cost %.6f sec' % (time() - start))

4179871
cost 4.461165 sec

渡风发表于 2017-1-21 23:43:43

此代码使用matlab编程
Problem23所用时间为4.2954秒
Problem23的答案为4179871
%% Problem23
% 题目23：算出两个不能够被两个过剩数之和表示的所有正整数之和
function Output=Problem23(Input)
tic
if nargin==0
Input=28123;
end
Abundant=[];
for ii=2:Input
if sum(Factor_Rank(ii))>ii
   Temp=;
   Abundant=Temp;
end
end
L=length(Abundant);
Result=1:Input;
for jj=1:L
Result=setdiff(Result,Abundant+Abundant(jj));%巧妙，将2重循环变为单重循环
end
Output=sum(Result);
toc
disp('此代码使用matlab编程')
disp(['Problem23所用时间为',num2str(toc),'秒'])
disp(['Problem23的答案为',num2str(Output)])
end
%% 子程序
%输入一个数，得到其真因子序列，顺序排列，入10，--1,2,5..
function Output=Factor_Rank(Input)
if nargin==0
Input=12;
end
Node=floor(sqrt(Input));
Factor=[];
if Node*Node==Input
Factor=Node;
Middle=Node-1;%最中间的约数
else
Middle=Node;
end
for ii=Middle:-1:2
if mod(Input,ii)==0
   Temp=;
   Factor=Temp;
end
end
Output=;
end

99592938 发表于 2017-3-15 14:55:41

import time
st = time.clock()
def isabundant(x):
sum0=1
for i in range(2,int(x**0.5)+1):
   if not x%i:
         if x==i**2:sum0+=i
         else:sum0+=i+x//i
if sum0>x:return 1
else:return 0

l_ab=[]
dic_n={}
for n in range(1,28124):
if isabundant(n):
   l_ab.append(n)
dic_n=n
for i in l_ab:
for j in l_ab:
   if i+j in dic_n:
         del dic_n
print(sum(list(dic_n.values())))
et = time.clock()
print('read:%.3f s' %(et-st))
>>>
4179871
read:13.530 s

由我们主宰 发表于 2018-3-18 18:36:43

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int Judeg(int x)
{
int i,sum=0;
for(i=1;i<x;i++)
{
if(0==x%i)
{
sum=sum+i;
}
}
if(sum>x)
{
return 1;
}
else
{
return 0;
}
}
int main()
{
int i,j,n,leap;
double s=0;
clock_t start,end;
start=clock();
for(n=1;n<=28123;n++)
{
leap=1;
for(i=12;i<=n/2;i++)
{
j=n-i;
if(Judeg(i)&&Judeg(j))
{
leap=0;
break;
}
}
if(leap)
{
s=s+n;
printf("%d\t",n);
}
}
end=clock();
printf("\n本次计算用时%f秒\n",(double)(end-start)/CLK_TCK);
printf("%f\n",s);
system("pause");
return 0;
}

hvagab 发表于 2018-4-22 22:18:55

from math import sqrt

import time

st = time.time()
def f(n):
l= set()
for i in range(1,int(sqrt(n))+1):
   if n % i ==0:
         j = n//i
         l.add(i)
         l.add(j)

return sum(l-{n})

def g(n):
if f(n)>n:
   return n
else:
   return 0

lis= []
for i inrange(12,28123):
if g(i) !=0:
   lis.append(g(i))

print(lis)
lis1 = set()
for ii in lis:
for j in lis:
   lis1.add(ii+j)

lis2 = []
for p in range(1,28123):
if p not in lis1:
   lis2.append(p)
print(sum(lis2))
print(time.time() - st)

hvagab 发表于 2018-4-22 22:19:29

4179871 9s

k往事如烟k 发表于 2019-3-25 14:37:28

本帖最后由 k往事如烟k 于 2019-3-25 14:38 编辑

测试

cwhsmile 发表于 2019-4-27 01:27:12

本帖最后由 cwhsmile 于 2019-4-27 12:44 编辑

方法不好，需要优化的地方多，列表对于超过一万以上的长度不建议用，最好用字典，长度低了就用列表。
慢慢的发现，思维方式不同，做出的结果可以差很多倍。
import time
import math

def test1():
num = []
for m in range(2,28124):
   li =
   for n in range(2,int(m**0.5)+1):
         if m%n == 0:
            li.append(n)
            li.append(int(m/n))

   if sum(set(li)) > m:
         num.append(m)
long = len(num)
print(long)
print(num[-10:])
b = []
for n in range(long):
   for i in range(n,long):
         temp = num+num
         if temp < 28124:
            b.append(temp)
         else:
            break

print(b[-10:])
result = 0
b = set(b)
print(len(b))
for j in range(1,28124):
   if j in b:
         continue
   result += j
return result

li = []
start = time.perf_counter()
print(test1())
end = time.perf_counter()
print(end-start)

上面的代码运行了5秒多，下面是改进的代码，把列表换成了字典，把过剩数相加的取值范围缩减了一下，3秒多运行完毕。
import time
import math

def test1():
num = []
for m in range(2,28124):
   li =
   for n in range(2,int(m**0.5)+1):
         if m%n == 0:
            li.append(n)
            li.append(int(m/n))
   if sum(set(li)) > m:
         num.append(m)

long = len(num)
dict1 = {}
for a in range(28124):
   dict1 = 1
for n in range(long//2):
   for i in range(n,long-n):
         temp = num+num
         dict1 = 0

result = 0
for j in range(28124):
   if dict1 == 1:
         result += j
return result
li = []
start = time.perf_counter()
print(test1())
end = time.perf_counter()
print(end-start)

王小召 发表于 2019-6-6 10:54:10

结果：4179871
用时：5.985732424725128import time
import math

def guosheng():
gs_l = []
for i in range(12, 28123):
   tmp = []
   for x in range(2, int(math.sqrt(i) + 1)):
         if not i % x:
            tmp.append(x)
            tmp.append(int(i/x))
   if sum(set(tmp)) > i-1:
         gs_l.append(i)

return sum(range(28124)) - sum(set( + gs_l for n1 in range(len(gs_l)) for n2 in range(n1, len(gs_l)) if gs_l + gs_l < 28124]))

start = time.clock()
print("结果：{}\n用时：{}".format(guosheng(), time.clock()-start))

永恒的蓝色梦想 发表于 2019-7-22 21:18:02

本帖最后由永恒的蓝色梦想于 2020-9-11 13:45 编辑

None

debuggerzh 发表于 2020-8-4 17:13:10

4179871

Process returned 0 (0x0) execution time : 0.824 s
Press any key to continue.
暴力打表，先求出1~28123的所有过剩数，再二层循环枚举两过剩数之和
以下为关键代码
const int M = 28123 + 1;
const int M_RANGE = 7000 + 5;

int abundant;
int vis = {0};

int main(){

int cnt = 0,ans = 0;

for (int i = 1;i < M;i++){
int factor_sum = 0;
for (int j = 1;j <= i/2;j++)
   if (i % j == 0) factor_sum += j;
if (factor_sum > i) abundant = i;
}

for (int i = 0;i < cnt;i++)
for (int j = i;j < cnt;j++){
   int sum = abundant + abundant;
   if (sum < M && !vis) vis = 1;
}

for (int i = 0;i < M;i++)
if (!vis) ans += i;

cout << ans << endl;
return 0;
}

guosl 发表于 2022-1-2 20:45:04

/*
答案：4179871
耗时：0.0097935秒
*/
#include <iostream>
#include <cmath>
using namespace std;

char a;//打表，a=1表示i是一个过剩数

bool is_abundant(int k)//计算k是否是一个过剩数
{
int d = (int)sqrt((double)k);
int s = 1;
for (int i = 2; i <= d; ++i)
{
if (k % i == 0)
{
   int n = k / i;
   if (i == n)
   s += i;
   else
   s += i + n;
}
}
return (s > k);
}

int main(void)
{
int nS = 0;
for (int i = 1; i < 28124; ++i) //打表
{
if (is_abundant(i))
   a = 1;
}
for (int i = 1; i < 28124; ++i)
{
bool bFlg = true;
for (int j = 1; j <= (i >> 1); ++j) //枚举i的拆分
{
   if (a == 1 && a == 1)
   {
   bFlg = false;
   break;
   }
}
if (bFlg)
   nS += i;
}
cout << nS << endl;
return 0;
}

叶落了 发表于 2023-6-21 11:10:55

cwhsmile 发表于 2019-4-27 01:27
方法不好，需要优化的地方多，列表对于超过一万以上的长度不建议用，最好用字典，长度低了就用列表。
慢慢 ...

过剩数相加的取值范围缩减了一下，具体有什么原理吗，我感觉好像不能完全覆盖。如果数据很大的话

叶落了 发表于 2023-6-21 11:11:37

#include<stdio.h>
#include<math.h>

int determine(int i);//求质因数之和
int determine(int i)
{
int k;
int sum1=0;

for(k=1;k<=pow(i,1.0/2);k++)
{
if(i%k==0&&i/k!=k)
{
sum1=sum1+k+i/k;
}
if(i%k==0&&i/k==k)
{
sum1=sum1+k;
}
}
sum1=sum1-i;
if(sum1>i)
{
return sum1;
}
else
{
return 0;
}
}

int main(void)
{
int k=0,i,m;
long int sum0=0;//前28213的和
int array={0};//储存过剩数
int count=0;//过剩数的数量
long int sum1=0;

for(i=1;i<=28213;i++)
{
sum0=sum0+i;
}
printf("%lld\n",sum0);
for(i=12;i<=28213;i++)
{
if(determine(i))
{
array=i;
count++;
k++;
}
}
printf("%d\n",count);
for(i=24;i<=28213;i++)
{
for(m=0;array<=i;m++)//这里不用<=(i-array),因为我曾经犯过错。除非你赋值
{
if(determine((i-array)))
{
sum1=sum1+i;
break;
}
}
}

printf("%lld\n",sum1);

printf("所有不能表示为两个过剩数之和的正整数之和为%d\n",(sum0-sum1));

return 0;
}

mathtimes 发表于 2023-10-10 11:46:21

4179871 0.5s
fn factors(x: i32) -> Vec<i32> {
let mut pt: Vec<i32> = vec!;
let mut x_sq = (x as f32).sqrt() as i32;
if x == x_sq * x_sq && x > 1 {
   pt.push(x_sq);
   x_sq -= 1;
}
for i in 2..=x_sq {
   if x % i == 0 {
         pt.push(i);
         pt.push(x / i);
   }
}
pt
}

fn main() {
let mut abundant = Vec::new();
for i in 1..=28123 {
   if factors(i).iter().sum::<i32>() > i {
         abundant.push(i);
   }
}
let mut number_table: Vec<bool> = vec!;
for i in &abundant {
   for j in &abundant {
         if i + j < 28124 {
            number_table[(i + j) as usize] = false;
         }
   }
}
println!(
   "{}",
   number_table
         .iter()
         .enumerate()
         .map(|(i, &x)| if x { i as i32 } else { 0 })
         .sum::<i32>()
)
}

页: [1]

鱼C论坛's Archiver

题目23：算出所有不能写成两个过剩数之和的正整数之和