ข้อความโจทย์
กำหนดจำนวนเต็ม N หาจำนวนตัวหารฟรีสแควร์ (square-free divisors) น้อยที่สุด
การแยกตัวประกอบของ N ควรประกอบด้วยตัวหารที่ไม่ใช่กำลังสองสมบูรณ์เท่านั้น
ตัวอย่าง
ถ้า N = 24 จะมีตัวประกอบฟรีสแควร์ 3 ตัว ดังนี้ −
ตัวประกอบ = 2 * 6 * 2
อัลกอริทึม
- หาตัวประกอบเฉพาะทั้งหมดจนถึงรากที่สองของ N
- พิจารณาตัวประกอบเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับรากที่สองของ N และสำหรับแต่ละตัวประกอบเฉพาะ หากำลังสูงสุดในจำนวน N (เช่น กำลังสูงสุดของ 2 ใน 24 คือ 3)
- เราทราบว่าถ้าตัวประกอบเฉพาะมีกำลังมากกว่า 1 ใน N มันไม่สามารถจับคู่กับตัวเองได้ (เช่น 2 มีกำลัง 3 ใน 24 ดังนั้น 2x2=4 หรือ 2x2x2=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
