求n 的因子个数

  • 时间:
  • 浏览:
  • 来源:互联网

线性筛求n 的因子个数;

#include<stdio.h>
#define MAX_N 100
int prime[MAX_N + 5];
int fac[MAX_N + 5];//i 的因子个数;
int cunt[MAX_N + 5];// i 的 最小素因子的幂次;

void init() {
    for(int i = 2; i <= MAX_N; i++) {
        if(!prime[i]){
            prime[++prime[0]] = i;
            fac[i] = 2;
            cunt[i] = 1;
        }
        for(int j = 1; j <= prime[0]; j++){
            if(i * prime[j] > MAX_N) break;
            prime[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                fac[i * prime[j]] = fac[i] / (cunt[i] + 1) * (cunt[i] + 2);
                cunt[i * prime[j]] = cunt[i] + 1;
            }
            else {
                fac[i * prime[j]] = fac[i] * fac[prime[j]];
                cunt[i * prime[j]] = 1;
            }
        }
    }
    return ;
}
int main() {
    init();
    for(int i = 2; i <= MAX_N; i++){
        printf("fac[%d] = %d\n", i, fac[i]);
    }
    return 0;
}

本文链接http://www.dzjqx.cn/news/show-617414.html