數(shù)論中，若一個(gè)正整數(shù)除了本身之外所有因子之和比此數(shù)自身小，則稱此數(shù)為虧數(shù)。虧數(shù)（Deficient number）也稱為缺數(shù)，參見百度百科_虧數(shù)，或參見維基百科的Deficient number。虧數(shù)在OEIS中的數(shù)列號為A005100。

問題描述：輸入n（n≤40000000），計(jì)算輸出≤n的所有虧數(shù)，每個(gè)數(shù)之間用空格隔開，輸出在一行里。

問題分析：可以使用篩選法原理計(jì)算各個(gè)數(shù)的因子之和，然后再判定輸出。

程序說明：數(shù)組sum[]中存放除了自身之外的因子之和，例如sum[i]中存放除了i以外的i的因子之和。

AC的C語言程序如下：

/* I00037 虧數(shù)（Deficient number） */#include <stdio.h> #include <memory.h>#define MAXN 40000000int sum[MAXN+1];void maketable(int n) {memset(sum, 0, sizeof(sum));sum[1] = 0;int i=2, j;while(i<=n) {sum[i]++;j = i + i; /* j=ki, k>1 */while(j <= n) {sum[j] += i;j += i;}i++;} }int main(void) {int n, flag, i;scanf("%d", &n);maketable(n);flag = 0;for(i=1; i<=n; i++)if(sum[i] < i) {if(flag)printf(" ");flag = 1;printf("%d", i);}printf("\n");return 0; }

運(yùn)行實(shí)例：

99
1 2 3 4 5 7 8 9 10 11 13 14 15 16 17 19 21 22 23 25 26 27 29 31 32 33 34 35 37 38 39 41 43 44 45 46 47 49 50 51 52 53 55 57 58 59 61 62 63 64 65 67 68 69 71 73 74 75 76 77 79 81 82 83 85 86 87 89 91 92 93 94 95 97 98 99

轉(zhuǎn)載于:https://www.cnblogs.com/tigerisland/p/7564323.html

總結(jié)

以上是生活随笔為你收集整理的I00037 亏数（Deficient number）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。