C++的问题 整数的因子数 Time Limit:2000MS Memory Limit:32768K
解决时间 2021-04-04 10:26
- 提问者网友：我是我
- 2021-04-03 18:30
Description:
找出整数的所有因子数。 一个整数n的因子数为包含它自身的所有因子的个数。例如：12的因子数为6(1,2,3,4,6,12)。
Input:
输入数据中含有一些整数n（1≤n＜2^32）。
Output:
对于每个n，列出其所有因子数，每个n加上冒号单独列一行。
Sample Input:
11 22 33 24
Sample Output:
11: 2
22: 4
33: 4
24: 8
http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1192
________________________________________________
我写的超时了 ，求更好的算法.......
#include
#include
using namespace std;
void main()
{
int n;
while(cin>>n)
{
if(n>=1)
{
cout< if(n>1)
{
int i,k=1;
for(i=2;i<=sqrt((double)n);i++)
if(n%i==0)
k++;
if((i-1)*(i-1)==n)
cout<<2*k-1< else
cout<<2*k< }
else
cout<<1< }
}
}
最佳答案
- 五星知识达人网友：独钓一江月
- 2021-04-03 20:06
我电脑算着也没问题，可能你电脑cpu较老吧。
算法改进：
1.上面这个程序是以根号n为循环边界，个人认为这时还不如用n/2，开根可比除2慢多了。
2.当得到n的第一个因子，比如说7时，不如n /= 7;再重新从2~n/2循环判断。举例说:23324 = 2*2*7*7*7*17，如果用上例的方法，会计算根号23324或者23324/2次，而用改进2中的方法的话，只用到2+2+7/2 + 7/2 + 7/2 + 17/2次也就是27次运算，11662:27可以说是很悬殊了。
按照以上改进我写了一个拆分整数的程序，结果是最简因子形式（质因子），计算普通因子个数的任务就交给你了，有了高中排列组合的知识，很好算的，小心其中重复出现的质因子。
#include
using namespace std;
int child(int n) //如果是素数则返回原数n，否则返回一个因子
{
if (n <= 2)return n;
for (int i = 2; i < n/2; i ++)
if (n%i == 0)return i;
return n;
}
int main()
{
int n;
cin>>n;
if (n<=0){cout<<"Please input positive integer\n";return 0;}
if (child(n) == n){cout<<"此数是素数\n";}
else
for (;;)
{
int factor = child(n);
cout<
n /= factor;
if (n == 1)break;
}
cout<
return 0;
}
全部回答
- 1楼网友：平生事
- 2021-04-03 21:45
#include
using namespace std;
#include
bool isorder(int* a, int m)
{
sort(a,a+m);
int t = a[1]-a[0];
for(int i=3;i>n;
for(int i=0;i>m;
for(int j=0;j>a[j];
r[i] = m<3||isorder(a,m);
}
for(int k=0; k
- 2楼网友：旧脸谱
- 2021-04-03 20:22
简单题
#include
#include
#include
using namespace std;
int n,m;
int arr[3010];
int main(){
int i,j,k;
vectorV;
while(scanf("%d %d",&n,&m)!=EOF){
for(i=0;i::iterator iter;
iter = V.end();
iter --;
printf("%d",*iter);
iter--;
for (i=1;i
我要举报
大家都在看
推荐资讯