You are not logged in. Please login at to post your questions!


Efficient way to find number of divisors for problem D1

Problem code
My solution

I am getting a TLE error. I am following the tutorial for it. I think my number of factors generation is slow. Is there any other problem? What is the most optimized method for generating the number of factors?

p.s. sqrt(n) approach gives TLE (as mentioned in editorial too)

asked 12 Aug '15, 19:55

dragonemperor's gravatar image

accept rate: 10%

Hi dragonemperor,

i didn't solve this problem but i can tell something about your solution

in your prime generator function you have j = i+i so make it j=i*i .

and rather than generating all primes upto MAX just generate upto sqrt(MAX) only because if number have no factor in range ( 2 to sqrt(n) ) then that number will be prime and after removing all factor less than sqrt(n) if that number is still greater than sqrt(n) means current value is prime.


answered 12 Aug '15, 23:09

admin123's gravatar image

accept rate: 28%

Brother, it is very effective way to calculate factors, you may be doing some mess with it.

Kindly refer to this link, for detail, and study completely (don't skip :) )

Integer Factorization


answered 12 Aug '15, 20:10

bradley's gravatar image

accept rate: 20%

please look at this link and tell me why I got WA...D1


answered 13 Aug '15, 01:58

rcsldav2017's gravatar image

accept rate: 6%

edited 13 Aug '15, 18:08

I optimised my sieve but still am getting TLE


answered 13 Aug '15, 16:15

dragonemperor's gravatar image

accept rate: 10%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 12 Aug '15, 19:55

question was seen: 2,350 times

last updated: 13 Aug '15, 18:08