■ 에라토스테네스의 체(Sieve of Eratosthenes)를 사용해 소수 구하기

------------------------------------------------------------------------------------------------------------------------


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 <= 10000)

                    {

                        this.primeNumberListBox.Items.Add(i);

                    }

 

                    primeNumberCount++;

                }

            }

 

            if(primeNumberCount > 10000)

            {

                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 i = 3; i <= maximumNumber; i += 2)

            {

                if(isPrimeNumberArray[i])

                {

                    for(int j = i * 3; j <= maximumNumber; j += i)

                    {

                        isPrimeNumberArray[j] = false;

                    }

                }

            }

 

            return isPrimeNumberArray;

        }

 

        #endregion

    }

}

 

------------------------------------------------------------------------------------------------------------------------

Posted by 사용자 icodebroker
TAG