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 :WAVE:
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++;
}
[714 byte] By [
xirix] at [2007-11-11 8:09:47]
# 1 Re: factoring problem
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.)
# 2 Re: factoring problem
Sorry, I don't understand what you are trying to do...
Take a look at this code... see if it helps:
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:
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;
}
destin at 2007-11-11 22:37:13 >
# 3 Re: factoring problem
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
xirix at 2007-11-11 22:38:17 >
# 4 Re: factoring problem
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 :)
xirix at 2007-11-11 22:39:16 >
# 5 Re: factoring problem
Hmm...
Well, first thing that comes to mind to me is a recursive algorithm.
factor(999999)
/ \
add(3) factor(333333)
/ \
add(3) factor(111111)
/ \
add(3) factor(37037)
... etc
destin at 2007-11-11 22:40:15 >
# 6 Re: factoring problem
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.
# 7 Re: factoring problem
Anyway, here's how to tackle my recursive algorithm.
private ArrayList<Integer> factors = new ArrayList<Integer>();
public void addPrimeFactors(int n) {
for (int i = 2; i < n / 2; i++) {
if (n % i == 0 && isPrime(i)) {
factors.add(i);
addPrimeFactors(n / 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.
destin at 2007-11-11 22:42:17 >
# 8 Re: factoring problem
we haven't learned arrays yet :(
xirix at 2007-11-11 22:43:24 >
# 9 Re: factoring problem
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...?
xirix at 2007-11-11 22:44:22 >
# 10 Re: factoring problem
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:
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);
}
}
# 11 Re: factoring problem
You don't need an isPrime(...) method. Here's an example:
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:
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 :o
destin at 2007-11-11 22:46:31 >
