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

• For anyone curios why there's a close vote, the site outputs 'Run Time Error Time Limit of 5 seconds exceeded' when it runs out of time, this code does seem to work as intended. – Peilonrayz May 17 '17 at 14:17
• @DJBunk: Here at Code Review, we don't allow posters to update the code in the question — experience has shown that this leads to confusion as the question becomes a moving target. What you can do instead is post your updated code as a new question, so that reviewers can post new answers. – Gareth Rees May 18 '17 at 17:40

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?