整数求因数算法

傷城~ 2022-05-14 04:05 517阅读 0赞

对一个整数求因数的计算在编程题中比较常见，还有在求出因数后对因数构成的数组再进行操作。例如，求一个整数的所有因数的求和结果，若是求和结果等于该整数，称这个整数为“完全数”，现在需要对输入的一个整数进行判断。首先是确定整数应该测试因数的范围，最直观的是将整数num依次循环除以2~num-1所有数，挑出余数为0的数。事实上，这样测试使循环次数增加了，例如32=4\*8，只需要测试出4，就已经知道8也满足条件了。所以，在循环进行测试的时候，测试到num的平方根就可以了。

编写一段程序测试完全数：

#include<iostream>
    #include<cmath>
    using namespace std;
    
    int perfectNumberCheck(int);
    int main(){
    	int num;
    	cin >> num;
    	if(perfectNumberCheck(num)){
            	cout << num << " is a perfect number!"<< endl;
        	}
        	else cout << num << " is not a perfect number!"<< endl;
    	return 0;
    }
    int perfectNumberCheck(int num){
    	int count=0;
    	int b[num]={0};
    	int a=sqrt(num);
    	for(int i=2;i<=a;i++){
    		if(num%i==0){
    			b[count]=i;
    			count++;
    		}
    	}
    	int sum=0;
    	for(int i=0;i<count;i++){
    		sum+=(b[i]+num/b[i]);
    	}
    	if(sum+1==num) return 1;
    	else return 0;
    }
    /*
    int perfectNumberCheck(int num){
    	int count=0;
    	int b[num]={0};
    	for(int i=2;i*i<=num;i++){ //直接使用i*i，可以避免使用开平方运算
    		if(num%i==0){
    			b[count]=i;
    			count++;
    		}
    	}
    	int sum=0;
    	for(int i=0;i<count;i++){
    		sum+=(b[i]+num/b[i]);
    	}
    	if(sum+1==num) return 1;
    	else return 0;
    }
    */

测试结果：

![70][]

在最后一次测试过程中，将for循环的起点改为了0，此时相当于num%0运算，因此出现了“浮点数例外（核心已转储）”的问题。

[70]: /images/20220514/174b2c976ae44e17914b8a29793407f1.png