소수 찾기

---

🔗 🔗 소수 찾기

문제 설명

---

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.

(1은 소수가 아닙니다.)

제한 사항

---

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

---

입출력 예 설명

---

입출력 예 #1

1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2

1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

풀이

---

1과 n 사이의 숫자들 중 소수인 수의 갯수를 요구하는 알고리즘

소수 판별 알고리즘을 설계하여, 해당 수가 소수일 경우 하나씩 카운팅하면 될 것이다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
private boolean isPrime(int n)
{
	for (int i = 2; i * i <= n; i++)
	{
		// 나눠 떨어질 경우
		if (n % i == 0)
		{
			return false;
		}
	}
	
	return true;
}

소수 판별 알고리즘은 위와 같다. 2부터 입력된 수 n의 제곱근까지 돌며 값을 나눠본다. 하나라도 나눠질 경우 소수가 아니므로 false를 반환한다.

만약 모든 반복문을 수행했음에도 나눠지지 않는다면 그 수는 소수이다.

$\sqrt{n}$까지만 반복문을 수행하는 이유는 소수의 특성 때문이다. n이 소수일 경우, 1과 n 자기 자신만을 갖는다. 즉, 이외의 약수를 가질 경우 소수가 아니다.

12 -> [ 1, 2, 3, 4, 6, 12 ]일 때, $\sqrt{12}$는 약 3이다. 3까지만 돌며 나누어 떨어지는 수를 구하면, 나머지 반쪽은 12로 나누어 그 값을 알 수 있다.

만약 약수 3을 구했다면, 12 / 3 = 4를 통해, 약수 4를 구할 수 있다.

이 문제는 약수의 갯수에 상관없이 소수인지만 판별하면 되므로, 1과 n 이외의 약수가 하나라도 확인되면 소수가 아니라고 판단하여 알고리즘을 구성하면 된다.

코드

---

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * 소수 찾기 클래스
 *
 * @author RWB
 * @since 2021.12.13 Mon 15:51:37
 */
class Solution
{
	/**
	 * 해답 반환 메서드
	 *
	 * @param n: [int] 자연수
	 *
	 * @return [int] 해답
	 */
	public int solution(int n)
	{
		int answer = 0;
		
		for (int i = 2; i <= n; i++)
		{
			answer += isPrime(i) ? 1 : 0;
		}
		
		return answer;
	}
	
	/**
	 * 소수 여부 반환 메서드
	 *
	 * @param n: [int] 숫자
	 *
	 * @return [boolean] 소수 여부
	 */
	private boolean isPrime(int n)
	{
		for (int i = 2; i * i <= n; i++)
		{
			// 나눠 떨어질 경우
			if (n % i == 0)
			{
				return false;
			}
		}
		
		return true;
	}
}