programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Eight Divisor Problem

dhrubo bhattacharjee
Greenhorn
Posts: 23
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
• 1
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
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
• 1
This problem comes from Project Euler. The spirit of the project is to do the problems yourself.

Stefan Evans
Bartender
Posts: 1837
10
• 1
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) ?