Below is an updated version of the question I asked prior:
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:
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\$
3 1 6 15
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)]