Question

5. Write a function called no_squares which takes an input parameter N, a positive integer, and returns: 1 if N is not divisible by a square and has an even number of prime factors -1 if N is not divisible by a square and has an odd number of prime factors 0 if N is divisible by a square For example, no-squares (10) returns 1 (since 10 = 2x5), no-squares (30) returns-1 (since 30 = 2 × 3 × 5) and no-squares (12) returns 0 (since 12 = 22 x 3).

How to solve it using Python?

Answer 1

Here is the code for you:

#!/usr/bin/python
def no_squares(N):
   factors = []
   i = 2
   #Lists the prime factors of N.
   while N > 1:
       if N % i == 0:
           factors.append(i)
           N /= i
       else:
           i += 1  
   #Sorts the factors.      
   factors.sort()
   #If a factor is duplicated, return 0.
   for i in range(1, len(factors)):
       if factors[i] == factors[i-1]:
           return 0
   #If the prime factors are even, return 1, and -1 otherwise.      
   if len(factors) % 2 == 0:
       return 1
   return -1          
print no_squares(10)
print no_squares(30)
print no_squares(12)   ?

And the output screenshot is: