Square free number

Question

Square free no: It is an integer which is divisible by no other perfect square than 1. For example, 10 is square-free but 18 is not, as 18 is divisible by 9 = 3^2.

The smallest positive square-free numbers are 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39

Is it possible to reduce the time execution for this code, without importing any Python module?

What should I use in place of a for loop body containing an if condition? Will using a lambda function be helpful?

def squarefree(n): 
 for i in range (2, round(n**0.5)): 
 if n % (i**2) == 0: 
 return False 
 return n

• Dair: Squarefree reduces down to being a number with a prime factorization such that none of the prime factors are squared (or more than squared). Thus this problem becomes similar to searching for primes. Using Eratosthenes' or Atkin's sieve will probably result in an improvement.
• alexwlchan: One easy win: after testing 4, you only need to test odd squares – if it’s 2-squarefree, then it must be (2*n)-squarefree for all n.

Answer 1

Review

Python has an official style-guide, PEP8. It recommends using white-space only where necessary (so the blank line after def squarefree(n): could go, as could the trailing space) and using four spaces as indentation.

Normally I would consider it best practice for a function like this to return actually True or False. Your function returns False or a truthy value, which also works, but is not as clean. Consider changing it from return n to return True.

---

Alternate implementation

As @Dair mentioned in the comments, depending on your use-case for this, it would be faster to write a sieve that gets all square-free numbers up to some limit.

Starting with the Sieve of Eratosthenes, taken from another of my answers, this could be implemented like this:

def squarefree(n):
 """
 Check if n is a square-free number, i.e. is divisible by no other perfect square than 1.
 Args:
 n positive integer to check
 Returns:
 n if n is a square-free number
 False else
 """
 for i in range(2, round(n**0.5) + 1):
 if n % (i**2) == 0:
 return False
 return n
def square_free_sieve(limit):
 """Generator that yields all square free numbers less than limit"""
 a = [True] * limit
 # Needed so we don't mark off multiples of 1^2
 yield 1
 a[0] = a[1] = False
 for i, is_square_free in enumerate(a):
 if is_square_free:
 yield i
 i2 = i * i
 for n in range(i2, limit, i2):
 a[n] = False
test1 = [n for n in range(100) if squarefree(n)]
test2 = list(square_free_sieve(100))
assert test1 == test2

When generating all square free numbers up to 100,000, your code needs about 3.5s, while the sieve only takes 0.05s, which is about 70 times faster.

• Gareth Rees: It would be nice if the revised code had docstrings.
• Graipher: @GarethReese Updated
• Emil Kerimov: When I try running square_free_sieve on python 3.4, the number 4, and other perfect squares, appear in this list for both implementations. I think this is due to the range being empty in those cases.
• Graipher: @EmilKerimov: So does the OP's implementation, btw. Nevertheless, I fixed it, it was a simple off-by-one error in both cases.