How To Uncovering Prime Number Factors Of Integer Numbers Inwards Coffee - Factorization Algorithm

One of the mutual homework/tasks inwards programming courses is most Prime Factorization. You are asked to write a programme to find prime factors of given integer number. The prime factors of a let out are all of the prime numbers that volition just split upwards the given number. For example, prime factors of 35 are seven as well as 5, both are prime inwards itself as well as just divides 35. Last fourth dimension I did this exercise when I was inwards college, as well as it was something like, writing a programme that asks the user for an integer input as well as and thus displays that number's prime factorization on the command line.   There are variants of this programme equally good e.g. appear at this exercise, Write a programme that prompts the user to come inwards a positive integer as well as displays all its smallest factors inwards decreasing order. It's to a greater extent than or less same equally the before mentioned version of prime factorization problem, but amongst a select grip of of displaying them inwards decreasing order.

Displaying is non a work at all, you lot tin display it inwards command prompt or a GUI easily, the top dog affair is to write logic to uncovering prime factors, as well as this is what you lot volition larn inwards this programming tutorial.

Remember, nosotros tin non utilisation an API method, which conduct solves the work e.g. you lot are non allowed to utilisation contrary method of StringBuffer, inwards companionship to contrary a String inwards Java. You demand to write the heart as well as someone logic of prime factorization past times using primitive programming constructs e.g. command statements, loops, arithmetics operator etc. Though you lot tin utilisation essential run e.g. length() to calculate the length of String or toArray() to convert String to array etc.

Java Program to Find Prime Factors

Without delaying whatsoever farther hither is our consummate Java programme to uncovering prime factors. Logic of calculating prime factors are written within method primeFactors(long number), it's a uncomplicated brute-force logic to uncovering prime factors.

We start from 2, because that's the outset prime let out as well as every let out is likewise divisible past times 1, as well as thus nosotros iterate until nosotros uncovering a prime gene past times incrementing as well as stepping ane at a time. When nosotros uncovering a prime factor, nosotros shop it within a Set as well as likewise trim the let out till which nosotros are looping.

In companionship to run this program, you lot tin merely re-create glue it inwards a file PrimeFactors.java as well as and thus compile as well as run past times using javac and java command. If you lot uncovering whatsoever difficulty running this program, you lot tin likewise refer this article for measuring past times measuring guide on how to run a Java programme from command prompt.

import java.util.HashSet; import java.util.Random; import java.util.Scanner; import java.util.Set;  /** * Java programme to impress prime factors of a number. For illustration if input is 15, * as well as thus it should impress iii as well as 5, similarly if input is 30, as well as thus it should * display 2, iii as well as 5. * * @author Javin Paul */ public class PrimeFactors{      public static void main(String args[]) {          System.out.printf("Prime factors of let out '%d' are : %s %n", 35, primeFactors(35));         System.out.printf("Prime factors of integer '%d' are : %s %n", 72, primeFactors(72));         System.out.printf("Prime factors of positive let out '%d' is : %s %n", 189, primeFactors(189));         System.out.printf("Prime factors of let out '%d' are equally follows : %s %n", 232321, primeFactors(232321));         System.out.printf("Prime factors of let out '%d' are equally follows : %s %n", 67232321, primeFactors(67232321));      }      /**      * @return prime factors of a positive integer inwards Java.      * @input xl      * @output 2, 5      */     public static Set<Integer> primeFactors(long number) {         Set<Integer> primefactors = new HashSet<>();         long copyOfInput = number;          for (int i = 2; i &lt;= copyOfInput; i++) {             if (copyOfInput % i == 0) {                 primefactors.add(i); // prime factor                 copyOfInput /= i;                 i--;             }         }         return primefactors;     }  }  Output: Prime factors of let out '35' are : [5, 7] Prime factors of integer '72' are : [2, 3] Prime factors of positive let out '189' is : [3, 7] Prime factors of let out '232321' are equally follows : [4943, 47] Prime factors of let out '67232321' are equally follows : [12343, 419, 13] 

If you lot are curious most what is that angle bracket <>, its diamond operator introduced inwards Java seven for ameliorate type inference. Now you lot don't demand to write type parameters inwards both side of expression, equally you lot receive got to do inwards Java 1.6, this makes them to a greater extent than readable. Now coming dorsum to exercise, if you lot appear at the output, it solely returns the unique prime factors because nosotros are using Set interface, which doesn't allow duplicates.


If your Interviewer inquire you lot to write programme to split upwards a let out into its prime factors, as well as impress all of them, as well as thus you lot demand to utilisation List interface instead of Set. For example, unique prime factors of '72' are [2,3] but the let out inwards damage of its prime gene is [2, 2, 2, 3, 3]. If you lot demand that variety of output, you lot tin rewrite our primeFactors(long number) method to provide a List<Integer>, equally shown below :

public static List<Integer> primeFactors(long number) {         List<Integer> primefactors = new ArrayList<>();         long copyOfInput = number;          for (int i = 2; i <= copyOfInput; i++) {             if (copyOfInput % i == 0) {                 primefactors.add(i); // prime factor                 copyOfInput /= i;                 i--;             }         }                  return primefactors;     }

and, hither is the output of running same programme amongst this version of primeFactors(long number) method. This fourth dimension you lot tin encounter all the prime factors instead of just the unique ones. This likewise explains difference betwixt Set as well as List interface, a really of import lesson for beginners.

Prime factors of let out '35' are : [5, 7]  Prime factors of integer '72' are : [2, 2, 2, 3, 3]  Prime factors of positive let out '189' is : [3, 3, 3, 7]  Prime factors of let out '232321' are equally follows : [47, 4943]  Prime factors of let out '67232321' are equally follows : [13, 419, 12343]

Now, its fourth dimension to practise writing about JUnit tests. Actually at that topographic point are 2 ways to seek out your code, ane is past times writing top dog method, calling method as well as comparison actual output to expected output past times yourself. Other, much to a greater extent than advanced as well as preferred approach is to utilisation unit of measurement seek out framework similar JUnit to do that.


If you lot follow seek out driven development, than you lot tin fifty-fifty write seek out before writing code as well as allow seek out drive your pattern as well as coding. Let's encounter how our programme fares amongst about JUnit testing.

import static org.junit.Assert.*; import java.util.ArrayList; import java.util.List; import org.junit.Test;   public class PrimeFactorTest {      private List<Integer> list(int... factors){         List&lt;Integer&gt; listOfFactors = new ArrayList<>();                  for(int i : factors){             listOfFactors.add(i);         }                return listOfFactors;     }          @Test     public void testOne() {         assertEquals(list(), PrimeFactors.primeFactors(1));     }          @Test     public void testTwo() {         assertEquals(list(2), PrimeFactors.primeFactors(2));     }      @Test     public void testThree() {         assertEquals(list(3), PrimeFactors.primeFactors(3));     }          @Test     public void testFour() {         assertEquals(list(2,2), PrimeFactors.primeFactors(4));     }          @Test     public void testSeventyTwo() {         assertEquals(list(2,2,2,3,3), PrimeFactors.primeFactors(72));     } }

In our seek out class, PrimeFactorsTest we receive got 5 seek out cases to seek out corner cases, unmarried prime gene cases, as well as multiple prime gene cases. We receive got likewise created a utility method list(int... ints) which accept wages of Java 5 varargs to provide List of given numbers. You tin telephone band this method amongst whatsoever let out of arguments including zero, inwards which instance it volition provide an empty List. If you lot like, you lot tin extend our seek out degree to add together few to a greater extent than tests e.g. functioning test, or about particular instance tests to seek out our prime factorization algorithm.

hither is the output of our JUnit tests, if your new, you lot tin likewise encounter this tutorial to larn how to create as well as run JUnit test.

That's all most how to uncovering prime factors of an Integer let out inwards Java. If you lot demand to a greater extent than practice, you lot tin likewise banking concern tally out next twenty programming exercises, ranging from diverse topics e.g. LinkdList, String, Array, Logic, as well as Concurrency.

1. How to Swap Two Numbers without using Temp Variable inwards Java? (Trick)
2. How to banking concern tally if LinkedList contains loop inwards Java? (Solution)
3. Write a Program to Check if a let out is Power of Two or not? (Answer)
4. How to uncovering middle chemical constituent of LinkedList inwards ane pass? (See here for Solution)
5. How to banking concern tally if a let out is Prime or not? (Solution)
6. Write a Program to uncovering Fibonacci Series of a Given Number? (Solution)
7. How to banking concern tally if a let out is Armstrong let out or not? (Solution)
8. Write a Program to forestall Deadlock inwards Java? (Click here for solution)
9. Write a Program to solve Producer Consumer Problem inwards Java. (Solution)
10. How to contrary String inwards Java without using API methods? (Solution)
11. Write a Program to calculate factorial using recursion inwards Java? (Click here for solution)
12. How to banking concern tally if a let out is Palindrome or not? (Solution)
13. How to banking concern tally if Array contains duplicate let out or not? (Solution)
14. How to take duplicates from ArrayList inwards Java? (Solution)
15. Write a Java Program to See if 2 String are Anagram of each other? (Solution)
16. How to count occurrences of  a grapheme inwards String? (Solution)
17. How to uncovering outset non repeated characters from String inwards Java? (See here for solution)
18. Write a Program to banking concern tally if a let out is binary inwards Java? (Solution)
19. How to take duplicates from array without using Collection API? (Solution)
20. Write a Program to calculate Sum of Digits of a let out inwards Java? (Solution)


Further Learning
The Coding Interview Bootcamp: Algorithms + Data Structures
Data Structures as well as Algorithms: Deep Dive Using Java
Algorithms as well as Data Structures - Part 1 as well as 2

Share this post