題目描述

對(duì)于任意給定的一個(gè)正整數(shù)，計(jì)算其因數(shù)個(gè)數(shù)。

輸入樣例：

6

輸出樣例：

4

說(shuō)明：

1、2、3、6都是6的因數(shù)。因此，輸出4。

輸入

輸入正整數(shù)N。

輸出

輸出N的因子個(gè)數(shù)。

樣例輸入

6

樣例輸出

4

數(shù)據(jù)范圍限制

1<=N<2^31

提示

1、2、3、6都是6的因數(shù)。因此，輸出4。

分析

結(jié)合題面和樣例發(fā)現(xiàn)，求得是數(shù)字的因子的個(gè)數(shù)。一種樸素的方法就是遍歷所有1~N范圍內(nèi)的值，找出所有的x的因子，進(jìn)行統(tǒng)計(jì)。
若a是b的因子，應(yīng)當(dāng)滿足b%a==0。

結(jié)構(gòu)

int cnt=0;
for(int i=1;i<=n;i++){
  if(n%i==0) cnt++;
}

但是，結(jié)合數(shù)據(jù)范圍分析，能夠發(fā)現(xiàn)，范圍過(guò)大，O(n)級(jí)別的算法會(huì)超時(shí)。此時(shí)就要想辦法優(yōu)化一下。
結(jié)合我們以前做過(guò)的質(zhì)數(shù)判斷的題目，找因子的話實(shí)際上到 $ \sqrt{n} $就夠了，不需要完整的遍歷到n。分析下復(fù)雜度O( $ \sqrt{n} $).n是最大\(2^{31}\) ，開(kāi)根號(hào)后大概是\(10^{4} - 10^{5}\)之間，是在時(shí)間限制內(nèi)的。
對(duì)于根號(hào)的處理要注意 類似25這個(gè)數(shù)字，存在\(5\times5=25\)的情況，因子只要計(jì)算一個(gè)，其他情況下，找到一個(gè)就算兩個(gè)因子。
另外要注意范圍，根號(hào)后范圍接近\(10^5\) ,平方后易超過(guò)int范圍，故使用long long 類型進(jìn)行處理。

代碼實(shí)現(xiàn)

#include <iostream>
#include <cstdio>
using namespace std;

int main(){
	long long x,cnt=0,i;
	cin>>x;
	for(i=1;i*i<x;i++){
		if(x%i==0) cnt+=2;
	}
	if(i*i==x) cnt++;
	cout<<cnt;
	return 0;
}