C# 소수(Prime Number) 찾기

학교에 다닐때 C로 많이 짜봤던 코드일것입니다. 소수 찾기

혹시 소수가 무엇인지 모르는 분을위해 잠시 설명을 드리면 어떤 정수의 숫자 중에서 1과 자기 자신으로만 나누어 지는 수를 소수라고 합니다. 2, 3, 5 같은 경우가 자기 자신과 1 로만 나누어지지요. 4를 보시면 1,2,4 로 나누어 집니다. 1과 자기 자신 말고도 나누어 지는 숫자가 있다는 것이죠.

소수에 대해서 알아보았으니 소수를 찾는 프로그램을 한번 만들어 보도록하겠습니다. 

using System;

 

namespace PrimeNumberTest

{

    class Program

    {

        static void Main(string[] args)

        {

            bool flag = true;

            for (int i = 2; i <= 100; i++)

            {

                for (int j = 2; j < i; j++)

                {

                    if (i % j == 0)

                    {

                        flag = false;

                    }

                }

                if (flag == true)

                {

                    Console.Write("{0} ", i);

                }

                flag = true;

            }

            Console.WriteLine();

        }

    }

}

다음과 같이 입력을 하면 나름 깔끔한 2~100까지의 소수 찾기 프로그램이 나오게 됩니다.

뭐 위의 소스대로 진행을 하여도 크게 문제는 되지 않을꺼라 생각이듭니다. 하지만 이번에 C# in Depth 책을 보다가 소수를 찾는 소스가 보였습니다. 위의 소스는 우선 C,C++,java 등 모든 소스에서 쉽게 사용할 수 있는 코드이긴 하지만 C#을 한다면 뭔가 더 좋은 코드를 써보아야 되지 않을까요?

그래서 준비한 코드가 이것입니다. 에라토스테네스의 체 라는 소수구하는 방법을 이용한 것이죠. 문법적으로는 제네릭과 델레게이트를 사용하여 첨 접하는 분들에게는 다소 어려울지도 모르겠네요. 하지만 언젠가는 정복해야 되는 것이므로.....

using System;

using System.Collections.Generic;

 

namespace PrimeNumberTest

{

    class Program

    {

        static void Main(string[] args)

        {

            List<int> list = new List<int>();

            for (int i = 2; i <= 100; i++)

            {

                list.Add(i);

            }

            for (int factor = 2; factor <= 100; factor++)

            {

                list.RemoveAll(delegate(int x) { return x > factor && x % factor == 0; });

            }

            list.ForEach(delegate(int prime) { Console.Write("{0} ", prime); });

            Console.WriteLine();

        }

    }

}

List<int> 에 2부터 100까지의 수를 입력해 놓고 거기서 에라토스테네스의 체 방법을 사용해서 소수가 아닌 수들을 RemoveAll로 제외시키고 있습니다. 그리고 ForEach 함수를 사용해서 소수만 출력하는 것이지요. 물론 결과는 위 코드와 마찮가지입니다. 어떻게 보면 첫번째 코드가 더 편할 수 있으나 만약 배열이나 리스트에 저장해서 사용해야 되는 값이라면 확실히 두번째 코드가 더 쉽게 구현할 수 있을 것입니다. 물론 선수학습(제네릭, 델레게이트)가 되어 있어야겠지요. ^^