資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢使數字成為完全平方數的最小除數
假設我們有一個數字 N。我們必須找到將 N 除以使其成為完全平方數的最小數字。因此，如果 N = 50，則最小數字為 2，因為 50 / 2 = 25，而 25 是一個完全平方數。
如果一個數字具有偶數個不同的因子，則該數字是完全平方數。因此，我們將嘗試找到 N 的素因子，並找到每個素因子的冪。找到並乘以所有冪為奇數的素因子。
示例
#include<iostream>
#include<cmath>
using namespace std;
int findMinimumNumberToDivide(int n) {
int prime_factor_count = 0, min_divisor = 1;
while (n%2 == 0) {
prime_factor_count++;
n /= 2;
}
if (prime_factor_count %2)
min_divisor *= 2;
for (int i = 3; i <= sqrt(n); i += 2) {
prime_factor_count = 0;
while (n%i == 0) {
prime_factor_count++;
n /= i;
}
if (prime_factor_count%2)
min_divisor *= i;
}
if (n > 2)
min_divisor *= n;
return min_divisor;
}
int main() {
int n = 108;
cout << "Minimum number to divide is: " << findMinimumNumberToDivide(n) << endl;
}輸出
Minimum number to divide is: 3
更新於: 2019年12月18日
1K+ 瀏覽量
廣告