• Post Reply Bookmark Topic Watch Topic
  • New Topic

Eight Divisor Problem  RSS feed

 
dhrubo bhattacharjee
Greenhorn
Posts: 23
Eclipse IDE Java Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello everyone,

I started learning java recently and was trying to solve some problems from Project Euler.I got stuck with one problem for which I need help .

The eight divisors of 24 are 1, 2, 3, 4, 6, 8, 12 and 24. The ten numbers not exceeding 100 having exactly eight divisors are 24, 30, 40, 42, 54, 56, 66, 70, 78 and 88. Let f(n) be the count of numbers not exceeding n with exactly eight divisors.You are given f(100) = 10, f(1000) = 180 and f(10^6) = 224427.Find f(10^12).


Here is my code so far :



I have tried till f(10^6) and the total running time is around one hour!!!Can you please suggest if there are any options to make this code run faster?



Thanks.
 
Ron McLeod
Bartender
Posts: 1603
232
Android Angular Framework Eclipse IDE Java Linux MySQL Database Redhat TypeScript
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Once count exceeds 8, there is no point to keep checking. There is also no use in checking any further when the divisor reaches half the value of the number under test.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi dhrubo,

well, there are these exercizes for which brute force simply won't work,
because of the runtime and/or memory usage.
In such cases there is no alternative: go Googling for some theory,
who knows you might get into totient functions or worse!

But this particular exercise is not exactly the first one. Can't you start
with some simpler excercizes?

Greetz,
Piet

 
Knute Snortum
Sheriff
Posts: 4289
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This problem comes from Project Euler. The spirit of the project is to do the problems yourself.
 
Stefan Evans
Bartender
Posts: 1837
10
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would look into caching results in some way. Maybe some dynamic programming.

The trick is in calculating the divisors of a number in an efficient manner.

For instance can you calculate the divisors of 24 given that you know the divisors of 2 (1,2) and divisors of 12 (1,2,3,4,6,12) ?



 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!