Count numbers with atleast one common factor, excluding one
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?