RUC_JudgeOnline 1006 计算约数

计算约数

Description

计算正整数n的所有约数。

Input

共一行，为正整数n(n<500000)。

Output

输出文件共一行，从小到大输出正整数n的所有有约数，每个数之间有一个空格。

Sample Input

 

12

 

Sample Output

1 2 3 4 6 12 

 

 

Source

习题6-7

问题分析：

就是一个简单的循环，用小于n的数去除n，只要能整除就输出。

参考代码：

 

 

#include<stdio.h> 
int main() 
{
 	int n; 
	scanf("%d",&n); 
	int i;
 	for(i=1;i<=n;i++) 
	{ 
		if(n%i==0)
			 printf("%d ",i);
 	} 
	return 0; 
} 

  如果对程序的最后一个输出进行单独处理（如下所示），则在运行时间上会有明显改进。

#include<stdio.h>
 int main() 
{ 
	int n;
	 scanf("%d",&n);
 	int i;
 	for(i=1;i<=n/2;i++)
 	{ 
		if(n%i==0)
			 printf("%d ",i); 
	}
 	printf("%d",n); 
	return 0; 
}

 最好的改进是只用1~sqrt（n）的数去除n，如果能整除，则讲对应的因数放入temp数组。最后逆序输出。增加一个变量来记录需要逆序输出的后半段的因子个数。

#include <stdio.h>
#include <math.h>

int main()
{
	int n,i,j=0;
	int temp[100];
	scanf("%d",&n);
	for(i=1;i<=sqrt(n);i++)
		if(n%i==0)
		{
			printf("%d ",i);
			temp[j++]=n/i;
		}
	i--;
	j--;
	if(i*i==n) j--;
	for(;j>=0;j--)
		printf("%d ",temp[j]);

}