ブルーブリッジ杯素因子去重C++アルゴリズム訓練HERODINGブルーブリッジ杯の道

リソース制限時間制限:1.0 sメモリ制限:256.0 MB問題は、与えられた正の整数nを記述し、正の整数pを求め、pがnのすべての素因子しか含まれていないことを満たし、各素因子の回数は1入力フォーマットより1つの整数ではなく、n出力フォーマットが1行出力され、1つの整数pが含まれていることを示す.サンプル入力1000サンプル出力10データ規模と約束n<=10^12サンプル解釈:n=1000=2^353,p=2*5=10
解題の構想:この問題の構想ははっきりしていて、まず素因子を探し出して、まず2に対して余数を取って、もし余数が0ならば、2が素因子であることを説明して、配列の中に入れて、それから絶えず循環して、繰り返しの2は判断して入れないで、2判断が終わった後に、3、5、7...平方数まで判断して、もちろん自身が質数の情況であることを考慮して、もし存在してしかも繰り返して配列の中に入れないならば、最後に,配列中のすべての数を乗算して求めた結果とする.コードは次のとおりです.

#include

using namespace std;

int index = 0;

int a[100];

bool judge(int num){
	for (int i = 0; i < index; i ++){
		if(a[i] == num){
			return false;
		}
	}
	return true;
}

int main(){
	long long n;
	cin >> n;
	while (n % 2 == 0) {
		if(judge(2)){
			a[index ++] = 2;
		}
		n /= 2;
	} 
	for(int i = 3;i <= sqrt(n*1.0);i += 2){
		while(n % i == 0){
		if(judge(i)){
			a[index ++] = i;
		}
			n /= i;
		}
	}
	if(n > 2){
	if(judge(n)){
			a[index ++] = n;
		}	
	}
	int sum = 1;
	for (int i = 0; i < index; i ++){
		sum *= a[i];
	}
	cout << sum;
	return 0;
}