c语言高效求一个数的约数和

答案:4 悬赏:0

解决时间 2021-01-23 21:19

提问者网友：姑娘长的好罪过
2021-01-23 16:38

c语言高效求一个数的约数和

最佳答案

二级知识专家网友：不甚了了
2021-01-23 17:11

//#include "stdafx.h"//vc++6.0加上这一行.
#include "stdio.h"
int main(void){
    int a,b,i,x,y,f,n;
    printf("Enter a & b(int)...
");
    scanf("%d%d",&a,&b);
    for(n=a;n<=b;n++){
        for(x=1,n&1 ? (i=3,f=2) : (i=2,f=1);(a=i*i)<=n;i+=f)
            if(!(n%i))
                (x+=i)+= a!=n ? n/i : 0;
        for(y=1,x&1 ? (i=3,f=2) : (i=2,f=1);(a=i*i)<=x;i+=f)
            if(!(x%i))
                (y+=i)+=a!=x ? x/i : 0;
        if(y==n && y!=x)
            printf("%d %d
",n,x);
    }
    return 0;
}追问
追答不明白你在追问什么。图片也看不清。给你一个执行结果参考……

全部回答

1楼网友：枭雄戏美人
2021-01-23 19:42

O（sqrt（n））复杂度还不够吗

2楼网友：想偏头吻你
2021-01-23 18:23

求解这个问题的算法是：
给出n后，枚举比他小的因子f，然后累加起来；
其中可以优化，并实现高效的是——枚举因子。
最简单的枚举因子是从[2, n-1]一个一个枚举；
但我们小学数学就学过“分解质因数”——将一个合数分解成一系列质数乘积的形式，这些单个的质数当然也是该数的因子，好像叫“质因子”，而其他因子可以看作是质因子序列中选出若干个的乘积。
如果真要“高效”，可以使用上面的思路。
然后是，另外一个优化在“分解质因数”过程中。分解质因数，需要枚举质数，枚举质数最高效的是“打表法”——即先把需要的质数用程序算出了，写死到代码里（数组），下次就不用再计算了。

3楼网友：持酒劝斜阳
2021-01-23 17:38

1、首先调用，设置状态静态寄存器初值，计数静态寄存器初值;2、调用一次，检测一次，对比前次的静态变量，不同则计数增1后反回，相同则清除计数返回;3、再调用一次，检测一次，对比前次的静态变量，不同则计数增1后反回，相同则清除计数返回;4、最后调用一次，检测一次，作对比，相同则清除计数，不同则修改要更新的变量，改变状态静态变量，清除计数器，返回。追问

数据范围0<=a

我要举报

如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！