[BOJ][C#] 2023 신기한 소수

LimJaeJun·2024년 1월 1일

algorithm boj

PS/BOJ

목록 보기

83/108

📕 문제

📌 링크

📗 접근 방식

재귀 함수로 소수 찾기:

주어진 소수 중 하나를 첫 번째 자리에 놓고, 나머지 자리를 채우기 위해 재귀 함수를 사용한다.
첫 번째 자리에 소수를 놓고, 나머지 자리를 홀수로 채워가면서 소수인지 확인한다.
소수일 경우 다음 자리로 넘어가며 재귀적으로 진행한다.

결과 출력:

모든 자리에 대해 소수를 찾은 결과를 출력한다.

📘 코드

using System.Text;

namespace BOJ
{    
    class No_2023
    {
        static void Main()
        {
            StringBuilder sb = new StringBuilder();
            int n = int.Parse(Console.ReadLine());
            int[] prime = { 2, 3, 5, 7 };
            for (int i = 0; i < 4; i++)
            {
                Recursive(prime[i], n - 1, sb);
            }

            Console.Write(sb);
        }

        static void Recursive(int first, int n, StringBuilder sb)
        {
            if (n == 0)
            {
                sb.AppendLine($"{first}");
            }

            for (int i = 1; i < 10; i += 2)
            {
                int temp = first * 10 + i;
                if (IsPrime(temp))
                {
                    Recursive(temp, n - 1, sb);
                }
            }
        }

        static bool IsPrime(int num)
        {
            if (num < 2)
            {
                return false;
            }

            for (int i = 2; i * i <= num; i++)
            {
                if (num % i == 0)
                {
                    return false;
                }
            }

            return true;
        }
    }
}