🔗 Finding Prime Numbers

Write a function, solution, that returns the count of prime numbers between 1 and the given number n.

A prime number is a number that is only divisible by 1 and itself.

(1 is not a prime number.)

• n is a natural number between 2 and 1,000,000, inclusive.

Input/Output Example #1

There are 4 prime numbers between 1 and 10: [2,3,5,7], so it returns 4.

Input/Output Example #2

There are 3 prime numbers between 1 and 5: [2,3,5], so it returns 3.

This is an algorithm that requires the count of prime numbers among the numbers between 1 and n.

We can design a primality test algorithm, and count up whenever a number turns out to be prime.

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

The primality test algorithm is as shown above. It loops from 2 up to the square root of the given number n, dividing the value by each. If it divides evenly for any of them, it's not prime, so false is returned.

If the loop completes without finding any divisor, then the number is prime.

The reason the loop only needs to run up to $\sqrt{n}$ is due to a property of prime numbers. If n is prime, it only has 1 and n itself as divisors — meaning if it has any other divisor, it's not prime.

For 12 -> [ 1, 2, 3, 4, 6, 12 ], $\sqrt{12}$ is about 3. If we loop only up to 3 and find a divisor, we can find the other half of the pair by dividing 12 by it.

For example, if we find the divisor 3, we can find the divisor 4 via 12 / 3 = 4.

Since this problem only requires determining whether a number is prime, regardless of how many divisors it has, we can design the algorithm to conclude that a number is not prime as soon as any divisor other than 1 and n is found.

JAVA
/**
 * Finding Prime Numbers class
 *
 * @author RWB
 * @since 2021.12.13 Mon 15:51:37
 */
class Solution
{
	/**
	 * Method that returns the answer
	 *
	 * @param n: [int] natural number
	 *
	 * @return [int] the answer
	 */
	public int solution(int n)
	{
		int answer = 0;
		
		for (int i = 2; i <= n; i++)
		{
			answer += isPrime(i) ? 1 : 0;
		}
		
		return answer;
	}
	
	/**
	 * Method that returns whether a number is prime
	 *
	 * @param n: [int] number
	 *
	 * @return [boolean] whether it is prime
	 */
	private boolean isPrime(int n)
	{
		for (int i = 2; i * i <= n; i++)
		{
			// If it divides evenly
			if (n % i == 0)
			{
				return false;
			}
		}
		
		return true;
	}
}