DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

1. Registered User
Join Date
Jan 2006
Posts
6

## factoring problem

Hi,

I am having trouble trying to factor 999999, i need to only print out the prime number factors of 999999 but right now I am just working on getting all the factors to printout. The first factor that is printed is 2 which obviously isn't correct because since I have both n and i declared as int. Then 3 isn't even printed which should be the first factor. Is this a problem in my first if statement? Please check my code, thanks for your help

int n=999999;
int i;
for (i=2; i<37; i++)
{

if (n%i ==0);
{
System.out.print(i +" ");
n=n/i;
System.out.print(n +" ");
i++;
}
if (n%i !=0)
i++;
}

2. Registered User
Join Date
Feb 2006
Posts
11
Factoring a number is actually fairly complicated. What does your algorithm look like? I think if you write it out, not only will it help us help you, but will help you figure out what you're doing wrong. (I couldn't clearly see where you're going. Something is wrong since you're looking that the modulus twice, when in your loop you should only need to do it once.)

3. Registered User
Join Date
Dec 2005
Location
New Jersey
Posts
290
Sorry, I don't understand what you are trying to do...

Take a look at this code... see if it helps:
Code:
```
public void printFactors(int n) {
for (int i = 1; i < n / 2; i++) {
if (n % i == 0) {
System.out.println(i + " * " + (n / i));
}
}
}```
Now, to print the prime factors, we only need to make a slight adjustment to our code:
Code:
```
public void printPrimeFactors(int n) {
for (int i = 1; i < n / 2; i++) {
if (n % i == 0 && isPrime(i)) {
System.out.println(i + " * " + (n / i));
}
}
}

public boolean isPrime(int n) {
// prime logic here
return true;
}```
Last edited by destin; 03-05-2006 at 08:57 PM.

4. Registered User
Join Date
Jan 2006
Posts
6
this is what my algorithm looks like.

step n k comment
------------------------------------------------
0 999999 2 not divisible by 2, k = k + 1
1 999999 3 n is divisible by 3, n = n / 3, print 3
2 333333 3 n is divisible by 3, n = n / 3, print 3
3 111111 3 n is divisible by 3, n = n / 3, print 3
4 37037 3 not divisible by 3, k = k + 1
5 37037 4 not divisible by 4, k = k + 1
6 37037 5 not divisible by 5, k = k + 1
7 37037 6 not divisible by 6, k = k + 1
8 37037 7 n is divisible by 7, n = n / 7, print 7
9 5291 7 not divisible by 7, k = k + 1
10 5291 8 not divisible by 8, k = k + 1
11 5291 9 not divisible by 9, k = k + 1
12 5291 10 not divisible by 10, k = k + 1
13 5291 11 n is divisible by 11, n = n / 11, print 11
14 481 11 not divisible by 11, k = k + 1
15 481 12 not divisible by 12, k = k + 1
16 481 13 n is divisible by 13, n = n / 13, print 13
17 37 13 STOP since 13^2 > 37 print 37

5. Registered User
Join Date
Jan 2006
Posts
6
so to sum up - I need to print all the prime factors of 999999 using this type of algorith. I know I need a for statement to increment the k value (1-37) but after that I'm a bit lost. Hopefully you are not

6. Registered User
Join Date
Dec 2005
Location
New Jersey
Posts
290
Hmm...

Well, first thing that comes to mind to me is a recursive algorithm.
Code:
```
factor(999999)
/             \
/        \
/    \
.... etc```

7. Registered User
Join Date
Feb 2006
Location
Minnesota
Posts
33
Well, just for starters, you have two BIG problems:

[1] Your curly braces {} don't match up.

[2] You're manipulating your loop counter "i" within the range of the for-loop.

Whether the logic you're using to solve the math problem is correct is another issue entirely.

8. Registered User
Join Date
Dec 2005
Location
New Jersey
Posts
290
Anyway, here's how to tackle my recursive algorithm.
Code:
```
private ArrayList<Integer> factors = new ArrayList<Integer>();

for (int i = 2; i < n / 2; i++) {
if (n % i == 0 && isPrime(i)) {
return;
}
}
}```
This should work -- there is one problem I left for you to fix: it will not add the last prime factor (in this case, 37). Anyway, see if this makes sense to you, if not, take a different approach.

9. Registered User
Join Date
Jan 2006
Posts
6
we haven't learned arrays yet

10. Registered User
Join Date
Jan 2006
Posts
6
i still am having problems with the prime logic - i cant seem to get the factor that i got from the main method to get to the isPrime method...?

11. Registered User
Join Date
Jul 2005
Location
the Netherlands
Posts
128
Originally Posted by xirix
i still am having problems with the prime logic - i cant seem to get the factor that i got from the main method to get to the isPrime method...?
You don't need an isPrime(...) method. Here's an example:
Code:
```public class Test {

public Test(int n) {
while(n > 1) {
for(int i = 2; i <= n; i++) {
if(n%i == 0) {
n = n/i;
System.out.println((n*i)+" = "+i+" * "+n);
break;
}
}
}
System.out.println("done!");
}

public static void main(String[] args) {
new Test(999999);
}
}```

12. Registered User
Join Date
Dec 2005
Location
New Jersey
Posts
290
Originally Posted by prometheuzz
You don't need an isPrime(...) method. Here's an example:
Code:
```public class Test {

public Test(int n) {
while(n > 1) {
for(int i = 2; i <= n; i++) {
if(n%i == 0) {
n = n/i;
System.out.println((n*i)+" = "+i+" * "+n);
break;
}
}
}
System.out.println("done!");
}

public static void main(String[] args) {
new Test(999999);
}
}```
Yeah, this was my first approach... I thought the other way might be easier to understand. Anyway, this was what I did:
Code:
```
public void printPrimeFactors(int n) {
for (int i = 2; i <= n; i++) {
if (n % i == 0) {
System.out.println(i);
n /= i;
i = 2;
}
}
}```
Which is really the same thing as yours

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise