🔗 Making Primes

We want to find the number of cases where adding 3 numbers chosen from the given numbers results in a prime number. Given an array nums containing numbers as a parameter, complete the solution function so that it returns the number of ways to choose 3 distinct numbers from nums whose sum is a prime number.

• The number of elements in nums is between 3 and 50 inclusive.
• Each element of nums is a natural number between 1 and 1,000 inclusive, and contains no duplicate numbers.

Input/Output Example #1

You can make 7 using [1,2,4].

Input/Output Example #2

You can make 7 using [1,2,4].

You can make 11 using [1,4,6].

You can make 13 using [2,4,7].

You can make 17 using [4,6,7].

This is a problem where we pick 3 arbitrary elements from an array and find the number of cases where the sum of those numbers is prime.

1. Pick 3 arbitrary elements
2. Determine whether the sum of the elements is prime

Implementing these two pieces of logic is the core of the algorithm.

Combinations are usually used for this, but let's implement it simply using nested for loops.

JAVA
for (int i = 0; i < nums.length; i++)
{
	for (int j = i + 1; j < nums.length; j++)
	{
		for (int k = j + 1; k < nums.length; k++)
		{
			int sum = nums[i] + nums[j] + nums[k];
		}
	}
}

Arbitrary sets of three elements can be obtained through a triple-nested for loop like this. Pay close attention to the indices of j and k. The initial values are set up so that each index doesn't overlap with the others.

JAVA
private boolean isPrime(int num)
{
	for (int i = 2; i <= Math.sqrt(num); i++)
	{
		// If it divides evenly
		if (num % i == 0)
		{
			return false;
		}
	}
	
	return true;
}

Primality can be determined like this. The reason we only compute up to Math.sqrt(num) is that there's no need to check beyond the square root.

For example, 12 has the divisors 1, 2, 3, 4, 6, 12, and $\sqrt{12}$ is roughly 3. The numbers after 3—4 and 6—each pair up with 2 and 3 to make 12, so if there's no number that divides evenly up to the square root, the number can be considered prime.

JAVA
/**
 * Making Primes class
 *
 * @author RWB
 * @since 2021.12.10 Fri 00:21:09
 */
class Solution
{
	/**
	 * Method that returns the answer
	 *
	 * @param nums: [int[]] The number array
	 *
	 * @return [int] The number of cases resulting in a prime
	 */
	public int solution(int[] nums)
	{
		int answer = 0;
		
		for (int i = 0; i < nums.length; i++)
		{
			for (int j = i + 1; j < nums.length; j++)
			{
				for (int k = j + 1; k < nums.length; k++)
				{
					int sum = nums[i] + nums[j] + nums[k];
					
					answer += isPrime(sum) ? 1 : 0;
				}
			}
		}
		
		return answer;
	}
	
	/**
	 * Method that returns whether the number is prime
	 *
	 * @param num: [int] The number
	 *
	 * @return [boolean] Whether it's prime
	 */
	private boolean isPrime(int num)
	{
		for (int i = 2; i <= Math.sqrt(num); i++)
		{
			// If it divides evenly
			if (num % i == 0)
			{
				return false;
			}
		}
		
		return true;
	}
}