factorizing numbers

[server_crash]

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

[EvilObsidian]

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

[DeepZ]

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.

[server_crash]

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

[DeepZ]

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

[server_crash]

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.

[kellyshl]

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

[ajst]

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)

[jon.kiparsky]

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.

[ajst]

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

[Saptarshi Patra]

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

[Taywin]

@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

[Momerath]

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