ให้หมายเลข n; ภารกิจคือการค้นหาฟังก์ชัน Mobius ของจำนวน n
ฟังก์ชัน Mobius คืออะไร
ฟังก์ชัน Mobius คือฟังก์ชันทฤษฎีจำนวนที่กำหนดโดย
$$\mu(n)\equiv\begin{cases}0\\1\\(-1)^{k}\end{cases}$$
n=0 ถ้า n มีตัวประกอบซ้ำอย่างน้อยหนึ่งตัว
n=1 ถ้า n=1
n=(-1)k ถ้า n เป็นผลคูณของ k จำนวนเฉพาะที่แตกต่างกัน
ตัวอย่าง
Input: N = 17 Output: -1 Explanation: Prime factors: 17, k = 1, (-1)^k 🠠(-1)^1 = -1 Input: N = 6 Output: 1 Explanation: prime factors: 2 and 3, k = 2 (-1)^k 🠠(-1)^2 = 1 Input: N = 25 Output: 0 Explanation: Prime factor is 5 which occur twice so the answer is 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 form mobius(N) Stop
ตัวอย่าง
#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;
} ผลลัพธ์
N = -1
