Java - Puzzle !?

Tyrant^

Hey guys

Just reading through some noob java book and came across this example...

class FindFac
{
	public static void main(String args[])
	{
		for(int i=2; i <= 20; i++)
		{
			System.out.print("Factors of " + i + ": ");
			for(int j = 2; j < i; j++)
			if((i%j) == 0)System.out.print(j + " "); 
			System.out.println();
		}
	}
}

Output:

Factors of 2:
Factors of 3:
Factors of 4: 2
Factors of 5:
Factors of 6: 2 3
Factors of 7:
Factors of 8: 2 4
Factors of 9: 3 
etc...

The code itself executes fine but an extra challenge left for me at the end of the example has left me puzzled !
"In the program, the outer loop runs i from 2 through 100. The inner loop successively tests all
numbers from 2 up to i, printing those that evenly divide i. Extra challenge: The preceding
program can be made more efficient. Can you see how? (Hint: the number of iterations in the
inner loop can be reduced.)"

Ive been stareing at this for about 2+ hours... I assume what it means so that it will only print when there is an actualy factor for the specific number for example it would print like this.

Factors of 4: 2
Factors of 6: 2 3
Factors of 8: 2 4
Factors of 9: 3
etc...

Whats the solution .... I bet its something simple... :rolleyes:

Pygmalion

I don't believe that's what the optimisation is (although that would still be a good one to make :P).
The one I assume they mean would be easier to do (when you get what they mean) but less obvious.

Think for larger numbers, if you had i = 1000000, this program would go all the way from 2 to 999999 testing for factors, which is a huge amount of tests.
Straight away you can see that the highest factor will be half the number (if it's even), less if it's odd, so from 2 to i/2 would be an improvement but still needlessly slow.

What you'd want to do is get it so that the amount of tests you do will stay small, even when the input gets fairly large.
The only hint I can think of is that you'll be getting 2 factors at a time and they won't be in ascending order.

Tillotson

sqrt(x) * sqrt(x) = x

Tyrant^

sorry guys... im still lost
Whats the solution !

ronivek

Well... technically there are many solutions.

At its most basic however; Pygmalion gave you the information you need. No integer greater than (n / 2) can be a factor; so straight away you can effectively halve the number of iterations. I would be surprised if the tutorial wants you to delve into the more mathematical realms of integer factorisation or the utilisation of other data structures.

Tyrant^

Sorry still not getting it .... I cant stress how much of a complete noob I am.

Can someone write up the code ?

fergalr

Sorry still not getting it .... I cant stress how much of a complete noob I am.

If I tell you that one factor of 24 is 2, can you use this to find another factor without searching for it? Is there a quick thing you'd do to tell me the other factor?

You probably think of a second factor as soon as you read that sentence.
If so, what is the second factor that occurs to you? What did you do in your head to find this factor? And how might you write that in code, to save iterations?

If you divide 24 by 2, you get 12, which is another factor of 24. The division is a short cut to get the second factor. So you don't have to go up as far as 12 in your inner loop... Think about how far you do actually have to go - can you terminate your inner loop earlier than 'i'?

As others have pointed out, there are plenty of more complex ways of cutting down the time this sort of thing takes - check out http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes for a simple method that can be used for this sort of thing, that is well explained, and easy to understand. But the exercise doesn't sound like its even after anything that complex.

TeaServer

If you combine what Tillotson and ferghalr have said, you can massively improve the performance of the iterations needed.

Essentially half the factors for any number will be less than or equal to the square root of the number your factoring. Once you have these numbers, you can determine the other half automatically.

In your example you need to factor 100

sqrt(100) = 10 (no need to check any higher than 10 in your iterations)

1 x 100 = 100
2 x 50 = 100
4 x 25 = 100
5 x 20 = 100
10 x 10 = 100

So now you have all factors after only 10 iterations: 1,2,4,5,10,20,25,50,100

Tyrant^

I think this did it

(int j = 2; j [B]<= i/2[/B]; j++)

Havnt seen a condition like that at all in the book so far... so I got confuzzled :eek:

Thanks for the help guys...

On to .... Module 4 Classes + OOP :rolleyes:

theliam

Tyrant^ wrote: »

I think this did it

(int j = 2; j [B]<= i/2[/B]; j++)

Havnt seen a condition like that at all in the book so far... so I got confuzzled :eek:

Thanks for the help guys...

On to .... Module 4 Classes + OOP :rolleyes:

(int j = 2; j [B]<= Math.sqrt(i)[/B]; j++)

ronivek

theliam wrote: »

(int j = 2; j [B]<= Math.sqrt(i)[/B]; j++)

That won't work unless he also changes the body of the loop. I think the issue is not one of mathematical optimisation of the algorithm; but simply experimenting with loop conditions.

Herbal Deity

If the compiler doesn't optimise:

for(int j = 2; j <= Math.sqrt(i); j++)

Then Math.sqrt(i) is going to be computed on every iteration.

Better to do:

double rooti = Math.sqrt(i);
for(int j = 2; j <= rooti; j++)

However, as ronivek said, sqrt(i) won't work here (unless you change the body of the loop like what Teasaver said), as he's looking for all factors, not just prime factors. e.g. 4 is the square root of 16, but 8 is a factor of 16.

But what I've said above applies to i/2 also:

int iover2 = i/2;
for(int j = 2; j <= iover2; j++)

theliam

my bad