
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++;
}

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.)

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; 03052006 at 08:57 PM.

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

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 (137) but after that I'm a bit lost. Hopefully you are not

Hmm...
Well, first thing that comes to mind to me is a recursive algorithm.
Code:
factor(999999)
/ \
add(3) factor(333333)
/ \
add(3) factor(111111)
/ \
add(3) factor(37037)
.... etc

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 forloop.
Whether the logic you're using to solve the math problem is correct is another issue entirely.

Anyway, here's how to tackle my recursive algorithm.
Code:
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.

we haven't learned arrays yet

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...?

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);
}
}

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
Similar Threads

By Irina in forum ASP.NET
Replies: 0
Last Post: 11292002, 10:47 PM

Replies: 0
Last Post: 12132001, 12:06 PM

By Roseta in forum VB Classic
Replies: 0
Last Post: 11142001, 03:24 AM

By Ayman in forum VB Classic
Replies: 0
Last Post: 04032000, 01:08 AM

By Jason Bock in forum VB Classic
Replies: 0
Last Post: 03212000, 06:48 PM
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Development Centers
 Android Development Center
 Cloud Development Project Center
 HTML5 Development Center
 Windows Mobile Development Center
