You are not logged in. Please login at www.codechef.com 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

3★dragonemperor
89321135
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.

link

answered 12 Aug '15, 23:09

admin123's gravatar image

5★admin123
1.2k12
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

link

answered 12 Aug '15, 20:10

bradley's gravatar image

3★bradley
6562321
accept rate: 20%

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

link

answered 13 Aug '15, 01:58

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

edited 13 Aug '15, 18:08

I optimised my sieve but still am getting TLE

https://www.codechef.com/viewsolution/7775402

link

answered 13 Aug '15, 16:15

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×5

question asked: 12 Aug '15, 19:55

question was seen: 2,350 times

last updated: 13 Aug '15, 18:08