หาตัวเลขน้อยที่สุดที่ต้องหารเพื่อให้ได้จำนวนกำลังสองสมบูรณ์ใน C++

โจทย์

ให้จำนวน N ต้องการหาตัวเลขน้อยที่สุดที่หาร N แล้วได้จำนวนกำลังสองสมบูรณ์ (Perfect Square)

ตัวอย่าง: N=50 → หาร 2 ได้ 25 (กำลังสอง) → คำตอบ 2

หลักการ

จำนวนเป็นกำลังสองสมบูรณ์ ↔ เฉพาะตัวประกอบทุกตัวมีเลขชี้กำลังเป็นเลขคู่

วิธี: หาเฉพาะตัวประกอบของ N และเลขชี้กำลัง → คูณเฉพาะตัวที่มีเลขชี้กำลังคี่

ตัวอย่างโค้ด C++

#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