解题思路:
O(n)的算法很容易想到,正好刚学了数论,就写一个求约数的模板吧,它的时间复杂度是O(sqrt(n))
根据算数基本定理,一个数可以分成多个质数相乘,例如60=2*2*3*5;
而约数个数就是根据算数基本定理来的,约数的个数等于分解出的质数次方+1相乘
如60的约数个数为:(2+1)*(1+1)*(1+1)=12
12的约数个数等于:(2+1)*(1+1)=6 【12=2*2*3】
附上算数基本定理的数学证明吧:
参考代码:
#include <stdio.h> #include <math.h> int main () { int i,k=0; int n,z=1; scanf("%d",&n); for(i=2;i<=n;i++){ while(n%i==0){ k++; n/=i; } z*=(k+1); k=0; } printf("%d",z); return 0; }
0.0分
155 人评分
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:545 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:851 |
简单的a+b (C语言代码)浏览:573 |
wu-淘淘的名单 (C++代码)浏览:1337 |
wu-理财计划 (C++代码)浏览:831 |
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:609 |
DNA (C语言描述,蓝桥杯)浏览:1553 |
A+B for Input-Output Practice (V) (C语言代码)浏览:459 |
【偶数求和】 (C语言代码)浏览:431 |
sizeof的大作用 (C语言代码)浏览:1024 |