首页 > 其他 > 详细

求一个数的约数个数 d(n)

时间:2019-05-15 21:10:21      阅读:186      评论:0      收藏:0      [点我收藏+]

方法一:筛法

for(int i = 1; i <= n; ++i)
    for(int j = 1; i * j <= n; ++j)
        d[i * j]++;

方法二:质因数分解

若A|B 则

a1<=b1,a2<=b2···an<=bn (a,b分别指正数A,B的质因数)

则A可取 (0~a1)*(0~a2)*···*(0~an)

即 (a1+1)*(a2+1)*···*(an+1)

#include <cstdio>
#include <cstring>
#define N 100001

int n,p;
bool mark[N];
int prime[N];

void get_prime(){
    for(int i = 2; i <= N;++i){
        if(!mark[i]) prime[++p] = i;
        for(int j = 1; j <= p; ++j){
            if(i * prime[j] > N) break;
            mark[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

int get(int n1){
    int w1[N];
    memset(w1, 0, sizeof(w1));
    for(int i = 1; prime[i] <= n1; ++i){
        while(n1 % prime[i] == 0){
            w1[i]++;
            n1 = n1 / prime[i];
        }
    }
    int ans = 1;
    for(int i = 1; i <= p; ++i) ans = ans * (w1[i] + 1);
    return ans;
}

int main(){
    get_prime();
    printf("%d", get(36));
    //for(int i = 1; i <= p; ++i) printf("%d ", prime[i]);
    return 0;
}

 

 

求一个数的约数个数 d(n)

原文:https://www.cnblogs.com/Adventurer-H/p/10872149.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!