CODEWITHSUNDEEP
javaprime-factoring
Daniel Horowitz
Daniel Horowitz

Reputation: 33

Prime Factorization in Java

I'm working on a prime factorization program in Java one that displays all prime factors of a number even if they are repeated. And I have this:

public static void factors(int a)
{
    int c=1;
    for(int i = 1; i <= a;i++)
    {
        if(a%i == 0)
        {
            for(int k = 2; k < i; k++)
            {
                if(i%k == 0)
                {
                    c = 1;
                    break;
                }
                else
                {
                    c = 0;
                }
            }
            if(c == 0 || i == 2)
            {
                System.out.print(i+ ", ");
            }
        }
    }
}

I need to account for repeated factors (as in 2, 2, 2 for 8). How could I do that without completely restructuring?

Upvotes: 0

Views: 2155

Answers (3)

amit
amit

Reputation: 178531

(1) if(c == 0 || i == 2) is wrong, it will print 2 for a == 5 as well.

(2) In order to do what you are asking without changing the code (*) - you should count how many times each prime factor is diviseable by the number. It can be done by simply adding a new loop before your print statement [pseudo code]:

boolean b = true;
int k = 1;
while (b) { 
  if (a % (int) Math.pow(i, k+1) == 0) k++;
  else b = false;
}

at the end of this loop, k denotes how many times i is a prime factor of a.

(*) Note: Though this approach should work, I'd still go with @KerrekSB suggestion to a redesign.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727107

I think you should start over, and build an algorithm from this simple description:

  • Prepare a List<Integer> of prime numbers that are less than or equal to 2^16
  • Run through this list from low to high, trying each prime in turn as a candidate divisor
  • Every time you run into a working divisor, continually divide it out until you can no longer divide the number by it; then continue to the next prime
  • Once you reach the end of the list of primes, your remaining number should be printed as well, unless it is equal to 1.

Finding a list of primes is a fun problem in itself. Dijkstra wrote a fascinating chapter on it back in 1972. This article has a C++ implementation and a very nice discussion.

Upvotes: 1

tsatiz
tsatiz

Reputation: 1121

You can have another collection that maintains the factors and their count and can finally account for repeated factors. A map with counts would be my choice.

Upvotes: 0

Related Questions