หาจำนวนตัวหารของ n² ที่ไม่ใช่ตัวหารของ n ใน C++

บทนำ

โจทย์นี้ต้องการหาจำนวนตัวหารของ n² ที่ ไม่ใช่ ตัวหารของ n โดยตรง

ขั้นตอนการแก้ปัญหา

1. รับค่า n
2. คำนวณ n²
3. วนลูปจาก 2 ถึง n²
4. ถ้า n² หารด้วย i ลงตัว แต่ n หารด้วย i ไม่ลงตัว → นับเพิ่ม
5. แสดงผลรวม

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

#include <bits/stdc++.h>
using namespace std;

int getNumberOfDivisors(int n) {
    int n_square = n * n;
    int divisors_count = 0;
    for (int i = 2; i <= n_square; i++) {
        if (n_square % i == 0 && n % i != 0) {
            divisors_count++;
        }
    }
    return divisors_count;
}

int main() {
    int n = 6;
    cout << getNumberOfDivisors(n) << endl;
    return 0;
}

ผลลัพธ์

5

คำอธิบายตัวอย่าง n = 6

• n² = 36
• ตัวหารของ 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
• ตัวหารของ 6: 1, 2, 3, 6
• ตัวหารของ 36 ที่ไม่ใช่ตัวหารของ 6: 4, 9, 12, 18, 36 → รวม 5 ตัว

หมายเหตุประสิทธิภาพ

วิธีนี้ใช้เวลา O(n²) อาจช้าเมื่อ n ใหญ่ สามารถปรับปรุงได้ด้วยการหาตัวหารเฉพาะจนถึง √(n²) และใช้ทฤษฎีจำนวน

สรุป

โค้ดนี้เหมาะสำหรับ n ขนาดเล็ก หากต้องการประสิทธิภาพสูง ควรใช้วิธีการแยกตัวประกอบเฉพาะ (Prime Factorization)