How can I reduce the time complexity of the given python code?

I have this python program which computes the "Square Free Numbers" of a given number. I'm facing problem regarding the time complexity that is I'm getting the error as "Time Limit Exceeded" in an online compiler.

number = int(input())
factors = []
perfectSquares = []
count = 0
total_len = 0

# Find All the Factors of the given number
for i in range(1, number):
if number%i == 0:
    factors.append(i)

# Find total number of factors        
total_len = len(factors)

for items in factors:
    for i in range(1,total_len):
  # Eleminate perfect square numbers
    if items == i * i:
        if items == 1:
            factors.remove(items)
            count += 1
        else:
            perfectSquares.append(items)
            factors.remove(items)
            count += 1

# Eleminate factors that are divisible by the perfect squares 
for i in factors:
    for j in perfectSquares:
    if i%j == 0:
        count +=1

# Print Total Square Free numbers
total_len -= count 
print(total_len)

How can I reduce the time complexity of this program? That is how can I reduce the for loops so the program gets executed with a smaller time complexity?

Solution 1:

Algorithmic Techniques for Reducing Time Complexity(TC) of a python code.

In order to reduce time complexity of a code, it's very much necessary to reduce the usage of loops whenever and wherever possible.

I'll divide your code's logic part into 5 sections and suggest optimization in each one of them.

Section 1 - Declaration of Variables and taking input

number = int(input())
factors = []
perfectSquares = []
count = 0
total_len = 0

You can easily omit declaration of perfect squares, count and total_length, as they aren't needed, as explained further. This will reduce both Time and Space complexities of your code.

Also, you can use Fast IO, in order to speed up INPUTS and OUTPUTS This is done by using 'stdin.readline', and 'stdout.write'.

Section 2 - Finding All factors

for i in range(1, number):
    if number%i == 0:
        factors.append(i)

1. Here, you can use List comprehension technique to create the factor list, due to the fact that List comprehension is faster than looping statements.
2. Also, you can just iterate till square root of the Number, instead of looping till number itself, thereby reducing time complexity exponentially. Above code section guns down to...

After applying '1' hack

factors = [for i in range(1, number) if number%i == 0]

After applying '2' hack - Use from_iterable to store more than 1 value in each iteration in list comprehension

factors = list( chain.from_iterable(
  (i, int(number/i)) for i in range(2, int(number**0.5)+1)
    if number%i == 0
  ))

Section 3 - Eliminating Perfect Squares

# Find total number of factors        
total_len = len(factors)

for items in factors:
    for i in range(1,total_len):
  # Eleminate perfect square numbers
    if items == i * i:
        if items == 1:
            factors.remove(items)
            count += 1
        else:
            perfectSquares.append(items)
            factors.remove(items)
            count += 1

Actually you can completely omit this part, and just add additional condition to the Section 2, namely ... type(i**0.5) != int, to eliminate those numbers which have integer square roots, hence being perfect squares themselves. Implement as follows....

factors = list( chain.from_iterable(
  (i, int(number/i)) for i in range(2, int(number**0.5)+1)
    if number%i == 0 and type(i**0.5) != int
  ))

Section 4 - I think this Section isn't needed because Square Free Numbers doesn't have such Restriction

Section 5 - Finalizing Count, Printing Count

There's absolutely no need of counter, you can just compute length of factors list, and use it as Count.

OPTIMISED CODES

Way 1 - Little Faster

number = int(input())

# Find Factors of the given number
factors = []
for i in range(2, int(number**0.5)+1):
    if number%i == 0 and type(i**0.5) != int:
        factors.extend([i, int(number/i)])

print([1] + factors)

Way 2 - Optimal Programming - Very Fast

from itertools import chain 
from sys import stdin, stdout

number = int(stdin.readline())
factors = list( chain.from_iterable(
  (i, int(number/i)) for i in range(2, int(number**0.5)+1)
    if number%i == 0 and type(i**0.5) != int
  ))

stdout.write(', '.join(map(str, [1] + factors)))

Solution 2:

First of all, you only need to check for i in range(1, number/2):, since number/2 + 1 and greater cannot be factors.

Second, you can compute the number of perfect squares that could be factors in sublinear time:

squares = []
for i in range(1, math.floor(math.sqrt(number/2))):
    squares.append(i**2)

Third, you can search for factors and when you find one, check that it is not divisible by a square, and only then add it to the list of factors.

This approach will save you all the time of your for items in factors nested loop block, as well as the next block. I'm not sure if it will definitely be faster, but it is less wasteful.