Integer(s) R from N to M with maximum number of divisors. 2<=N<

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 1454 Views - Last Post: 15 December 2016 - 03:41 PM Rate Topic: -----

#1 McPrince  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 14-December 16

Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 14 December 2016 - 12:15 PM

Write a c++ or c program that finds the integer R from N to M which has the maximum number of divisors, how many divisors it has, and how many numbers have that number of divisors. 2<=N<M<=1000. My Problem: For instance, for N = 2, M = 9, the program displays: 6 as the integer with maximum number of divisors. It has 2 divisors but 8 also has the same. What do I need to do so it show other integers that also have the same maximum number of divisors. Please find below the program I wrote. Thanks.

#include <iostream>
using namespace std;

int main()
{
int number, n;          
int divisor, d;         
int remainder, r;         
int divisors_count, c = 0;      
int nd = 0;     
int cd = 0;  
int N;
int M;
cout<<"Enter N, "<<endl;
cin>>N;
cout<<"Enter M, "<<endl;
cin>>M;

cout << "This program finds the integer R from N to M (2<=N<M<=1000)\n";
cout << "and the integer R has the maximum number of divisors.\n";
 
try
{
	if(N<2||N>1000)
	throw(M);
	else if(M>1000||M<2)
	throw(0.1);
	else
	{
	for(n = N; n <= M; n++)
	{
	for(d = 2; d < n ; d++)
	{
	r = n % d;
	if (r == 0)
	{
	c++;
	}
	}
	if (cd < c)
	{
	cd = c;
	nd = n;
	}
	c = 0;
	}
	cout << "The integer R is " << nd << "." << '\n';
	cout << "It has " << cd << " divisors." << '\n';
	}
}
catch(int)
{
	cout<<"N must be more than 1, equal or more than 2 but less than 1000, "<<endl;	
}
catch(double)
{
	cout<<"M must be less than or equal to 1000 and more than 2, "<<endl;
}

return 0;
}

:code:

This post has been edited by modi123_1: 14 December 2016 - 12:25 PM
Reason for edit:: In the future, please use the [code] tag button.


Is This A Good Question/Topic? 0
  • +

Replies To: Integer(s) R from N to M with maximum number of divisors. 2<=N<

#2 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5823
  • View blog
  • Posts: 19,821
  • Joined: 05-May 12

Re: Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 14 December 2016 - 01:40 PM

So instead of just capturing the maximum so far, you'll need to keep a list of number than also match that maximum. Each time the maximum is replaced, clear the list and add the number with that new maximum. Since you are assured that N < M <= 1000, you'll never have to store more than 1000 items in your list. In fact the most you'll have to possibly store would be M - N numbers, so an array would suffice. You wouldn't need to dynamically allocate the array to hold the list. Of course, since you are using C++, you shouldn't even be doing the dynamic allocation yourself. Just use the standard STL containers.
Was This Post Helpful? 3
  • +
  • -

#3 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3695
  • View blog
  • Posts: 13,355
  • Joined: 08-August 08

Re: Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 14 December 2016 - 04:47 PM

I suggest using functions and better indenting to make your code more readable. Readable code is easier to debug.
Was This Post Helpful? 3
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

Re: Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 14 December 2016 - 05:18 PM

This actually has the feel of a dynamic programming problem. Primes clearly have one prime divisor. Every integer is the distinct product of primes. So you simply "glue" a prime factor onto a previous integer. The lookup table manages the previous prime factorization.

Perhaps some folks will have some number theoretic optimizations in mind.
Was This Post Helpful? 0
  • +
  • -

#5 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3695
  • View blog
  • Posts: 13,355
  • Joined: 08-August 08

Re: Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 14 December 2016 - 05:21 PM

My impression was that there's a distinction between prime factors and divisors. So for example, 2 and 8 are divisors of 16, but 2 is the only prime factor.
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

Re: Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 14 December 2016 - 05:37 PM

That is correct. But the Fundamental Theorem of Arithmetic tells us that every natural number has a unique prime factorization. So the divisors are formed by products of prime powers that divide our selected integer.

In particular, if n = \prod_{i=1}^{k} p_{i}^{a_{i}}, there is a bijection between divisors of n and the sub-multisets of \{ 1^{a_{1}}, 2^{a_{2}}, ..., k^{a_{k}} \}. These objects are well studied in combinatorics.

This post has been edited by macosxnerd101: 14 December 2016 - 05:41 PM

Was This Post Helpful? 1
  • +
  • -

#7 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5823
  • View blog
  • Posts: 19,821
  • Joined: 05-May 12

Re: Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 14 December 2016 - 06:24 PM

But would it be faster to compute the prime factors and then compute the number of combinations from those prime factors? Or would be faster to do brute force count of divisors for a number like our OP is currently doing?
Was This Post Helpful? 0
  • +
  • -

#8 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5823
  • View blog
  • Posts: 19,821
  • Joined: 05-May 12

Re: Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 14 December 2016 - 06:56 PM

I'm brain fried after a long day of fighting servers, fires, and this stupid cold so take what I write next with a huge boulder of salt.

Just looking at the micro level of finding the divisors for a single number, the brute force trial divisions approach looks to be O(n).

The approach of prime factorization and then computing combinations looks to be (based on Google searches because I'm not that smart) O(n*log(log(n))) + O(n). The first term is the cost of sieving for prime factors, and the second term is the loop to compute the sum of various combinations.
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

Re: Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 14 December 2016 - 07:09 PM

If an integer n is prime, then we know this after sieving and we are done. Otherwise, we simply need to find a prime factor p of n, which takes O(sqrt(n)) time. Then we can look up the number of divisors of n/p. We know that p has one prime divisor.

Actually, I remember writing a blog entry on counting divisors. The tau function will be helpful in computing the number of divisors for base cases.

I should also add that I'm not a number theorist, and my number theory book is back at school (I'm home on break). So take some of what I say with a grain of salt.

This post has been edited by macosxnerd101: 14 December 2016 - 07:09 PM

Was This Post Helpful? 2
  • +
  • -

#10 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3695
  • View blog
  • Posts: 13,355
  • Joined: 08-August 08

Re: Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 14 December 2016 - 08:38 PM

If you find all prime factors and not just all primes that are factors, you could use them to compute all divisors. Back to my example: N = 16. It has one prime factor: 2 that appears three times. You can check its products to find other divisors:
2*2
2*2*2

If N = 588 we have three prime factors: 2,3, and 7 that appear:
2*2*3*7*7
Now we can multiply the first and second, first and third, first and fourth, etc. to get the rest of the factors:
4, 6, 12, 14, 21, 28, etc.

I'd use a map<int, bool> to hold the divisors so that duplicates (2*7 would appear four times in this example) won't be a problem.
Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

Re: Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 14 December 2016 - 08:52 PM

Once you have a prime factorization (you could use a map<int, int>), it comes down to using the fact that the tau function from my blog entry is multiplicative. You don't have to explicitly compute the divisors, just count them.
Was This Post Helpful? 0
  • +
  • -

#12 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5823
  • View blog
  • Posts: 19,821
  • Joined: 05-May 12

Re: Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 14 December 2016 - 10:08 PM

View Postmacosxnerd101, on 14 December 2016 - 09:09 PM, said:

If an integer n is prime, then we know this after sieving and we are done. Otherwise, we simply need to find a prime factor p of n, which takes O(sqrt(n)) time. Then we can look up the number of divisors of n/p. We know that p has one prime divisor.

Actually, I remember writing a blog entry on counting divisors. The tau function will be helpful in computing the number of divisors for base cases.

I should also add that I'm not a number theorist, and my number theory book is back at school (I'm home on break). So take some of what I say with a grain of salt.


I must be really tired and not thinking straight. Let's take for granted that the amortized cost of sieving is O(1) and the Tau() lookup is also an amortized O(1), my instincts (or all the cold and pain medicine I'm taking) makes me think something is still amiss here.

Using n = 12, 12 is not prime. So we try to find a prime that is a factor of 12. 2 is a factor of 12. So let p = 2, and q = 6:
Tau( n) == Tau(p) * Tau(q)
Tau(12) == Tau(2) * Tau(6) 
   6    ==   2    *   4
   6    !=        8


Oops!

Okay, so the blog said that p and q needed to be relatively prime to each other. So let's try p = 3, and q = 4:
Tau(12) == Tau(3) * Tau(4) 
   6    ==   2    *   3
   6    ==        6


That's more like it!

But what about n = 36? Trying p = 3 and q = 12 (yes I know they are not relatively prime, but the best we can do following the approach of just finding a prime):
Tau(36) == Tau(3) * Tau(12) 
   9    ==   2    *   6
   9    !=       12



Trying for relatively prime: p = 9 and q = 4
Tau(36) == Tau(9) * Tau(4) 
   9    ==   3    *   3
   9    ==        9


Yay!

So it seems like we are forced to find relatively prime numbers to get the benefits of quick O(1) lookup and multiplication of Tau() values. Using the Euclidean algorithm to check for relatively primes will be an added O(N) term that will override the O(sqrt(N)) search for a prime.

So now we have relatively complex O(N) vs. much easier to understand brute force O(N). Is this when you start doing profiling runs to see if the juice is worth the squeeze for actual wall clock time advantage vs. maintaining the more complex code?
Was This Post Helpful? 1
  • +
  • -

#13 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

Re: Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 14 December 2016 - 11:01 PM

You can design a NaturalNumber class with attributes map<int, int> for a prime factorization, an int for the actual value of the natural number, and an int for the number of divisors. That alleviates the need to factor n/p, as it is already factored when you look up its NaturalNumber object.

You'll want to construct these NaturalNumber objects using dynamic programming techniques. This is where the challenging computations come in. Sieving is O(1), since M, N <= 1000- just sieve up to 1000 and be done.
Was This Post Helpful? 2
  • +
  • -

#14 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3695
  • View blog
  • Posts: 13,355
  • Joined: 08-August 08

Re: Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 14 December 2016 - 11:37 PM

I don't know, but I think the code below is easier to understand than the brute force method, even if it is beyond the OP at the moment. It might be slower on a first run, but if you have multiple numbers to test and you start with the largest, calculating the needed primes only needs to be done once, so that might make up the difference.

Spoiler

@OP: This might be too much too soon, so see if you can figure it out before looking at the code.

Also, I'm doing a modified portion of your task, showing the divisors instead of counting them and keeping track of their number.
Was This Post Helpful? 0
  • +
  • -

#15 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5823
  • View blog
  • Posts: 19,821
  • Joined: 05-May 12

Re: Integer(s) R from N to M with maximum number of divisors. 2<=N<

Posted 15 December 2016 - 06:51 AM

To guarantee O(1) runtime prime sieving since we know our maximum, check out this use of C++ template meta programming to let the compiler generate the primes at compile time: Compile-time sieve of Eratosthenes

Or you could just paste in all the primes less than 1000 like this guy did, but that has a low refuctoring score. :)
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2