Skip to content

Instantly share code, notes, and snippets.

@pknowledge
Created June 9, 2020 14:50
Show Gist options
  • Save pknowledge/4dc3446e57f96b636894f1605069d30d to your computer and use it in GitHub Desktop.
Save pknowledge/4dc3446e57f96b636894f1605069d30d to your computer and use it in GitHub Desktop.
Number Theory for Competitive Programming Using Python - Find Divisors Of A Number O(sqrt(n))
# 24 [1,2,3,4,6,8,12,24]
from math import *
def fun1(n):
# T.C = O(n)
div1 = []
for i in range(1,n+1): # [1,n]
if n%i == 0:
div1.append(i)
return div1
def fun2(n):
# T.C = O(root(n))
div2 = set()
for i in range(1,int(sqrt(n))+1): # [1,root(n)]
if n%i == 0:
div2.add(i)
div2.add(n//i)
return list(div2)
t = int(input())
while t:
n = int(input())
div1 = fun1(n)
print(*div1)
div2 = fun2(n)
print(*div2)
t=t-1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment