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

One of the mutual homework/tasks inwards programming courses is well-nigh Prime Factorization. You are asked to write a plan to find prime factors of given integer number. The prime factors of a release are all of the prime numbers that volition precisely dissever the given number. For example, prime factors of 35 are seven as well as 5, both are prime inwards itself as well as precisely divides 35. Last fourth dimension I did this exercise when I was inwards college, as well as it was something like, writing a plan that asks the user for an integer input as well as and hence displays that number's prime factorization on the command line.   There are variants of this plan equally good e.g. appear at this exercise, Write a plan that prompts the user to live on 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 grab of displaying them inwards decreasing order.

Displaying is non a occupation at all, y'all tin give notice display it inwards command prompt or a GUI easily, the primary matter is to write logic to notice prime factors, as well as this is what y'all volition larn inwards this programming tutorial.

Remember, nosotros tin give notice non purpose an API method, which straight solves the occupation e.g. y'all are non allowed to purpose contrary method of StringBuffer, inwards corporation to contrary a String inwards Java. You demand to write the meat logic of prime factorization past times using primitive programming constructs e.g. command statements, loops, arithmetics operator etc. Though y'all tin give notice purpose essential component 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 whatever farther hither is our consummate Java plan to notice prime factors. Logic of calculating prime factors are written within method primeFactors(long number), it's a uncomplicated brute-force logic to notice prime factors.

We start from 2, because that's the start prime release as well as every release is equally good divisible past times 1, as well as hence nosotros iterate until nosotros notice a prime gene past times incrementing as well as stepping 1 at a time. When nosotros notice a prime factor, nosotros shop it within a Set as well as equally good trim the release till which nosotros are looping.

In corporation to run this program, y'all tin give notice just re-create glue it inwards a file PrimeFactors.java as well as and hence compile as well as run past times using javac and java command. If y'all notice whatever difficulty running this program, y'all tin give notice equally good refer this article for measuring past times measuring guide on how to run a Java plan from command prompt.

import java.util.HashSet; import java.util.Random; import java.util.Scanner; import java.util.Set;  /** * Java plan to impress prime factors of a number. For illustration if input is 15, * as well as hence it should impress three as well as 5, similarly if input is 30, as well as hence it should * display 2, three as well as 5. * * @author Javin Paul */ public class PrimeFactors{      public static void main(String args[]) {          System.out.printf("Prime factors of release '%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 release '%d' is : %s %n", 189, primeFactors(189));         System.out.printf("Prime factors of release '%d' are equally follows : %s %n", 232321, primeFactors(232321));         System.out.printf("Prime factors of release '%d' are equally follows : %s %n", 67232321, primeFactors(67232321));      }      /**      * @return prime factors of a positive integer inwards Java.      * @input forty      * @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 release '35' are : [5, 7] Prime factors of integer '72' are : [2, 3] Prime factors of positive release '189' is : [3, 7] Prime factors of release '232321' are equally follows : [4943, 47] Prime factors of release '67232321' are equally follows : [12343, 419, 13] 

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


If your Interviewer inquire y'all to write plan to dissever a release into its prime factors, as well as impress all of them, as well as hence y'all demand to purpose List interface instead of Set. For example, unique prime factors of '72' are [2,3] but the release inwards price of its prime gene is [2, 2, 2, 3, 3]. If y'all demand that form of output, y'all tin give notice rewrite our primeFactors(long number) method to furnish 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 plan amongst this version of primeFactors(long number) method. This fourth dimension y'all tin give notice run across all the prime factors instead of just the unique ones. This equally good explains difference betwixt Set as well as List interface, a really of import lesson for beginners.

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

Now, its fourth dimension to exercise writing to a greater extent than or less JUnit tests. Actually at that topographic point are ii ways to attempt your code, 1 is past times writing primary 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 purpose unit of measurement attempt framework similar JUnit to do that.


If y'all follow attempt driven development, than y'all tin give notice fifty-fifty write attempt before writing code as well as allow attempt drive your pattern as well as coding. Let's run across how our plan fares amongst to a greater extent than or less 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 attempt class, PrimeFactorsTest we lead maintain v attempt cases to attempt corner cases, unmarried prime gene cases, as well as multiple prime gene cases. We lead maintain equally good created a utility method list(int... ints) which accept wages of Java 5 varargs to furnish List of given numbers. You tin give notice telephone telephone this method amongst whatever release of arguments including zero, inwards which instance it volition furnish an empty List. If y'all like, y'all tin give notice extend our attempt course of education to add together few to a greater extent than tests e.g. functioning test, or to a greater extent than or less exceptional instance tests to attempt our prime factorization algorithm.

hither is the output of our JUnit tests, if your new, y'all tin give notice equally good run across this tutorial to larn how to create as well as run JUnit test.

That's all well-nigh how to notice prime factors of an Integer release inwards Java. If y'all demand to a greater extent than practice, y'all tin give notice equally good banking concern agree out next xx 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 agree if LinkedList contains loop inwards Java? (Solution)
3. Write a Program to Check if a release is Power of Two or not? (Answer)
4. How to notice middle chemical ingredient of LinkedList inwards 1 pass? (See here for Solution)
5. How to banking concern agree if a release is Prime or not? (Solution)
6. Write a Program to notice Fibonacci Series of a Given Number? (Solution)
7. How to banking concern agree if a release is Armstrong release 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 agree if a release is Palindrome or not? (Solution)
13. How to banking concern agree if Array contains duplicate release or not? (Solution)
14. How to withdraw duplicates from ArrayList inwards Java? (Solution)
15. Write a Java Program to See if ii String are Anagram of each other? (Solution)
16. How to count occurrences of  a graphic symbol inwards String? (Solution)
17. How to notice start non repeated characters from String inwards Java? (See here for solution)
18. Write a Program to banking concern agree if a release is binary inwards Java? (Solution)
19. How to withdraw duplicates from array without using Collection API? (Solution)
20. Write a Program to calculate Sum of Digits of a release 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

Sumber https://javarevisited.blogspot.com/

Share this post