奇因子之和（C语言）

题意：

一个整数的因子，就是所有可以整除这个数的数。奇数指在整数中，不能被 2 整除的数。所谓整数?Z?的奇因子，就是可以整除?Z?的奇数。
给定?N?个正整数，请你求出它们的第二大奇因子的和。当然，如果该数只有一个奇因子，就用它唯一的那个奇因子去求和。

输入格式：

输入第一行给出一个正整数?N（≤1000）。随后一行给出?N?个不超过?106?的正整数。

输出格式：

在一行中输出所有给定整数的第二大奇因子之和。

输入样例：

5
147 12 35 78 4

输出样例：

71

样例解释：

• 147 的因子有 { 1、3、7、21、49、147 }，第二大奇因子是 49；
• 12 的因子有 { 1、2、3、4、6、12 }，第二大奇因子是 1；
• 35 的因子有 { 1、5、7、35 }，第二大奇因子是 7；
• 78 的因子有 { 1、2、3、6、13、26、39、78 }，第二大奇因子是 13；
• 4 的因子有 { 1、2、4 }，只有一个奇因子，所以用 1 参与求和。
  所以输出的答案是：49+1+7+13+1 = 71。

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

代码如下：

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