시리즈 톺아보기

프로그래머스

소수 찾기

문제 설명
제한 사항
입출력 예

입출력 예 설명

풀이
코드

소수 찾기 🔗

랭크	사용 언어
Level 1

🔗 소수 찾기

문제 설명 🔗

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

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

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

제한 사항 🔗

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

입출력 예 🔗

n	result
10	4
5	3

입출력 예 설명 🔗

입출력 예 #1

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

입출력 예 #2

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

풀이 🔗

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

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

JAVA

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

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

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

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

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

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

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

코드 🔗

JAVA

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

📆 작성일

2021-12-17 Fri 09:44:27

📚 카테고리

알고리즘

🏷️ 태그

프로그래머스

알고리즘

JAVA(자바)

Level 1

[프로그래머스 / JAVA] Level 1 서울에서 김서방 찾기 (12919)

[프로그래머스 / JAVA] Level 1 수박수박수박수박수박수? (12922)

𝝅번째 알파카의 개발 낙서장

[프로그래머스 / JAVA] Level 1 소수 찾기 (12921)

posts

알고리즘

시리즈 톺아보기

Table of Contents

소수 찾기 🔗

문제 설명 🔗

제한 사항 🔗

입출력 예 🔗

입출력 예 설명 🔗

풀이 🔗

코드 🔗

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

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