# Anti-Triangle

Computer Science Level pending

Chris wants a list of numbers up to $$N$$ that is not divisible by any triangular numbers greater than 1. Here is his algorithm in Python:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def anti_tri(N): # L[i] = 1 implies i is not divisible by any triangular number > 1 L = [0] + [1] * N T = 3 # triangular number i = 3 while T <= N: for i in range(T,N,T): L[i] = 0 T += i i += 1 ans = [] for i in range(N+1): if L[i] == 1: ans.append(i) return ans 

What is the time complexity of the algorithm above?

Details and Assumptions

• $$N$$ : range of numbers
• $$M$$ : number of triangular numbers smaller than $$N$$
• Triangular Numbers are numbers that can be expressed in the form $$n(n+1) / 2$$. The first 5 triangular numbers are 1, 3, 6, 10 and 15.
×