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

Question

I have this python program which registers the "Square Free Numbers" of a given number. I'm dealing with issue in regards to the time complexity that is I'm getting the mistake 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 might I lessen the time complexity of this program? That is how might I decrease the for loops so the program gets executed with a more modest time complexity?

Answer 1

To improve the time complexity of your program and make it more efficient, you can consider the following optimizations:

Instead of iterating up to the number itself, you can limit the first loop to the square root of the number. This reduces the number of iterations required to find the factors.

Rather than storing all the factors in a list, you can calculate the count of factors directly while iterating. This eliminates the need for the factors list and the subsequent calculation of total_len.

Instead of removing elements from the list, you can create a new list that only includes the non-perfect square factors. This avoids the need for nested loops and improves efficiency.

Here's a version of your program with these optimizations:

import math

number = int(input())

perfectSquares = []

count = 0

# Find perfect square numbers

for i in range(2, int(math.sqrt(number)) + 1):

    if i * i <= number:

        perfectSquares.append(i * i)

# Find the total number of factors and count perfect square factors

for i in range(1, number):

    if number % i == 0:

        count += 1

        for j in perfectSquares:

            if i % j == 0:

                count -= 1

                break

# Print the total count of square-free numbers

total_len = number - count

print(total_len)

By implementing these optimizations, you can reduce the number of iterations and improve the time complexity of your program.

Answer 2

As a matter of first importance, you just need to check for i in range(1, number/2):, since number/2 + 1 and more prominent can't be factors. 

Second, you can figure the quantity 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 look for factors, and when you discover one, watch that it isn't divisible by a square, and really at that time add it to the rundown of factors.

Interested to learn python in detail? Come and Join the python course.

Answer 3

To decrease the time complexity of your program and improve its efficiency, you can make a few optimizations:

Use the square root of the number as the upper limit in the first loop instead of number. This reduces the number of iterations needed to find the factors.

Instead of storing all the factors in a list, you can count them directly and calculate the total length as you go. This eliminates the need for the factors list and the subsequent loop to calculate total_len.

Rather than removing elements from a list, create a new list containing only the non-perfect square factors. This eliminates the need for nested loops and improves efficiency.

Here's an optimized version of your program:

import math

number = int(input())

perfectSquares = []

count = 0

# Find perfect square numbers

for i in range(2, int(math.sqrt(number)) + 1):

    if i * i <= number:

        perfectSquares.append(i * i)

# Find total number of factors and count perfect square factors

for i in range(1, number):

    if number % i == 0:

        count += 1

        for j in perfectSquares:

            if i % j == 0:

                count -= 1

                break

# Print Total Square Free numbers

total_len = number - count

print(total_len)

By implementing these optimizations, you can reduce the number of iterations and improve the overall time complexity of your program.

Answer 4

To improve the time complexity and efficiency of your program:

Use the square root of the number as the upper limit in the first loop.

Count the factors directly instead of storing them in a list.

Create a new list of non-perfect square factors instead of removing elements.

Here's the optimized version:

import math

number = int(input())

perfectSquares = []

count = 0

for i in range(2, int(math.sqrt(number)) + 1):

    if i * i <= number:

        perfectSquares.append(i * i)

for i in range(1, number):

    if number % i == 0:

        count += 1

        for j in perfectSquares:

            if i % j == 0:

                count -= 1

                break

total_len = number - count

print(total_len)

These optimizations reduce the number of iterations and improve the overall efficiency of your program.