Möbius function: Difference between revisions
Adds Python code for the task. Everything from GeeksForGeeks and code written by Manish Shaw.
(Adds crediting) |
(Adds Python code for the task. Everything from GeeksForGeeks and code written by Manish Shaw.) |
||
Line 1,287:
0 -1 -1 1 0 1 -1 1 0 0 -1 -1 0 -1 1 -1 0 -1 0 -1
</pre>
=={{header|Python}}==
Everything verbatim from: https://www.geeksforgeeks.org/program-mobius-function/
We iterate through all numbers i smaller than or equal to N. For every number we check if it divides N. If yes, we check if it’s also prime. If both conditions are satisfied, we check if its square also divides N. If yes, we return 0. If the square doesn’t divide, we increment count of prime factors. Finally, we return 1 if there are an even number of prime factors and return -1 if there are odd number of prime factors.
<lang python>
# Python Program to
# evaluate Mobius def
# M(N) = 1 if N = 1
# M(N) = 0 if any
# prime factor of
# N is contained twice
# M(N) = (-1)^(no of
# distinct prime factors)
# def to check if
# n is prime or not
def isPrime(n) :
if (n < 2) :
return False
for i in range(2, n + 1) :
if (i * i <= n and n % i == 0) :
return False
return True
def mobius(N) :
# Base Case
if (N == 1) :
return 1
# For a prime factor i
# check if i^2 is also
# a factor.
p = 0
for i in range(1, N + 1) :
if (N % i == 0 and
isPrime(i)) :
# Check if N is
# divisible by i^2
if (N % (i * i) == 0) :
return 0
else :
# i occurs only once,
# increase f
p = p + 1
# All prime factors are
# contained only once
# Return 1 if p is even
# else -1
if(p % 2 != 0) :
return -1
else :
return 1
# Driver Code
N = 17
print ("Mobius defs M(N) at N = {} is: {}" .
format(N, mobius(N)),end = "\n")
print ("Mobius defs M(N) at N = {} is: {}" .
format(25, mobius(25)),end = "\n")
print ("Mobius defs M(N) at N = {} is: {}" .
format(6, mobius(6)),end = "\n")
# This code is contributed by
# Manish Shaw(manishshaw1)</lang>
{{out}}
<pre>Mobius Functions M(N) at N = 17 is: -1
Mobius Functions M(N) at N = 25 is: 0
Mobius Functions M(N) at N = 6 is: 1</pre>
Method 2 (Efficient)
The idea is based on efficient program to print all prime factors of a given number. The interesting thing is, we do not need inner while loop here because if a number divides more than once, we can immediately return 0.
<lang Python># Python Program to evaluate
# Mobius def M(N) = 1 if N = 1
# M(N) = 0 if any prime factor
# of N is contained twice
# M(N) = (-1)^(no of distinct
# prime factors)
import math
# def to check if n
# is prime or not
def isPrime(n) :
if (n < 2) :
return False
for i in range(2, n + 1) :
if (n % i == 0) :
return False
i = i * i
return True
def mobius(n) :
p = 0
# Handling 2 separately
if (n % 2 == 0) :
n = int(n / 2)
p = p + 1
# If 2^2 also
# divides N
if (n % 2 == 0) :
return 0
# Check for all
# other prime factors
for i in range(3, int(math.sqrt(n)) + 1) :
# If i divides n
if (n % i == 0) :
n = int(n / i)
p = p + 1
# If i^2 also
# divides N
if (n % i == 0) :
return 0
i = i + 2
if(p % 2 == 0) :
return -1
else :
return 1
# Driver Code
N = 17
print ("Mobius defs M(N) at N = {} is: {}\n" .
format(N, mobius(N)));
print ("Mobius defs M(N) at N = 25 is: {}\n" .
format(mobius(25)));
print ("Mobius defs M(N) at N = 6 is: {}\n" .
format(mobius(6)));
# This code is contributed by
# Manish Shaw(manishshaw1)</lang>
{{out}}
<pre>Mobius Functions M(N) at N = 17 is: -1
Mobius Functions M(N) at N = 25 is: 0
Mobius Functions M(N) at N = 6 is: 1</pre>
=={{header|Raku}}==
| |||