Win a copy of Cross-Platform Desktop Applications: Using Node, Electron, and NW.js this week in the JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

program that return the number with most divisors.  RSS feed

 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i am having a problem writing a program that will return the number with most divisors in 10000. that is; a number between 0 and 10000 that has the most numbers of divisors.
anyone to help, please.
 
Junilu Lacar
Sheriff
Posts: 10948
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What exactly is your problem? What have you tried? Please TellTheDetails (←click that, it's a link)

Just a reminder: We don't allow folks in these forums to give out full solutions to questions like this. The Ranch is NotACodeMill (←another link)
 
fred rosenberger
lowercase baba
Bartender
Posts: 12529
48
Chrome Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The first step is to figure out how to do this by hand.  Writing the actual java code is the easy part. The hard part is writing out the steps you would take if you had to do this using pencil and paper.  And then re-writing those steps such that a 10yr old child could follow them

You want to break this down into methods that each do one simple thing, and do it well.  If you can't give a method a simple name that clearly explains exactly what it does, it's probably doing too much.  For example, I'd consider writing a method named:

public int divisorCount(int number)

So this method would take an int, and would return an int that is tee number of divisors the input number has.

Now, this method may need to call several other methods...i've not though through that part yet. But once I wrote this method, and tested it on a bunch of inputs, I could easily call it on the numbers 1-10000 (or really, anything).  Then it's not to hard to keep track of which number returns the most divisors.
 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:What exactly is your problem? What have you tried? Please TellTheDetails (←click that, it's a link)

Just a reminder: We don't allow folks in these forums to give out full solutions to questions like this. The Ranch is NotACodeMill (←another link)

sure i understand the concepts , i have tried many things but nothing seems to work, and as am still a beginner , all i need was just an idea, not the answer.
 
Stephan van Hulst
Saloon Keeper
Posts: 7713
141
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
When I read the title, the first idea that popped into my head was to perform prime factorization on the integer under test. The number of divisors is then the number of combinations of prime factors with repetition, I think. I don't know if that's mathematically correct, but it's an avenue you can explore.

https://en.wikipedia.org/wiki/Prime_factor
https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition
 
Stephan van Hulst
Saloon Keeper
Posts: 7713
141
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Let's see... The prime factorization of 90 is [2,3,3,5]. This means that the divisors of 90 are:

I was mistaken. It's not the number of combinations with repetition, but it might still give you some insight in how to approach this problem.
 
Stephan van Hulst
Saloon Keeper
Posts: 7713
141
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A simple heuristic for determining the integer with the most divisors would be to simply count the number of factors in the prime factorization, but it's not completely accurate if the factorization contains many duplicates:

ValuePrime factorizationDivisors
30[2,3,5]1, 2, 3, 5, 6, 10, 15, 30
81[3,3,3,3]1, 3, 9, 27, 81

This implies that the best heuristic is h(x,y) = f(x) - g(y), where x is the number of prime factors, and y is the number of duplicate prime factors. f(x) and g(y) are for you to determine.
 
Henry Wong
author
Sheriff
Posts: 23275
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:
This implies that the best heuristic is h(x,y) = f(x) - g(y), where x is the number of prime factors, and y is the number of duplicate prime factors. f(x) and g(y) are for you to determine.


Pretty interesting study. IMHO, mathematically, I think you did *all* the heavy lifting for the OP. Have some cows.

Henry
 
Knute Snortum
Sheriff
Posts: 3942
92
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
adebari olalekan wrote:
Junilu Lacar wrote:What exactly is your problem? What have you tried? Please TellTheDetails (←click that, it's a link)

Just a reminder: We don't allow folks in these forums to give out full solutions to questions like this. The Ranch is NotACodeMill (←another link)

sure i understand the concepts , i have tried many things but nothing seems to work, and as am still a beginner , all i need was just an idea, not the answer.

Can you post your latest attempt?  And UseCodeTags (that's a link).
 
fred rosenberger
lowercase baba
Bartender
Posts: 12529
48
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
of course, brute force also works.  for a given number, try dividing it by every number up to it's sqaure root and see if it goes evenly. For every number OTHER than the square root, you get two divisors.
 
Vitalii Plagov
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If I understand the condition right, this task is similar to the one when you find the minimum or maximum number in the array. First, you set as a targetNumber first number from the array. Then goes the loop. Inside the loop, you take each number and calculate its divisors. Compare the number of divisors of the current number with the number of divisors of the previous number. And so on.

Are you asking more for a design of this class, or rather for an algorithm itself?
 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:
adebari olalekan wrote:
Junilu Lacar wrote:What exactly is your problem? What have you tried? Please TellTheDetails (←click that, it's a link)

Just a reminder: We don't allow folks in these forums to give out full solutions to questions like this. The Ranch is NotACodeMill (←another link)

sure i understand the concepts , i have tried many things but nothing seems to work, and as am still a beginner , all i need was just an idea, not the answer.

Can you post your latest attempt?  And UseCodeTags (that's a link).


this is what i have tried , i try to create a method that will recieve a parametre and evaluate on the parametre and then store it in an array; then am planning on just looking for the greatest numbers in the array
but i stopped halfway because i realized it wont work.



i know it doesnt work, and it does not even compile, it returns::

>
 
Henry Wong
author
Sheriff
Posts: 23275
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
adebari olalekan wrote:
i know it doesnt work, and it does not even compile, it returns::


Your code, declares a store array size, of zero elements. So, later, when you try to get the second element, as index one, you get an array out of bounds condition.... since, obviously, an array for zero elements, doesn't have a second element.

Anyway, as already mentioned, the solution is more about math, than about Java code. Do you understand the math? Or are you attempting to just brute force through the problem? For the latter, it can take a lot of time...

I highly recommend that you take a step back, and take a look at the mathematical discussion, that has already taken place in this topic.

Henry
 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Henry Wong wrote:
adebari olalekan wrote:
i know it doesnt work, and it does not even compile, it returns::


Your code, declares a store array size, of zero elements. So, later, when you try to get the second element, as index one, you get an array out of bounds condition.

Anyway, as already mentioned, the solution is more about math, than about Java code. Do you understand the math? Or are you attempting to just brute force through the problem? For the latter, it can take a lot of time...

Henry


yea, the math has been the problem; and that is why i didnt post my trials earlier. i discovered it is about maths , but i cant seem to wrap around the mathematical concept that could solve the problem. i know if i can get it mathematically , then it will be easy to implement into java code.
 
Henry Wong
author
Sheriff
Posts: 23275
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
adebari olalekan wrote:
yea, the math has been the problem; and that is why i didnt post my trials earlier. i discovered it is about maths , but i cant seem to wrap around the mathematical concept that could solve the problem. i know if i can get it mathematically , then it will be easy to implement into java code.


Take a look at Stephan's posts. His analysis pretty much explains, in my opinion, the majority of the math. If you have any questions regarding it, then feel free to follow up the discussion in this topic.

Henry
 
Paul Clapham
Sheriff
Posts: 22374
42
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:I was mistaken. It's not the number of combinations with repetition, but it might still give you some insight in how to approach this problem.


However, if you have the prime factorization of a number there is a very simple rule which yields the number of divisors of that number. As you already saw, the power of each prime in the factorization plays a key role.
 
Piet Souris
Rancher
Posts: 1943
66
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I must say that the formula for the number of divisors, given the prime factorization, is not simple at all (well, it is not rocket science too).
For instance, say we have a factorization with two primes, each of multiplicity 2. We have then 9 divisors. If we have a factorization, again of two primes, with multiplicity 3 and 1 respectively, then we have 8 divisors.
In both cases we have 4 primes, giving us 2^4 subsets, in principle giving us 16 divisors.
In the (2, 2) case, we seem to subtract 8 divisors to get the actual number of divisors, in the (3, 1) case we seem to subtract 7 divisors to get the number of divisors.
What very simple formula are we then talking about?

I could not remember a formula that gave me the unique number of subsets of a set, given that duplicate elements might be present. So I derived this simple scheme:

Suppose we have a set with N equal elements a. Then we can form N unique subsets. For instance, say we have this set: [2, 2, 2], then the unique subsets are [2], [2, 2] and [2, 2, 2]. 3 in total.
Now suppose that we add M b's to this set. How many uniques subsets do we get then? First of all, the M b's give us M new subsets ([b], [b, b], et cetera). Then, for each of the N existing subsets (with only a's), we can add M subsets with only b's (for instance: [a, a] and [b] give me a new subset [a, a, b]).
The new total is therefore: N (the existing number) + M (from the added b's) + N * M (to each of the N subsets with a we add M subsetswith b's).

What has all this to do with the assignment? Well, if we have the set [a, a, b], then you may read that as the set [3, 3, 5], where the prime 3 has multiplicity 2 and 5 has multiplicity 1.

According to the above, the number 45 has two primes 3 and one prime 5. The formula gives us:

for the prime 3: 2 unique subsets.
adding 5: 1  new subset ([5]) + 2 existing subsets + 2 * 1 = 5.

So, we have 5 divisors. But hang on: 45 has 6 divisors: 1, 3, 5, 9, 15, 45! Indeed, in the derived formula we left '1' out of the picture. It is not a prime (therefore we neglected it), but it is a divisor.
To our formuls: M + N + M*N, we must add 1 to get the correct number.

If we look at Stephans examples, we have:

30 = [2, 3, 5]. The derivation gives us:
for the 2: 1 subset
including the 3: 1 + 1 + 1 * 1 = 3
including the 5: 3 + 1 + 1 * 3 = 7.
Adding 1 to the outcome, we get 8 divisors.

81 = [3, 3, 3, 3]
for the 3 we get: 4 subsets.
adding 1 we get 5 divisors.

Now, this is the simplest I could come up with. I will think about the 'very simple rule' for deriving the number of divisors. Maybe I have forgotten, or have been overlooking, something quite simple.

Edit: wasn't this a Project Euler assignment? If so, I must have solved it, but how? I'll have a look and if I find something really clever, I will report.
 
Stephan van Hulst
Saloon Keeper
Posts: 7713
141
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It really is quite simple though. Look at the formula you would need if your number can be factored as a power of a single prime. Now see if you can extend that formula to cases with distinct prime factors.
 
Paul Clapham
Sheriff
Posts: 22374
42
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What simple formula? If the prime factorization is p1^a1 * p2^a2 * ... * pn^an then the number of divisors is (a1+1) * (a2+1) * ... * (an+1).
 
Stephan van Hulst
Saloon Keeper
Posts: 7713
141
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think that's pretty simple :P

Anyway, Adebari Olalekan, if you've followed the discussion so far, you have seen that you need to perform prime factorization. Here's a quick outline on how to do that:

Create a class that represents the prime factorization. It must hold the number of factors per prime number. I suggest using a Map<Integer, Integer> internally.

Write an algorithm to perform the factorization. Divide the number by primes, starting with 2 and going up, until the remainder is 1. Each time you can divide the number, add the prime divisor to the factorization.

To do this, you need to be able to generate prime numbers. This is the first challenge you should start with. Do you know how the Sieve of Erastosthenes works?
 
Henry Wong
author
Sheriff
Posts: 23275
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Honestly ... I am actually starting to lean towards a brute force solution...

First, the mathematics route is definitely the more elegant route. Second, the mathematics route is most likely the quicker route in terms of running time. And third, in my opinion, the mathematics solution is definitely the most interesting solution. If I had to do it, I can see myself spending time to do this on paper first, working on the math.

On the other hand, for reasonable small numbers, it is debatable if brute forcing the solution is slower (in running time). Also, the code necessary to figure out the primes is very similar code to figure out the divisors. Granted, going to primes may be "quicker" as there are less of them, but then, permutations/combinations will need to be done to get to the divisors. It is debatable if figuring out the primes and then calculating the number of divisors, is quicker than figuring out the divisors.

The pragmatic side of me is thinking that brute force isn't all that bad...

Henry
 
Tobias Bachert
Ranch Foreman
Posts: 85
18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I also tend to brute force for this task as it is significantly easier to implement, but would tend to brute force the prime factors instead of the divisors.
The advantage of brute forcing prime factors is that it has significantly better performance in the best case:
When brute forcing the factors the border to iterate to is reduced with each found prime factor (-> has to iterate to max(second largest factor of x, sqrt(largest factor of x))), whereas brute forcing divisors has to always iterate to sqrt(x). (Of course brute force cannot compare with e.g. pollard-rho for products of larger prime factors such as 9223371994482243049 (on my pc ~10 seconds (skipping multiples of 2 and 3) vs <.01 seconds), but should be sufficient for the required range.)
And as Henry already stated, the code to find prime factors is quite similar to the code required to find divisors. (There is no need to sieve/generate prime numbers, trial division is sufficient to find prime factors (preferable with a small wheel to skip multiples of 2 or 2 and 3 etc., which makes brute forcing prime factors always faster than brute forcing divisors as the latter cannot skip values).)

Alternatively one could try to turn the whole process around and generate the number with the most factors by maximizing the value of (a1+1) * (a2+1) * ... * (an+1) for the specific range without actually calculating the number of divisors for each number in the range.
 
adebari olalekan
Ranch Hand
Posts: 61
Chrome Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:I think that's pretty simple :P

Anyway, Adebari Olalekan, if you've followed the discussion so far, you have seen that you need to perform prime factorization. Here's a quick outline on how to do that:

Create a class that represents the prime factorization. It must hold the number of factors per prime number. I suggest using a Map<Integer, Integer> internally.

Write an algorithm to perform the factorization. Divide the number by primes, starting with 2 and going up, until the remainder is 1. Each time you can divide the number, add the prime divisor to the factorization.

To do this, you need to be able to generate prime numbers. This is the first challenge you should start with. Do you know how the Sieve of Erastosthenes works?

no, i dont know how the sieve works but i will check online.
 
Piet Souris
Rancher
Posts: 1943
66
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It was indeed a very simple formula, one that immediately comes to mind if you cannot remember it or have never seen it before.

But here you do not need complex prime factorization. As is clear from my subsets analogy, you get the most divisors when you have as many unique primes as possible (given N elements, the maximum number of subsets is 2^N, which you get when all elements are unique). Since N <= 10_000, the maximum prime number to take into account is 13. Now, you get as many primes as possible if you keep them as small and as unique as possible. A simple spreadsheet and some tries are sufficient for this.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!