博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Project Euler 23 Non-abundant sums( 整数因子和 )
阅读量:5842 次
发布时间:2019-06-18

本文共 2195 字,大约阅读时间需要 7 分钟。


题意:

完全数是指真因数之和等于自身的那些数。例如,28的真因数之和为1 + 2 + 4 + 7 + 14 = 28,因此28是一个完全数。

一个数n被称为亏数,如果它的真因数之和小于n;反之则被称为盈数。

由于12是最小的盈数,它的真因数之和为1 + 2 + 3 + 4 + 6 = 16,所以最小的能够表示成两个盈数之和的数是24。通过数学分析可以得出,所有大于28123的数都可以被写成两个盈数的和;尽管我们知道最大的不能被写成两个盈数的和的数要小于这个值,但这是通过分析所能得到的最好上界。

找出所有不能被写成两个盈数之和的正整数,并求它们的和。

思路:此题与欧拉21题相似


/*************************************************************************    > File Name: euler023.c    > Author:    WArobot     > Blog:      http://www.cnblogs.com/WArobot/     > Created Time: 2017年06月30日 星期五 19时30分05秒 ************************************************************************/#include 
#include
#define MAX_N 28123int32_t isPrime[MAX_N + 10] = {0}; // 记录最小素数幂次方isPrime[24] = 8 (2^3)int32_t prime[MAX_N + 10] = {0}; // 记录素数int32_t d[MAX_N + 10] = {0}; // 记录整数分解约数和int32_t abundantSum[MAX_N + 10] = {0};int32_t vis[MAX_N + 10] = {0};void Init() { for (int32_t i = 2 ; i <= MAX_N ; i++) { if (!isPrime[i]) { isPrime[i] = i; prime[++prime[0]] = i; d[i] = i + 1; } for (int32_t j = 1 ; j <= prime[0] ; j++) { if (i * prime[j] > MAX_N) break; if (i % prime[j] != 0) { // 在prime[j]还小于i的最小素因子时 isPrime[i * prime[j]] = prime[j]; d[i * prime[j]] = d[i] * d[prime[j]]; } else { isPrime[i * prime[j]] = isPrime[i] * prime[j]; d[i * prime[j]] = d[i] * (isPrime[i] * prime[j] * prime[j] - 1) / (isPrime[i] * prime[j] - 1); break; } } } for (int32_t i = 1 ; i <= MAX_N ; i++) { d[i] -= i; if (d[i] <= i) continue; abundantSum[++abundantSum[0]] = i; } for (int32_t i = 1 ; i < abundantSum[0] ; i++) { for (int32_t j = i + 1 ; j <= abundantSum[0] ; j++) { if (abundantSum[i] + abundantSum[j] > MAX_N) continue; vis[abundantSum[i] + abundantSum[j]] = 1; } }}int32_t main() { Init(); int32_t sum = 0; for (int32_t i = 1 ; i <= MAX_N ; i++) { if (vis[i]) continue; sum += i; } printf("%d\n",sum); return 0;}

转载于:https://www.cnblogs.com/WArobot/p/7100502.html

你可能感兴趣的文章
js冒泡排序
查看>>
第一次作业 4班卢炳武
查看>>
抽象类的调用
查看>>
使用硬盘,安装双系统,Win7+CentOS
查看>>
Javascript学习总结
查看>>
php 用正则替换中文字符一系列问题解决
查看>>
ActiveMQ应用笔记一:基本概念&安装
查看>>
大话数据结构之四(串)
查看>>
加热炉简是新来的整个系统的板
查看>>
Mockito使用注意事项
查看>>
[LeetCode] Palindrome Linked List 回文链表
查看>>
UVA - 825Walking on the Safe Side(dp)
查看>>
评论:人才流失强力折射出现实畸形人才观
查看>>
git服务器gitlab之搭建和使用--灰常好的git服务器【转】
查看>>
基于机器学习的web异常检测——基于HMM的状态序列建模,将原始数据转化为状态机表示,然后求解概率判断异常与否...
查看>>
虚拟运营商10月或大面积放号 哭穷背后仍有赢家
查看>>
分布式光伏发电建设中的逆变器及其选型
查看>>
UML中关联,组合与聚合等关系的辨析
查看>>
《大数据管理概论》一3.2 大数据存储与管理方法
查看>>
ios的google解析XML框架GDataXML的配置及使用
查看>>