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:
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 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 > 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 < 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])