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
defanti_tri(N):# L[i] = 1 implies i is not divisible by any triangular number > 1L=[0]+[1]*NT=3# triangular numberi=3whileT<=N:foriinrange(T,N,T):L[i]=0T+=ii+=1ans=[]foriinrange(N+1):ifL[i]==1:ans.append(i)returnans
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.
Excel in math and science
Master concepts by solving fun, challenging problems.
It's hard to learn from lectures and videos
Learn more effectively through short, interactive explorations.
Used and loved by over 6 million people
Learn from a vibrant community of students and enthusiasts,
including olympiad champions, researchers, and professionals.
Your answer seems reasonable.
Find out if you're right!