数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时装研究
法律研究C++ 中莫比乌斯函数的程序
给定一个数 n；任务是求数 n 的莫比乌斯函数。
什么是莫比乌斯函数？
莫比乌斯函数是数论函数，由如下定义
$$\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。
- 从 1 到小于 N 迭代 i，检查 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
更新于: 20-Dec-2019
362 次浏览
广告