5
\$\begingroup\$

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
\$\endgroup\$
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – Dair Jan 7 '17 at 8:34
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – alexwlchan Jan 7 '17 at 8:37
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ It would be nice if the revised code had docstrings. \$\endgroup\$ – Gareth Rees Jan 8 '17 at 10:07
  • \$\begingroup\$ @GarethReese Updated \$\endgroup\$ – Graipher Jan 8 '17 at 10:22
  • \$\begingroup\$ 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. \$\endgroup\$ – Emil Kerimov Sep 9 '18 at 18:03
  • \$\begingroup\$ @EmilKerimov: So does the OP's implementation, btw. Nevertheless, I fixed it, it was a simple off-by-one error in both cases. \$\endgroup\$ – Graipher Sep 10 '18 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.