1,105,585 Community Members

factorizing numbers

Member Avatar
server_crash
Postaholic
2,106 posts since Jun 2004
Reputation Points: 64 [?]
Q&As Helped to Solve: 29 [?]
Skill Endorsements: 28 [?]
 
0
 

I made this simple program that prints out all the factors of a given number. The only problem is that it prints out the numbers in different order...For example:

factors of 12:

1*12
2*6
3*4

but this is what my program prints out:

1*12
2*6
3*4
4*3
6*2
12*1


It's taking the numbers and just switching the order, and I was wondering if anyone knew how I could get rid of that.

import java.io.*;
import java.util.*;

public class Factorizer
{
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		System.out.print("Number to factor --> ");
		int limit = Integer.parseInt(br.readLine());
		System.out.println("\n\n<-- Factors --> ");
		ArrayList firstOperand = new ArrayList();
		ArrayList secondOperand = new ArrayList();
		
		for (int i=1; i<=limit; i++)
		{
			for (int j=limit; j>=1; j--)
			{
				if (j *i == limit)
				{
					System.out.println(i+ " * " + j);
				}
			}
		}
	}
}
Member Avatar
EvilObsidian
Newbie Poster
4 posts since Apr 2005
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

I'm a newby, myself, but hopefully this helps:
Store all the factors you get in an array, then each time it finds another factor, have it loop through the array and check to see if the integer is already stored.

EvilObsidian

Member Avatar
DeepZ
Light Poster
27 posts since Sep 2004
Reputation Points: 3 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

What you would need to do (from the top of my head) is to see if the lefthand factor (i in your example) matches the previous righthand factor (j in your ex.).

As soon as i matches the j, we are finding the mirrors of the previously found factors and can stop.

You could use a break from the loops when j == i. (Not print this result as it is already a duplicate).

Have fun.

Member Avatar
server_crash
Postaholic
2,106 posts since Jun 2004
Reputation Points: 64 [?]
Q&As Helped to Solve: 29 [?]
Skill Endorsements: 28 [?]
 
0
 

What you would need to do (from the top of my head) is to see if the lefthand factor (i in your example) matches the previous righthand factor (j in your ex.).

As soon as i matches the j, we are finding the mirrors of the previously found factors and can stop.

You could use a break from the loops when j == i. (Not print this result as it is already a duplicate).

Have fun.

I tried that but I was having problems. Here is what I came up with: I stored the numbers in an ArrayList since I wouldn't know the exact size at runtime, and when printing them out, I only printed out the first half of the numbers. It works, but it's a HUGE waste.

import java.io.*;
import java.util.*;

public class Factorizer
{
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		System.out.print("Number to factor --> ");
		int limit = Integer.parseInt(br.readLine());
		System.out.println("");
		System.out.print("Factors --> ");
		ArrayList firstOperands = new ArrayList();
		ArrayList secondOperands = new ArrayList();

		for (int i=1; i<=limit; i++)
		{
			for (int j=limit; j>=1; j--)
			{
				if (j *i == limit)
				{
					firstOperands.add(i);
					secondOperands.add(j);
				}
			}
		}
		int stop = firstOperands.size()/2;

		for (int i=0; i<stop; i++)
		{
			System.out.println("\n" + firstOperands.get(i) + " * " + secondOperands.get(i));
		}
	}
}
Member Avatar
DeepZ
Light Poster
27 posts since Sep 2004
Reputation Points: 3 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

I was more thinking along these lines : (Quick kludge on the lastFactor > 0 test but ok) :

import java.io.*;
import java.util.*;
public class Factorizer
{
 public static void main(String[] args) throws Exception
 {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  System.out.print("Number to factor --> ");
  int limit = Integer.parseInt(br.readLine());
  System.out.println("\n\n<-- Factors --> ");
//  ArrayList firstOperand = new ArrayList();
//  ArrayList secondOperand = new ArrayList();
  int lastFactor = -1;
  
  for (int i=1; i<=limit; i++)
  {
   if ((lastFactor > 0) && (i >= lastFactor)) {
	break;
   }
   {
   }
   for (int j=limit; j>=1; j--)
   {
	if (j *i == limit)
	{
	 lastFactor = j;
	 System.out.println(i+ " * " + j);
	 break;
	}
   }
  }
 }
}
Member Avatar
server_crash
Postaholic
2,106 posts since Jun 2004
Reputation Points: 64 [?]
Q&As Helped to Solve: 29 [?]
Skill Endorsements: 28 [?]
 
0
 

I was more thinking along these lines : (Quick kludge on the lastFactor > 0 test but ok) :

import java.io.*;
import java.util.*;
public class Factorizer
{
 public static void main(String[] args) throws Exception
 {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  System.out.print("Number to factor --> ");
  int limit = Integer.parseInt(br.readLine());
  System.out.println("\n\n<-- Factors --> ");
//  ArrayList firstOperand = new ArrayList();
//  ArrayList secondOperand = new ArrayList();
  int lastFactor = -1;
  
  for (int i=1; i<=limit; i++)
  {
   if ((lastFactor > 0) && (i >= lastFactor)) {
	break;
   }
   {
   }
   for (int j=limit; j>=1; j--)
   {
	if (j *i == limit)
	{
	 lastFactor = j;
	 System.out.println(i+ " * " + j);
	 break;
	}
   }
  }
 }
}

That's pretty sweet, thanks for the good work and help.

Member Avatar
kellyshl
Newbie Poster
1 post since Dec 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

sorry, i wanted to delete this post. but duno how =x

Member Avatar
ajst
Junior Poster
120 posts since Nov 2010
Reputation Points: 18 [?]
Q&As Helped to Solve: 3 [?]
Skill Endorsements: 0 [?]
 
0
 

what you can do is rather then running the inner loop to the same number as the outer loop get it to stop at half of the outer loop. that way it will not create duplicates or have to waste time comparing if its in list allready

e.g

int limit = 12
for(i < limit)
for(j < limit /2)
Member Avatar
jon.kiparsky
Posting Virtuoso
1,837 posts since Jun 2010
Reputation Points: 326 [?]
Q&As Helped to Solve: 192 [?]
Skill Endorsements: 6 [?]
 
0
 

what you can do is rather then running the inner loop to the same number as the outer loop get it to stop at half of the outer loop. that way it will not create duplicates or have to waste time comparing if its in list allready

Doesn't help much with factoring. 4 < 12/2


Just a thought: once you've found a factor, you can simplify the problem.
Factoring n, if you find that n%f==0 then you know f is a factor of n, and you know that you now need to factor n/f, starting at f.

For example, 132 % 2 = 0, so we keep 2 as a factor and try to factor 66 starting at 2.
66 % 2 = 0, so we take another 2 and factor 33, starting at 2.
33 % 2 = 1 - no more twos. 33 % 3 = 0, so we take a 3 as a factor and try to factor 11,
starting with 3. we try 3, 4, 5, 6 ... okay it's prime, so we're done. (You can run the combinations if you want 66*2, 12*11, 3*44, etc, or you can filter duplicates if you just want to know what divides evenly into n, but once you're down to prime factors you've got what you came for)

At this point you might speed up by setting n/2 as your limit, but of course you're only going to hit that on your last time through, so unless you're trying to factor a lot numbers that involve really heavy primes you'll never see any time difference from that. It'll save you at most half of the traverse of your last loop - not a big deal.

Member Avatar
ajst
Junior Poster
120 posts since Nov 2010
Reputation Points: 18 [?]
Q&As Helped to Solve: 3 [?]
Skill Endorsements: 0 [?]
 
0
 

Saving half of your traverse is a big deal if your looking for the 1000th prime because it will save you half the loops. which is like 0.1sec but as you get bigger it helps.

this is the code i use for finding all the prime factors of a number

for(x < num;)
        {
            if( x % 2 != 0 || x == 2 )
            {
                for( y <= x / 2;)
                {
                    if( x % y == 0 )
                    {
                        break loop
                    }
                }
                if( y > x / 2 )
                {
                    add prime
                }
            }
        }
Member Avatar
Saptarshi Patra
Newbie Poster
1 post since Mar 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 
import java.io.*;
public class Factorizer
{
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		System.out.print("Number to factor --> ");
		int limit = Integer.parseInt(br.readLine());
		System.out.println("\n\n<-- Factors --> ");
 
		for (int i=1; i<=limit; i++)
		{
			for (int j=limit; j>=1; j--)
			{
				if (j *i == limit)
				{
					if(i <= j)
					{
						System.out.println(i+ " * " + j);
					}
				}
			}
		}
	}
}

hope this will serve your purpose

Member Avatar
Taywin
Posting Maven
2,632 posts since Apr 2010
Reputation Points: 134 [?]
Q&As Helped to Solve: 378 [?]
Skill Endorsements: 17 [?]
 
0
 

@ajst
I understand that it could help but it is not worth it. In big O time, it is still the same. If you really want to reduce the computation, why don't you use square root of x? You should have found a factor of a number before the number's square root value. If you go above the value, you are going through the same symmetry already. Using square root will reduce the big O from O(n) to O(logn). Or if it is O(n^2), it will become O(nlogn).

Back to TC, I am still confused what you want here :( Do you want to print out all possible factors or do you want to print out none duplicated factors???

For example...
12
2 * 6
2 * 2 * 3

or...
12
1 * 12
2 * 6
3 * 4

Member Avatar
Momerath
Senior Poster
3,832 posts since Aug 2010
Reputation Points: 1,327 [?]
Q&As Helped to Solve: 664 [?]
Skill Endorsements: 19 [?]
Featured
 
0
 

What you need to remember is that factors come in pairs and that you only need to check up to the square root of the number for factors to get them all (think about it a bit).

So, you need to

Loop i from 1 to Square root of number
    if number mod i (number % i) == 0 then
        i is a factor as is number / i
    end if
end loop
You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article