Count numbers with atleast one common factor, excluding one (updated)

Question

Below is an updated version of the question I asked prior:

Count numbers with atleast one common factor, excluding one

I have been trying to teach myself some python 3 by working through problems at geeksforgeeks.org. A common issue I am having is that my code runs on my machine, and in their test environment, but my code ultimately exceeds their time limits upon submission. I was wondering if anyone had any general advice on making my code more efficient so I could continue to make use of the practice problems.

As for my update, I have tried:

(1) Utilizing list comprehension in python. While cleaner, I don't think this made any dramatic improvements for me. (2) I only populate the list of possibilities once now as per the suggestion of Gareth Rees. I originally knew this was inefficient, but I thought this was bad form since it makes my code less flexible for the most general case. I realize now that the constraints should be used in a way to make the code faster for these types of time-limited problems. (3) I have traded a while loop for a for loop since I read this was faster.

That said, I am still no where near the time limits they are imposing in the problem. Some thoughts I had:

(1) My guess is the main culprit is the nested for loop inside a for loop which is likely very time consuming, but I don't know how to get around using nested for loops in this.

(2) Also, I am wondering if Python is even suitable for severely time limited challenges of this sort? I have read that Python is generally slower than C++ and from what I can tell very few people use Python on time-limited sites like this.

The problem I have been working on is:

http://practice.geeksforgeeks.org/problems/mathematical-manipulation/0

Given a number \$N\$, find the total numbers, less than or equal to \$N\$ which have at-least one common factor with \$N\$ other than \$1\$.

Input: The first line of input contains an integer \$T\$ denoting the no of test cases. Then \$T\$ test cases follow. Each test case consist of an integer \$N\$.

Output: For each test case output an integer denoting the count of numbers, less than or equal to \$N\$ having at-least one common factor between the number and \$N\$ except \$1\$.

Constraints: \$1 \le T \le 100000\$
\$1 \le N \le 1000000\$

Example:
Input:

3
1
6
15

Output:

0
4
7

And my (updated) code:

def myfun(num_in):

    int_list = []
    some_list = []
    final_list = []

    if num_in == 1:
        print(0)
    elif num_in > 1:

        # check remainder from division
        test = [num_in % pos[j] for j in range(0, (num_in + 1) // 2)]  # only need .5 the number or smaller

        # record if remainder is 0, if it is, keep that because it will be common denominator
        for i in range(0, len(test)):
            if test[i] == 0:
                int_list.append(pos[i])

        # multiply factor by integers until it exceeds input
        # this seems like the best candidate to make more efficient
        for i in range(0, len(int_list)):
            temp = int_list[i]
            # for j in range(1, int(num_in / temp)):
            #     final_list.append(temp * j)

            ttempp = [j for j in range(1, int(num_in / temp))]
            some_list = list(map(lambda x: x * temp, ttempp))
            final_list = final_list + some_list


        #print(final_list)
        #print(set(final_list))
        # add 1 for the number itself since we don't check that (only checked up to .5 * num)
        print(len(set(final_list)) + 1)


# list all possibilities once
pos = [i for i in range(2, 1000000)]


# input code
# how many to run
tot_num = int(input())

# get full list of inputs
master_list = [int(input()) for i in range(tot_num)]

# run code on list of inputs
[myfun(master_list[q]) for q in range(tot_num)]

Answer 1

Your algorithm is very far from optimal. In the worst case (if all numbers are equal to N in the input), it does O(N * T) operations, which clearly way too much (not just for python, for any programming language).

What they're asking to compute is n - phi(n), where phi is the Euler's totient function. Using the fact that the function is multiplicative one can derive a formula phi(n) = n * {product of (1 - 1 / p) over all prime p dividing n. Using this fact, we can compute it efficiently in O(N log log N) time for all 1 <= i <= N using something that looks like the sieve of Eratosthenes. After that, we can answer each query in O(1).

A C++ implementation is ridiculously concise and easily fits in the time limit:

#include <cstdio>
#include <vector>
#include <algorithm>

int main() {
    const int max_n = 1000 * 1000;
    std::vector<int> ans(max_n + 1);
    std::iota(ans.begin(), ans.end(), 0);
    for (int i = 2; i <= max_n; i++)
        if (ans[i] == i)
            for (int j = i; j <= max_n; j += i)
                ans[j] = ans[j] / i * (i - 1);
    int t;
    scanf("%d", &t);
    while (t--) {
        int x;
        scanf("%d", &x);
        printf("%d\n", x - ans[x]);
    }
}

Unfortunately, the same solution in python is too slow.

def calc_phi(n):
    res = [i for i in range(n + 1)]
    is_prime = [True] * (n + 1)
    for i in range(2, n + 1):
        if is_prime[i]:
            for j in range(2 * i, n, i):
                is_prime[j] = False
                res[j] = res[j] // i * (i - 1)
    return res


def solve():
    max_n = 10 ** 6
    phi = calc_phi(max_n)
    cnt = int(input())
    res = []
    for _ in range(cnt):
        n = int(input())
        res.append(n - phi[n])
    print('\n'.join(map(str, res)))


if __name__ == '__main__':
    solve()

With some optimizations (like more efficient input reading and handling small prime divisors separately), which made the code less readable and nice, I managed to make it complete under 1 second in the worst case on my machine, which is pretty close. It's still too slow for the online judge. So I'm not sure if it's actually solvable in python. That's the main reason why python is rarely used to solve problems with a tight time limit: it's much slower than C++ or Java.

Answer 2

Try to not use list comprehensions when you don't need to. Instead use a generator comprehension, to change to this you only need to change the square brackets to curved. (i for i in range(10)), rather than [i for i in range(10)]. This changes the output from a list to a generator, which has better memory management, and makes splitting up your code more efficant.

I'd also change myfun to only use one comprehension, splitting it across multiple for loops and comprehensions just makes it harder to read.

pos is also rather pointless, it's using up memory, whilst making your code harder to understand. Instead I'd just change pos[i] to (i + 2), or better that that, change it so that you don't need the (i + 2).

Finally, don't use comprehensions for side effects, it's horrible and not only un-Python but un-functional. Only use them for their output. Your very last line should use a standard for loop.

And so I'd change your code to:

def myfun(num_in):
    if num_in == 1:
        print(0)
    elif num_in > 1:
        print(len(set(
            j * i
            for i in range(2, (num_in + 1) // 2 + 2)
            if (num_in % i) == 0
            for j in range(1, int(num_in / i))
        ) + 1))

tot_num = int(input())
master_list = [int(input()) for i in range(tot_num)]
for q in range(tot_num):
    myfun(master_list[q])