Java Program to Find a List of Prime Numbers (Step by Step)

 


A Prime number is a Number whose only factors are 1 and the Number itself. A good problem to solve using Java code is to find the list of all numbers which are Prime till, let's say 100. 

Now, that's a bit difficult to find by hand, and we can use the crunching power of loops to do this calculation for us easily. 

The problem itself is a bit complicated and we can't solve it in one shot. We have to break it down into steps. Let's list down the steps required:

  1. Find the Factors of a Number
  2. Find if a Number is Prime (Factors should be 1 and Number itself)
  3. Find the list of Prime numbers
Cool! So, as we have seen, we need to perform three operations in order to reach our final output. 
One approach can be to write one really big function to do this calculation. The second, and better approach, is to break it down into separate functions, like we have broken down the problem. That makes the code reusable and showcases to the Interviewer that you have a grasp on different concepts. Our final aim is to crack that interview, right!

Now, we've written a function to find the factors of a number earlier. We'll make use of that function and build upon it to reach our final goal.

Here is the code for your reference:

/**
 * Find all the factors of a Number
 * @author computengine.com
 * @param num
 * @return
 */
public static ArrayList<Integer> findFactors(int num){
	
	ArrayList<Integer> factors = new ArrayList<Integer>();
	
	//check the division of each number from 1 to the number itself
	for(int i=1;i<=num;i++) {
		//if remainder is 0, means the number is a factor
		if(num%i==0)
			factors.add(i);
	}
	
	return factors;
}

Next step is to find if a number is prime. What was the definition again? A number having factors as 1 and the number itself. Good candidate for reuse, right!

/**
 * Find if a number is Prime
 * @author computengine.com
 * @param num
 * @return
 */
public boolean checkNumberPrime(int num) {
	
	boolean isPrime = false;
	
	//1 is by default a prime number
	if(num==1)
		return true;
	
	//get the factors of the number
	ArrayList <Integer> factors = findFactors(num);
	
	//if only 1 and the number itself are the factors, the number is prime.
	if(factors.get(0)==1 && factors.get(1)==num && factors.size()==2)
		isPrime=true;
	
	
	return isPrime;
}

We'll fetch the factors of a number, and then check the factors in a set of conditions to derive that a number is Prime or not.

//if only 1 and the number itself are the factors, the number is prime.
if(factors.get(0)==1 && factors.get(1)==num && factors.size()==2)
	isPrime=true;


Now coming to the last code bit. We need to find a list of numbers between 1 and any given number. 

/**
 * Find the list of all Prime Numbers between a 1 and a Given number
 * @author computengine.com
 * @param maxRange
 * @return
 */
public ArrayList<Integer> listOfPrimeNumbers(int maxRange){
	
	ArrayList<Integer> al = new ArrayList<Integer>();
	
	for(int i=1;i<=maxRange;i++) {
		if(checkNumberPrime(i)) 
			al.add(i);
	}
	return al;
	
}

Now, let's check the output. 

System.out.println("List of Prime Numbers:"+listOfPrimeNumbers(100).toString());

List of Prime Numbers:[1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Cool, right! We've created reusable functions to achieve our goal to find the list of prime numbers. 

Thanks for Reading the Article. If you have reached this far, we hope that the article was useful to you! Please Like/Share/Follow us on FacebookTwitterTumblr.

Comments

Popular posts from this blog

Calculate Your CTC Hike Percentage

Java Program to check Palindrome

What is my IP Address - How to find your IP address on Local Network using Command Prompt, and External Network using JavaScript Code

Reduce Server Load from Dynamic Page Search - Create a Dynamic JavaScript based Table filter