Count numbers with atleast one common factor, excluding one I have been trying to teach myself some python 3 lately by working through some 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. Also, if there are any concerns about using geeksforgeeks.org and folks could recommend other practice problem sites that would be appreciated. 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 code:

def myfun(num_in):

    new = num_in

    pos = []
    test = []
    int_list = []
    temp_list = []
    final_list = []

    if num_in == 1:
        print(0)
    elif num_in &gt; 1:
        # list all possibilities
        for i in range(2, num_in):
            pos.append(i)

        # check remainder from division
        for i in range(0, len(pos)):
            test.append(num_in % pos[i])

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

        # multiply factor my integers until it exceeds input
        for i in range(0, len(int_list)):
            temp_val = int_list[i]
            j = 1
            while temp_val * j &lt; num_in:
                final_list.append(temp_val * j)
                j += 1

        # add 1 for the number itself since we don't need to check that
        print(len(set(final_list)) + 1)

master_list = []

tot_num = int(input())

for p in range(tot_num):
    temp_val = int(input())
    master_list.append(temp_val)

for q in range(tot_num):
    myfun(master_list[q])
You write:


  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.


Here's that general advice: measure your code before you submit it! These kind of programming challenges normally give bounds on the size of the possible inputs, for example here it says:


  Constraints: \$1≤T≤100000\$, \$1≤N≤1000000\$


So in the worst case there would be 100,000 test cases, each of which has a number that might be as large as 1,000,000. So you need to ensure that your code runs quickly enough when run against a test case of this size.

Creating a test case is easy, for example you could write:

import random
T = 100000
N = 1000000
with open('worst-case.txt', 'w') as f:
    print(T, file=f)
    for _ in range(T):
        print(random.randrange(1, N + 1), file=f)


And then run your code using worst-case.txt as the input and see how long it takes. If the time limit is 5 seconds on the challenge site, then you probably want to make sure your code runs a bit quicker than that on your computer, in case the challenge site is running on a slower computer.

When you try this you'll find that the code in the post takes so long that you would be waiting a very long time for it to finish! I find that with \$T\$ reduced to 10, the code in the post takes about 3 seconds. So, extrapolating to the worst case, it would seem that when \$T = 100000\$, the code in the post would take 30,000 seconds, or about 8 hours.

Why does it take so long? Well, for every number \$n\$ in the input, it calls myfun. And then myfun constructs a list pos of all the numbers between 1 and \$n\$. But remember that \$n\$ might be as large as 1,000,000, which means that pos might have 1,000,000 elements, and a new list pos gets created for each number in the input. But there might be as many as 100,000 numbers in the input, so the line

pos.append(i)


might need to be executed as many as 100,000,000,000 times!

In this case you need to think clearly about all the steps involved in your algorithm. Try working through your algorithm step-by-step on a piece of paper. Can you spot any steps that seem useless? Can you spot any places where you needlessly compute the same thing many times?