คำชี้แจงปัญหา
กำหนดจำนวนเต็ม N หาจำนวนขั้นต่ำของตัวหารว่างกำลังสอง
การแยกตัวประกอบของ N ควรประกอบด้วยเฉพาะตัวหารที่ไม่เต็มกำลังสอง
ตัวอย่าง
ถ้า N =24 แล้วจะมีตัวประกอบอิสระ 3 ตัวดังนี้ −
ตัวประกอบ =2 * 6 * 2
อัลกอริทึม
- ค้นหาตัวประกอบเฉพาะทั้งหมดไม่เกินรากที่สองของ N
- ตอนนี้ ให้พิจารณาตัวประกอบเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับรากที่สองของ N และสำหรับปัจจัยเฉพาะแต่ละตัว ให้หากำลังสูงสุดเป็นจำนวน N (เช่น กำลังสูงสุด 2 ใน 24 คือ 3)
- ตอนนี้ เรารู้ว่าหากปัจจัยเฉพาะมีกำลังมากกว่า 1 ใน N จะไม่สามารถจัดกลุ่มกับตัวเองได้ (เช่น 2 มีกำลัง 3 ใน 24 ดังนั้น 2 x 2 =4 หรือ 2 x 2 x 2 =8 ไม่สามารถเกิดขึ้นในการแยกตัวประกอบของ 24 เนื่องจากทั้งคู่ไม่ว่างกำลังสอง) เนื่องจากจะหารด้วยกำลังสองสมบูรณ์บางตัว
- แต่ตัวประกอบเฉพาะที่จัดกลุ่มกับตัวประกอบเฉพาะอื่น (เพียงครั้งเดียว) จะไม่มีวันหารด้วยกำลังสองสมบูรณ์ใดๆ
- สิ่งนี้ทำให้เรามีสัญชาตญาณว่าคำตอบจะเป็นค่าสูงสุดของกำลังสูงสุดของตัวประกอบเฉพาะทั้งหมดในจำนวน N
ตัวอย่าง
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define MAX 1005
void getPrimes(vector<int>& primes) {
bool prime[MAX];
memset(prime, true, sizeof(prime));
for (int p = 2; p * p < MAX; p++) {
if (prime[p] == true) {
for (int i = p * 2; i < MAX; i += p)
prime[i] = false;
}
}
for (int p = 2; p < MAX; p++)
if (prime[p])
primes.push_back(p);
}
int getMinimumSquareFreeDivisors(int n) {
vector<int> primes;
getPrimes(primes);
int maxCnt = 0;
for (int i = 0; i < primes.size() && primes[i] * primes[i] <= n; i++) {
if (n % primes[i] == 0) {
int tmp = 0;
while (n % primes[i] == 0) {
tmp++;
n /= primes[i];
}
maxCnt = max(maxCnt, tmp);
}
}
if (maxCnt == 0)
maxCnt = 1;
return maxCnt;
}
int main() {
int n = 24;
cout << "Minimum number of square free divisors = " << getMinimumSquareFreeDivisors(n) << endl;
return 0;
} ผลลัพธ์
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
Minimum number of square free divisors = 3
