posted 2 years ago

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 .

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.

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.

posted 2 years ago

- 1

Once count exceeds

*, 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.***8**
Piet Souris

Master Rancher

Posts: 2044

75

posted 2 years ago

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

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

posted 2 years ago

- 1

This problem comes from Project Euler. The spirit of the project is to do the problems yourself.

All things are lawful, but not all things are profitable.

Stefan Evans

Bartender

Posts: 1837

10

posted 2 years ago

- 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) ?

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) ?