CODEWITHSUNDEEP
javaalgorithmmathprimes
ravi
ravi

Reputation: 6328

Counting the occurrence of each number in prime factors of an integer

I want to count the number of each prime factor of an integer. For an example 18=2^1*3^2. I want to get all exponent part of each prime number. For number 18, it is 1+2=3.
Below is the program which generates all the prime factors of an integer.

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    for (int i = 2; i <= n / i; i++) {
        while (n % i == 0) {
            System.out.print(i + ", ");
            n /= i;
        }
    }
    if (n > 1)
        System.out.print(n + ", ");

For input 18, this program prints 2, 3, 3, . As for completing my requirement, to count the occurrence of each prime factor, i can first add them all to a list, then a for loop from starting to ending of the list can count the occurrence of each number. But this idea doesn't seem good to me. Unnecessary i am adding one for loop, for all prime factors, which just tells me that this prime factor comes n times in the list.
Any better approach to get the number of individual number of prime factors of an integer.

Upvotes: 0

Views: 3581

Answers (2)

kritzikratzi
kritzikratzi

Reputation: 20221

yy, just as @attila and @robert said: 

import java.util.Scanner; 
import java.util.TreeMap; 

public class Test{
    public static void main( String args[] ){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        TreeMap<Integer, Integer> factors = new TreeMap<Integer, Integer>(); 

        for (int i = 2; i <= n / i; i++) {
            int count = 0; 

            while (n % i == 0) {
                System.out.print(i + ", ");
                n /= i;
                count ++; 
            }
            if( count > 0 ) 
                factors.put( i, count ); 
        }
        if (n > 1){
            System.out.print(n + ", ");
            factors.put( n, 1 ); 
        }
        System.out.println(); 

        System.out.println( "-------------" ); 
        for( Integer factor : factors.keySet() ){
            System.out.println( factor + "^" + factors.get( factor ) ); 
        }
    }
}

i'm using a treemap because it keeps the factors in their natural order, which is neat :) you could also use a hashmap which should be a bit faster. but the implementation of the prime decomposition should be so slow that i don't think it matters much :)

Upvotes: 1

Attila
Attila

Reputation: 28762

Every time you are executing n/=i;, you are encountering a factor. So by incrementing a counter (Starting from 0) at that point, you get the total number of factors at the end of the factorization process.

Note that you need an extra if for properly handling prime numbers. For primes you do not find any factors, so the counter will be 0 -- you need to set it to 1 after the loop in this case (one factor: itself)

Upvotes: 0

Related Questions