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.