โปรแกรม C++ สำหรับฟังก์ชันเมียบิอุส (Mobius Function)

ฟังก์ชันเมียบิอุสคืออะไร?

ฟังก์ชันเมียบิอุส (Mobius Function) เป็นฟังก์ชันทฤษฎีจำนวนที่นิยามโดย:

$$\mu(n)\equiv\begin{cases}0\\1\\(-1)^{k}\end{cases}$$

• μ(n) = 0 ถ้า n มีตัวประกอบซ้ำกัน 1 ตัวขึ้นไป
• μ(n) = 1 ถ้า n = 1
• μ(n) = (-1)ᵏ ถ้า n เป็นผลคูณของ k จำนวนเฉพาะที่ต่างกัน

ตัวอย่าง

Input: N = 17
Output: -1
Explanation: ตัวประกอบเฉพาะ: 17, k = 1, (-1)^k → (-1)^1 = -1

Input: N = 6
Output: 1
Explanation: ตัวประกอบเฉพาะ: 2 และ 3, k = 2, (-1)^k → (-1)^2 = 1

Input: N = 25
Output: 0
Explanation: ตัวประกอบเฉพาะคือ 5 ซึ่งเกิดขึ้น 2 ครั้ง ดังนั้นคำตอบคือ 0

แนวทางการแก้ปัญหา

• รับอินพุต N
• วนลูป i จาก 1 ถึง N ตรวจสอบตัวหารของ N และตรวจสอบว่าเป็นจำนวนเฉพาะหรือไม่
• หากเงื่อนไขทั้งสองเป็นจริง ให้ตรวจสอบว่ากำลังสองของตัวเลขนั้นหาร N ลงตัวหรือไม่ ถ้าลงตัวให้คืนค่า 0
• มิฉะนั้น เพิ่มจำนวนนับของตัวประกอบเฉพาะ ถ้าจำนวนนับเป็นเลขคู่คืนค่า 1 หากเป็นเลขคี่คืนค่า -1
• พิมพ์ผลลัพธ์

อัลกอริทึม

Start
Step 1 → In function bool isPrime(int n)
    Declare i
    If n < 2 then,
        Return false
    Loop For i = 2 and i * i <= n and i++
        If n % i == 0
            Return false
        End If
    Return true

Step 2 → In function int mobius(int N)
    Declare i and p = 0
    If N == 1 then,
        Return 1
    End if
    Loop For i = 1 and i <= N and i++
        If N % i == 0 && isPrime(i)
            If (N % (i * i) == 0)
                Return 0
            Else
                Increment p by 1
            End if
        End if
    Return (p % 2 != 0)? -1 : 1

Step 3 → In function int main()
    Declare and set N = 17
    Print the results from mobius(N)
Stop

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

#include <iostream>
using namespace std;

// Function to check if n is prime or not
bool isPrime(int n) {
    int i;
    if (n < 2)
        return false;
    for (i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return true;
}

int mobius(int N) {
    int i;
    int p = 0;
    // if n is 1
    if (N == 1)
        return 1;
    // For a prime factor i check if i^2 is also a factor.
    for (i = 1; i <= N; i++) {
        if (N % i == 0 && isPrime(i)) {
            // Check if N is divisible by i^2
            if (N % (i * i) == 0)
                return 0;
            else
                // i occurs only once, increase p
                p++;
        }
    }
    // All prime factors are contained only once
    // Return 1 if p is even else -1
    return (p % 2 != 0)? -1 : 1;
}

// Driver code
int main() {
    int N = 17;
    cout << mobius(N) << endl;
}

ผลลัพธ์

-1