5 replies to this topic

[liamzebedee]

How would I find the number of divisers/factors for a positive integer. I would like the code in Java but I put this in general programming because I really would just like the algorithm.

[liamzebedee]

Don't worry I figured it out-

public static int num(int n){

		int q = 0; 

		ArrayList<Integer> factors = new ArrayList<Integer>();

		 factors.add(n);

		 factors.add(1);

		 q += 2;

		 for(int test = n - 1; test >= Math.sqrt(n); test--)

		  if(n % test == 0)

		  {

		   factors.add(test);

		   factors.add(n / test);

		   q += 2;

		   

		  }

		 return q;

		 }

[fayyazlodhi]

The general solution approach above is correct except may be a few amends:

For e.g. will it work correctly when factors are repeated e.g. 12 or 8?

As a general approach we should be reducing the actual number as we move along
i.e. if 10%5 is zero, add five to factors and the new number should be 2 i.e. 10/5. Try dividing again by the same number before proceeding to next until it is no longer perfectly divisible.

Note: I didn't test the code thoroughly, these are just quick thoughts that came to mind upon skimming the solution

[WingedPanther]

More importantly, the factors for 25 should be 1, 5, and 25, but I suspect it will return 1, 5, 5, and 25.

[Momerath]

WingedPanther said:

More importantly, the factors for 25 should be 1, 5, and 25, but I suspect it will return 1, 5, 5, and 25.

It also returns 1,1 for an input of 1.

On a side note, why count the factors? Doesn't the java ArrayList have a count property?

[lethalwire]

David Pollack of this forum (link below) explains how to calculate the # of factors for a number.

is there a formula to calculate the number of factors? • Manhattan GMAT Forums

In short, calculate the prime factors of your number. For each prime factor, count how many times you *see* it and add 1. Then multiply all these numbers together

Example:
Number: 6078814
Prime factors = [2, 7, 434201]
2 appears 1 time.
7 appears 1 time.
434201 appears 1 time.

Take your underlined numbers and add 1 to each, then multiply them together.
1 + 1 = 2
1 + 1 = 2
1 + 1 = 2
2 * 2 * 2 = 2^3 = 8.
There are a total of 8 factors for the number 6078814.

Example:
Number: 943823181546
Prime factors = [2, 3, 3, 7, 23, 151, 1063, 2029]

2 appears 1 time
3 appears 2 times
7 appears 1 time
23 appears 1 time
151 appears 1 time
1063 appears 1 time
2029 appears 1 time.
1 + 1 = 2
2 + 1 = 3
1 + 1 = 2
1 + 1 = 2
1 + 1 = 2
1 + 1 = 2
1 + 1 = 2

2*2*2*2*2*2*3 = 2^6 * 3 = 64 * 3 = 192 factors.

Edited by lethalwire, 23 May 2011 - 04:08 PM.