算n因子的个数

最新推荐文章于 2022-03-19 15:24:30 发布

HQD因为有趣所以做题

最新推荐文章于 2022-03-19 15:24:30 发布

阅读量3.5k

点赞数

分类专栏： ACM_数论文章标签： n2 算法

本文链接：https://blog.csdn.net/hqd_acm/article/details/5800817

版权

ACM_数论专栏收录该内容

29 篇文章

订阅专栏

这种题目以前就曾经做过，但是这次在做又忘了怎么写，在这里做个总结，任意一个数n都可以表示成p1^n1*p2^n2*p3^n3..........(p1,p2....是n的素因子，n1,n2是p1,p2的个数)，n因子的个数就num=（n1+1）*(n2+1)*........

所以我们在算因子个数的时候，就要先筛素数，筛素数的方法有很多种，效率也都不一样，用不同的方面也影响着后面算n1,n2....同样也影响后来算num的效率

这里有一种的算法。。。

void make_prime()
{
   pn=0;
   for(int i = 2; i < N; i++){
          if(!pt[i]) pr[pn++]=i, pt[i]=i;
           for(int j=0; j < pn && pr[j]*i < N; j++){
                 pt[pr[j]*i] = pr[j];
              if(i % pr[j] == 0) break;
             }
      }
}

int solve(int n)
{
     int ans=1;
      while (n!=1)
     {
           int t=0;
         int k=pt[n];
           while (!(n%k))
        {
             n/=k;
             t++;
        }
       ans*=t+1;
   }
    return ans;
}