Counting Divisors from 1 to 10 000

[Juukamen]

Making a program that is counting the Divisors from 1 to 10 000.
My thoughts on it.
Loop 1, i, go trough 1 to 10 000.
Loop 2, j, take the current number from loop 1, and then use i%j, check if the result is 0, and then store the highest divisor count.

here is the code:

public class Divisors {
	public static void main(String[] args) {
		// Setting up Variables
		int bufferInt = 0;
		int bufferDivisors = 0;
		int integer = 0;
		int divisor = 0;
		int howManyNumbers = 10000;
		
		for (int i = 1; i<=howManyNumbers;i++){ // loop 1, counting 1 to 1000
			for (int j = 1; j<=i; j++){ // loop 2, divisor checks
				
				if (i%j == 0){ 
					bufferInt = i;
					bufferDivisors++;
					
					if(bufferDivisors > divisor ){ // saving the higest divisor count resetting the buffers
						divisor = bufferDivisors;
						integer = bufferInt;
						bufferDivisors = 0;
						bufferInt = 0;
						System.out.println("Number "+integer+" and had "+divisor+" divosors");
						
					}// end if
				}// end if
				
			}//end for2
		}// end for1
			
	} // end main
}// end Divisors class

Here are the last lines of the output.

Number 9452 and had 419 divosors
Number 9494 and had 420 divosors
Number 9535 and had 421 divosors
Number 9576 and had 422 divosors
Number 9616 and had 423 divosors
Number 9658 and had 424 divosors
Number 9699 and had 425 divosors
Number 9740 and had 426 divosors
Number 9780 and had 427 divosors
Number 9823 and had 428 divosors
Number 9864 and had 429 divosors
Number 9905 and had 430 divosors
Number 9946 and had 431 divosors
Number 9990 and had 432 divosors

Doupt that is correct at all. Since if I'm not wrong, then 9990 got 32 divisors not 432.
So the is the problem in resetting the bufferDivisor bufferInt or in the for loop..

[Norm]

Have you tested the code with smaller numbers? What was the results?

Have you tried debugging the code? One way is to add println statements to print out the values of variables as the code executes so you can see what the computer i doing.

[Junky]

One issue I can see is that bufferDivisors is only reset to zero inside a nested if statement. If either statement is false, bufferDivisors is not reset to zero. It should always be reset between subsequent numbers.

[.paul.]

my calculations show:

Number 9990 and had 31 divisors

[Zyril]

my calculations show:

Number 9990 and had 31 divisors

That cannot be correct. The mathematical formula gives 32 divisors. Is your code perhaps omitting the first divisor, 1?

[.paul.]

That cannot be correct. The mathematical formula gives 32 divisors. Is your code perhaps omitting the first divisor, 1?

no the last divisor... the OP's code is lucky to be 432 as the counts seem to be sequential.

[Norm]

I'd suggest the OP re-do his algorithm and test it with a smaller number like 10 or 20 until it generates the right results.

[.paul.]

That cannot be correct. The mathematical formula gives 32 divisors. Is your code perhaps omitting the first divisor, 1?

as a matter of interest, what is the formula you used?

[Juukamen]

One issue I can see is that bufferDivisors is only reset to zero inside a nested if statement. If either statement is false, bufferDivisors is not reset to zero. It should always be reset between subsequent numbers.

Here is the changes

for (int i = 1; i<=howManyNumbers;i++){ // loop 1, counting 1 to 1000
bufferInt = 0;
bufferDivisors = 0;
for (int j = 1; j<=i; j++){ // loop 2, divisor checks

and for the fun of it, I made a change in the IF statment

if(bufferDivisors >= divisor ){

Here is the outut

Number 7560 and had 61 divosors
Number 7560 and had 62 divosors
Number 7560 and had 63 divosors
Number 7560 and had 64 divosors
Number 9240 and had 64 divosors

The complete program if it will help others in the furure.

public class Divisors {
	public static void main(String[] args) {
		// Setting up Variables
		int bufferInt = 0;
		int bufferDivisors = 0;
		int integer = 0;
		int divisor = 0;
		int howManyNumbers = 10000;
		
		for (int i = 1; i<=howManyNumbers;i++){ // loop 1, counting 1 to 1000
			bufferInt = 0;
			bufferDivisors = 0;
			for (int j = 1; j<=i; j++){ // loop 2, divisor checks
				
				if (i%j == 0){ 
					bufferInt = i;
					bufferDivisors++;
					
					if(bufferDivisors >= divisor ){ // saving the higest divisor count resetting the buffers
						divisor = bufferDivisors;
						integer = bufferInt;
						System.out.println("Number "+integer+" and had "+divisor+" divosors");
						
					}// end if
				}// end if
				
			}//end for2
		}// end for1
			
	} // end main
}// end Divisors class

[Norm]

Is the output correct? It seems strange that the count of divisors goes up by one for each number.

For easier way to verify the testing set howManyNumbers to 20.

Comment on loop variables: i & j are not very descriptive. How about:

        for (int aNbr = firstNbr; aNbr <= lastNbr; aNbr++){ // loop 1, counting 1 to 1000
  
            for (int aDvsr = 1; aDvsr <= aNbr; aDvsr++){    // loop 2, divisor checks

                if (aNbr % aDvsr == 0){

[Zyril]

as a matter of interest, what is the formula you used?

Sorry for not replying earlier to you, I forgot about this thread. Also I apologize for posting an "off topic" reply, even though it has some correlation to the subject of the thread itself.

This is the method that my algebra teacher taught us when we needed to do some statistical analysis. The method gives you only the numbers of divisors, not which numbers.

Take the number that you want to find the NUMBER of divisors from.

Let's start with 80.
Use prime factorization to form this number.

2 * 40 = 80
2 * 2 * 20 = 80
2 * 2 * 2 * 10 = 80
2 * 2 * 2 * 2 * 5 = 80 (All factors are PRIME!)

We can now write this as 2^4 * 5^1, right?
The exponents are 4 and 1. Add one to each of these exponents and then multiply them. This gives us new exponents 5 and 2, and multiplied together it's 10. Therefor, the number of divisors of 80 is 10.

---

Now, if we want to apply this to a larger number such as 9990, one must be able to remember how many exponents you have, and also be quite good at seeing what number you can divide something with.

Let's try:

2 * 4995 = 9990
Since we can't divide 4995 further on with 2, we go up in prime factors to 3.
2 * 3 * 1665 = 9990.
2 * 3 * 3 * 555 = 9990
2 * 3 * 3 * 3 * 185 = 9990
Since we can't divide 185 further on with 3, we go up in prime factors to 5.
2 * 3 * 3 * 3 * 5 * 37 = 9990 (All factors are PRIME!)

We have 2^1 * 3^3 * 5^1 * 37^1, which gives us the exponents of 1, 3, 1 and 1. Add one to each --> 2, 4, 2, 2. Multiply them together, you get 32. This is the number of divisors of 9990.

To sum it up, this gives you the formula:

n = p₁^a1 * p₂^a2 * p₃^a3 * p₄^a4 * p_k^ak

Then the number of divisors is:

Dn = (a1 + 1)(a2 + 1)(a3 + 1)(a4 + 1)...(ak + 1)

--

When you've done it a few times it's actually quite easy. Just know your math and multiplication and you will be fine! There are cheats to this aswell! =)

[.paul.]

@Zyril. thanks, works great...

[Zyril]

You are welcome!

If you like math, I think it's quite cool! :P