[C#/COMMON] 오일러의 체(Euler's Sieve)를 사용해 소수 구하기

TestProject.zip

다운로드

▶ MainForm.cs

using System;
using System.Windows.Forms;

namespace TestProject
{
    /// <summary>
    /// 메인 폼
    /// </summary>
    public partial class MainForm : Form
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 생성자 - MainForm()

        /// <summary>
        /// 생성자
        /// </summary>
        public MainForm()
        {
            InitializeComponent();

            #region 이벤트를 설정한다.

            this.findButton.Click += findButton_Click;

            #endregion
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method
        ////////////////////////////////////////////////////////////////////////////////////////// Private
        //////////////////////////////////////////////////////////////////////////////// Event

        #region 찾기 버튼 클릭시 처리하기 - findButton_Click(sender, e)

        /// <summary>
        /// 찾기 버튼 클릭시 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void findButton_Click(object sender, EventArgs e)
        {
            this.primeNumberListBox.Items.Clear();

            this.estimatePrimeNumberCountValueLabel.Text = string.Empty;
            this.actualPrimeNumberCountValueLabel.Text   = string.Empty;

            Cursor = Cursors.WaitCursor;

            Refresh();

            int maximumNumber = int.Parse(this.maximumNumberTextBox.Text);

            bool[] isPrimeNumberArray = GetIsPrimeNumberArray(maximumNumber);

            int primeNumberCount = 0;

            for(int i = 2; i <= maximumNumber; i++)
            {
                if(isPrimeNumberArray[i])
                {
                    if(primeNumberCount <= maximumNumber)
                    {
                        this.primeNumberListBox.Items.Add(i);
                    }

                    primeNumberCount++;
                }
            }

            if(primeNumberCount > maximumNumber)
            {
                this.primeNumberListBox.Items.Add("...");
            }

            this.actualPrimeNumberCountValueLabel.Text = primeNumberCount.ToString();

            double estimatePrimeNumber = (maximumNumber / (Math.Log(maximumNumber) - 1.08366));

            this.estimatePrimeNumberCountValueLabel.Text = estimatePrimeNumber.ToString("0");

            Cursor = Cursors.Default;
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////// Function

        #region 소수 여부 배열 구하기 - GetIsPrimeNumberArray(maximumNumber)

        /// <summary>
        /// 소수 여부 배열 구하기
        /// </summary>
        /// <param name="maximumNumber">최대 번호</param>
        /// <returns>소수 여부 배열</returns>
        private bool[] GetIsPrimeNumberArray(int maximumNumber)
        {
            bool[] isPrimeNumberArray = new bool[maximumNumber + 1];

            isPrimeNumberArray[2] = true;

            for(int i = 3; i <= maximumNumber; i += 2)
            {
                isPrimeNumberArray[i] = true;
            }

            for(int p = 3; p <= maximumNumber; p += 2)
            {
                if(isPrimeNumberArray[p])
                {
                    int maximumQ = maximumNumber / p;

                    if(maximumQ % 2 == 0)
                    {
                        maximumQ--;
                    }

                    for(int q = maximumQ; q >= p; q -= 2)
                    {
                        if(isPrimeNumberArray[q])
                        {
                            isPrimeNumberArray[p * q] = false;
                        }
                    }
                }
            }

            return isPrimeNumberArray;
        }

        #endregion
    }
}