[AmateurC]

Can anybody help me with the prime factoring code I just posted? How do I get this Java code to work?

import java.util.Scanner;
class Factors {
  public static void main (String[] args ) {
	Scanner scan = new Scanner( System.in );
	long num, div, quotient, remainder;
	System.out.println("Enter an integer: " );
	num = scan.nextInt();
	div = 2;
	quotient = num / div;
	remainder = num % div;	  
	for (div = 2; div <= num / div; div++)
	{
		 if (num % div == 0)
		 {
			while (remainder == 0)
			{
			  quotient = num / div;
			  remainder = num % div;			  
			  System.out.println ("factor: " + div);
			  num = quotient;
			}
		 }
		 else
		 {
			div = div + 1;
			quotient = num / div;
			remainder = num % div;			  
			System.out.println ("factor: " + div);
		 }
		
   }
  } 
}

** Edit **

[macosxnerd101]

Please respect rules 4 and 6 when posting. They state:

Quote

4. Use BBCode when posting. For example:
6. Describe any errors you are encountering. Help us help you!

This post has been edited by macosxnerd101: 24 October 2009 - 09:28 PM

[macosxnerd101]

If you are looking for factoring in general, a for loop is a good place to start. However, if you are looking for prime factors, then you are going to need to generate primes from 2 to n/2. The Sieve of Eratosthenes is a good place to start for this. I've actually written a snippet on the sieve if you want to check it out: http://www.dreaminco...snippet4245.htm

From there, I would use a Map to store the number of times each prime is a factor of the given number. And since the primes are stored in an ArrayList, you can use the contains(elem) from the list of primes to check to see if the quotient of number/prime is a prime number.

For more information on using a Map, check out the Map interface and HashMap class:
http://java.sun.com/...a/util/Map.html
http://java.sun.com/...il/HashMap.html

[kanshu]

AmateurC, on 24 Oct, 2009 - 08:19 PM, said:

Can anybody help me with the prime factoring code I just posted? How do I get this Java code to work?

First of all, what's the output?

This post has been edited by kanshu: 24 October 2009 - 10:34 PM

[AmateurC]

kanshu, on 24 Oct, 2009 - 09:29 PM, said:

AmateurC, on 24 Oct, 2009 - 08:19 PM, said:

Can anybody help me with the prime factoring code I just posted? How do I get this Java code to work?

First of all, what's the output?

The program must display prime factors of a number. For example, the prime numbers of 12 is 2 * 2 * 3.

This post has been edited by AmateurC: 25 October 2009 - 01:29 AM

[kanshu]

AmateurC, on 25 Oct, 2009 - 12:29 AM, said:

The program must display prime factors of a number. For example, the prime numbers of 12 is 2 * 2 * 3.

I meant, what is the actual output as it is right now? I can only help to fix whatever is wrong with it.

This post has been edited by kanshu: 25 October 2009 - 02:37 AM

[AmateurC]

kanshu, on 25 Oct, 2009 - 01:35 AM, said:

AmateurC, on 25 Oct, 2009 - 12:29 AM, said:

The program must display prime factors of a number. For example, the prime numbers of 12 is 2 * 2 * 3.

I meant, what is the actual output as it is right now? I can only help to fix whatever is wrong with it.

When I input the number 12, the program prints "factor: 2" three times instead of printing "factor: 2" twice and "factor: 3" once. Also, when I tried to input 15, the program would not even execute. Instead, the cursor moves back into the source code area. (I use DrJava.)

[kanshu]

This is my initial analysis. I haven't traced the "else" or odd factor part of your code.

class Factors {
  public static void main (String[] args ) {
	Scanner scan = new Scanner( System.in );
	long num, div, quotient, remainder;
	System.out.println("Enter an integer: " );
	num = scan.nextInt();
	div = 2;
	quotient = num / div;
	remainder = num % div;	  
	for (div = 2; div <= num / div; div++)
	{
		 /* another variable should be used for num 
		 because you're overwriting its contents below */
		 if (num % div == 0)
		 {
			/* i think remainer==0 should use (quotient % div)==0 */
			while (remainder == 0)  
			{
			  quotient = num / div;
			  remainder = num % div;			  
			  System.out.println ("factor: " + div);

			  /* assigning to num will affect your for loop condition */
			  /* i suggest using another variable for num */
			  num = quotient; /* quotient should be used in the while loop condition */
			}
		 }
		 else
		 {
			div = div + 1;
			quotient = num / div;
			remainder = num % div;			  
			System.out.println ("factor: " + div);
		 }
	   
   }
  }
}

This post has been edited by kanshu: 25 October 2009 - 03:47 AM

[pbl]

Isn't that simpler ?

		String times = " ";	// will be " " first time
		System.out.print(num + " =");
		boolean found = true;
		while(found) {
			found = false;
			for(int i = 2; i < num; i++) {
				if(num % i == 0) {
					System.out.print(times + i);
					num /= i;
					times = " * ";   // next one will have " * "
					found = true;
					break;
				}
			}
			// if not found it means last one is prime
			if(!found) {
				System.out.println(times + num);
			}
		}

[sakshamkum]

you can make a function prime(int num) and check for prime numbers and in tne main() function check and print

[kanshu]

sakshamkum, on 25 Oct, 2009 - 11:25 AM, said:

you can make a function prime(int num) and check for prime numbers and in tne main() function check and print

Actually, at first, I thought it would be a simple matter of finding primes or testing for prime numbers. But it turned out that the problem is more about factoring.

So, an input of 32 should yield: 32 = 2 * 2 * 2 * 2 * 2.

This post has been edited by kanshu: 25 October 2009 - 03:29 PM

[kanshu]

pbl, on 25 Oct, 2009 - 11:11 AM, said:

Isn't that simpler ?

		String times = " ";	// will be " " first time
		System.out.print(num + " =");
		boolean found = true;
		while(found) {
			found = false;
			for(int i = 2; i < num; i++) {
				if(num % i == 0) {
					System.out.print(times + i);
					num /= i;
					times = " * ";   // next one will have " * "
					found = true;
					break;
				}
			}
			// if not found it means last one is prime
			if(!found) {
				System.out.println(times + num);
			}
		}

First impression. I think this will work. It just needs to be tweaked a little to handle prime numbers like 11 because it still continues to increment, in this case, from 6 to 11 which is not necessary.

[pbl]

kanshu, on 25 Oct, 2009 - 02:37 PM, said:

First impression. I think this will work. It just needs to be tweaked a little to handle prime numbers like 11 because it still continues to increment, in this case, from 6 to 11 which is not necessary.

LOL !!! I was just polite by writing "Isn't that simpler ?"
This IS simpler and don't see why it would work with 11 ?
And the idea of isPrime() will evaluate a few dozen time if the same number is a prime

[kanshu]

pbl, on 25 Oct, 2009 - 02:59 PM, said:

kanshu, on 25 Oct, 2009 - 02:37 PM, said:

First impression. I think this will work. It just needs to be tweaked a little to handle prime numbers like 11 because it still continues to increment, in this case, from 6 to 11 which is not necessary.

LOL !!! I was just polite by writing "Isn't that simpler ?"
This IS simpler and don't see why it would work with 11 ?

Yup. I agree with you. It is simpler. Actually, my comment was more directed to the original poster if he choose to use your code. My tweak suggestion is for efficiency because for any given number N, it is enough to just analyze factors from 2 to N/2.

This post has been edited by kanshu: 25 October 2009 - 05:09 PM

[pbl]

kanshu, on 25 Oct, 2009 - 04:09 PM, said:

pbl, on 25 Oct, 2009 - 02:59 PM, said:

kanshu, on 25 Oct, 2009 - 02:37 PM, said:

First impression. I think this will work. It just needs to be tweaked a little to handle prime numbers like 11 because it still continues to increment, in this case, from 6 to 11 which is not necessary.

LOL !!! I was just polite by writing "Isn't that simpler ?"
This IS simpler and don't see why it would work with 11 ?

Yup. I agree with you. It is simpler. Actually, my comment was more directed to the original poster if he choose to use your code. My tweak suggestion is for efficiency because for any given number N, it is enough to just analyze factors from 2 to N/2.

I spent 20 years of my life doing Performance Analysis, in the times were 64K of memory cost $ 100,000.00
if you want me to track down all yoiur posts for performance analysis... just ask for it