关于约数个数的两种解法

1.代码清晰，简单，易懂
 链接：https://www.nowcoder.com/questionTerminal/04c8a5ea209d41798d23b59f053fa4d6
来源：牛客网
#include
using namespace std;
int numOfDivisor(int num)
{
    int ans = 0;
    int i;
    if(num==1)//原代码当num=1时会出现错误，这里是我自己修改的
    {
        ans=1;
        return；
    }
    for (i = 1; i*i<num; i++)//和i<sqrt(num)原理相同
    {
        if (num%i == 0)
            ans += 2;//因为能整除，所以有两个因数，另外一个肯定大于i
    }
    if (i*i == num) ans++;//如，16=4*4，前面i的范围是1-3，i=4时跳出了循环，所以后面要再判断如果4*4=16了，约数个数再加1
    return ans;
}
int main()
{
    int n, num;
    while (cin >> n)
    {
        for (int i = 0; i<n; i++)
        {
            cin >> num;
            cout << numOfDivisor(num) << endl;
        }
    }
    return 0;
}

2.复杂的质因数的分解法，如24=2^3*3，所以它的约数个数为（3+1）*（1+1）=8

#include<iostream>//修改后的版本，防止内存溢出
#include<cmath>
using namespace std;
unsigned int  a[1000];
int sum[1000];
int j,sum1;
void init()
{
    for (int i = 0; i < 1000; i++)
    {
        a[i] =sum[i]= 0;
         
    }
}
void set(int x)
{
    init();
    for (int i = 0; i < x; i++)
        cin >> a[i];
}
 
void getprimecnt(int x)
{
    
    int cout ;
    for (int i = 0; i < x; i++)
    {
        cout = 0;
        sum1 = 1;
        if (a[i] == 1)//同样对1单独输出
        {
            sum[i] = sum1;
            continue;
 
        }
             
        int k =(int)sqrt(a[i])+1;
        for (j = 2; j < k; j++)//质因数分解
        {
            cout = 0;
            while (a[i] % j == 0)
            {
                cout++;//质因数的指数
                a[i] /= j;
            }
            sum1 *= (cout+1);//指数的乘积
            if(a[i]==1)
                 break;
        }
        if (a[i] != 1)//如果通过了前面质因数的分解后，num还没分解为1，说明num本身是一个质数，经历上面的分解过程没有改变num的值，因为分解范围是2-sqrt(num),
            sum1*= 2;//所以他的因数是1和它本身，为2；
        sum[i] = sum1;
    }
}
void output(int x)
{
    
 
    for (int i = 0; i < x; i++)
    {
        
        cout << sum[i] << endl;
    }
 
}
int main()
{
    int n;
    while (cin >> n)
    {
        set(n);
        getprimecnt(n);
        output(n);
    }
    return 0;
}

代码学习笔记文章被收录于专栏

学习笔记，pat,牛客