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, conceptual quizzes.
Our wiki is made for math and science
Master advanced concepts through explanations,
examples, and problems from the community.
Used and loved by 4 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!