诡异的因数

　

因数

原题题址

题目描述

四舍五入下成功率，大概就是百分之百的样子。

——韩信-逐梦之影

小T喜欢玩数。这天他弄到了一个数n，他玩心大发，他让小s求它的正因数数量。

小s并不会这道题，现在如果你是他，你会怎么做？

小T为了防止小s作弊，他要询问T次。

输入描述:

第一行一个整数T。

后T行每行一个整数n。

输出描述:

T行一个整数代表答案。

示例1

输入

1
6

输出

4

说明

6的因数有1 2 3 6共4个

100% 1≤n,T≤104

显然最直接想到最小约数定理，先筛素数一下，再通过分解N，

$N=p_1^{a_1}+p_2^{a_2}+\mathrm{.}\mathrm{.}\mathrm{.}+p_n^{a_n}$N=p1a1​​+p2a2​​+...+pnan​​

那么${\prod }_{i=1}^n(a_i+1)$∏i=1n​(ai​+1)即为约数个数。

代码：

#include"iOStream"
using namespace std;
int a[10000],cnt = 0;
bool p[10000+5];
int main(){
    for(int i = 2;i <= 10000;i++){//素数筛
        if(!p[i]){
             a[cnt++]=i;
            for(int j = i;j <= 10000;j+=i)p[j]=1;
        }  
}
    int T;
    cin >> T;
    while(T--){
        int i = 0,p,ans = 1;
        cin >> p;
      while(p>1){
          int Num = 0;
          while(p%a[i]==0&&i<cnt)p/=a[i],Num++;
              i++;
          ans*=(Num+1);
      }
        cout << ans <<endl;
    }
    
}

素数筛其实可以直接做，不判重地筛，筛到一次就意味着有一个因数，记录刷到的次数即可。

memset(ans,0,sizeof(ans));
for(int i = 1;i <= N;i++){//ans即为因数数组。
  for(int j = 1;j*i <= N;j++)
      ans[j*i]++; 
  }

文章最后发布于: 2019-06-16 16:19:16

相关阅读

质因数

# include<iostream> # include<cmath> using namespace std; void zys(int n) { cout<<n<<"="; int k=sqrt(n); int i=2; w

【C语言】最大公因数

#include<stdio.h> int main(){ int a,b; printf("请输入a b:"); scanf("%d%d",&a,&b); while(b!=0){ int temp=a%b; a=

质因数分解

算术基本定理：任何一个大于 1 的整数都能唯一分解为有限个质数的乘积。 试除法：结合质数质数判定的“试除法”和质数筛选的“Eratos

求两个数最大公因数的c语言程序

对于这个问题,我能想到的方法有三种: ①先找出这两个数中最小的那个,可以用i表示,然后用这两个数依次对i取余. 同时i不断减1,直到

【C】质因数的个数

题目描述 求正整数N(N>1)的质因数的个数。相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。 输入描述: 可能有多组测