Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!

# finding factors of a number

Deepika Shet
Greenhorn
Posts: 2
solved

Original Question ...

I need to write a program in Java that takes a positive integer and prints out all ways to multiply smaller integers that equal the original number, without repeating sets of factors. Below is my attempt so far at it. Could anyone provide some pointers?

Ulf Dittmer
Rancher
Posts: 42967
73

First thing I notice is that you're calculating "n / start" a lot. For performance reasons you should retain that value instead of recalculating multiple times. You should also try to avoid division, which tends to be a slow operation compared to multiplication. For correctness reasons you should be aware that dividing integers produces an integer result - possibly not what you want.

Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15207
36
• 1
There are more efficient ways to check if a number is prime. One easy improvement you can make is that the loop (line 59) only needs to go up to the square root of n, not n itself.

Randall Twede
Ranch Hand
Posts: 4363
2
there are two ways really.

calculate it on the fly, or use the sieve of aristophanes(or however that is spelled).sieve

it depends on the situation of the problem. if you need to go there many times use the sieve if not just do it on the fly

Tony Docherty
Bartender
Posts: 2942
59
• 2

For the record the original question was:

I need to write a program in Java that takes a positive integer and prints out all ways to multiply smaller integers that equal the original number, without repeating sets of factors. Below is my attempt so far at it. Could anyone provide some pointers?

Henry Wong
author
Marshal
Posts: 20902
76

I copied the original question back to the first post -- as it is easier to read.

Henry

Ivan Jozsef Balazs
Rancher
Posts: 972
5
Randall Twede wrote:aristophanes(or however that is spelled)[/url]

Aristophanes was an author (he wrote comedies) in ancient Greece.

Eratosthenes (with the prime sieve) was a Greek mathematician, geographer, poet, astronomer, and music theorist.
He was chief librarian of the Great Library of Alexandria, he measured (calculated) the Earth's circumference,
he founded the science of geography. He must have been a remarkable guy!

The difference between them is more than purely spelling...