using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

using System.Diagnostics;

namespace SieveOfEratosthenes
{
    public partial class frm85SieveOfEratosthenes : Form
    {
        public frm85SieveOfEratosthenes()
        {
            InitializeComponent();
        }

        // Make a sieve and display the primes.
        private void btnFindPrimes_Click(object sender, EventArgs e)
        {
            primesTextBox.Clear();
            estPrimesLabel.Text = "";
            actualPrimesLabel.Text = "";
            Cursor = Cursors.WaitCursor;
            Refresh();

            // Make the sieve.
            int max = int.Parse(maxNumberTextBox.Text);
            Stopwatch watch = new Stopwatch();
            watch.Start();
            List<int> primes = FindPrimes(max);
            watch.Stop();
            Console.WriteLine(watch.Elapsed.TotalSeconds.ToString("0.00") + " seconds");

            // Display the primes.
            int imax = Math.Min(primes.Count, 1000);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < imax; i++)
                sb.Append(primes[i].ToString() + "\t");
            if (imax < primes.Count) sb.Append("...");
            primesTextBox.Text = sb.ToString();

            // Display the estimated and actual number of primes.
            actualPrimesLabel.Text = primes.Count.ToString("N0");

            // Display a Legendre estimate Pi(n) = n/(log(n) - 1.08366).
            // See http://mathworld.wolfram.com/PrimeCountingFunction.html.
            double est = (max / (Math.Log(max) - 1.08366));
            estPrimesLabel.Text = est.ToString("N0");

            Cursor = Cursors.Default;
        }

        // Use a sieve of Eratosthenes to find primes.
        private List<int> FindPrimes(int max)
        {
            // Make an array indicating whether numbers are prime.
            // Initially 2 and odd values greater than 1 are true.
            bool[] isPrime = new bool[max + 1];
            isPrime[2] = true;
            for (int i = 3; i <= max; i += 2) isPrime[i] = true;

            // Find the square root of max.
            int maxRoot = (int)Math.Sqrt(max);

            // Cross out multiples of odd primes.
            for (int i = 3; i <= max; i += 2)
            {
                // If i > maxRoot, then there are no more entries to check.
                if (i > maxRoot) break;

                // See if i is prime.
                if (isPrime[i])
                {
                    // Knock out multiples of i.
                    for (int j = i * i; j <= max; j += i)
                        isPrime[j] = false;
                }
            }

            // Convert the sieve into a list of primes.
            List<int> result = new List<int>();
            for (int i = 2; i <= max; i++) if (isPrime[i]) result.Add(i);

            return result;
        }


        /// <summary>
        /// Required designer variable.
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
        /// Clean up any resources being used.
        /// </summary>
        /// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Windows Form Designer generated code

        /// <summary>
        /// Required method for Designer support - do not modify
        /// the contents of this method with the code editor.
        /// </summary>
        private void InitializeComponent()
        {
            this.actualPrimesLabel = new System.Windows.Forms.Label();
            this.label4 = new System.Windows.Forms.Label();
            this.estPrimesLabel = new System.Windows.Forms.Label();
            this.label2 = new System.Windows.Forms.Label();
            this.maxNumberTextBox = new System.Windows.Forms.TextBox();
            this.label1 = new System.Windows.Forms.Label();
            this.findPrimesButton = new System.Windows.Forms.Button();
            this.primesTextBox = new System.Windows.Forms.TextBox();
            this.SuspendLayout();
            // 
            // actualPrimesLabel
            // 
            this.actualPrimesLabel.BorderStyle = System.Windows.Forms.BorderStyle.Fixed3D;
            this.actualPrimesLabel.Location = new System.Drawing.Point(97, 70);
            this.actualPrimesLabel.Name = "actualPrimesLabel";
            this.actualPrimesLabel.Size = new System.Drawing.Size(74, 20);
            this.actualPrimesLabel.TabIndex = 37;
            this.actualPrimesLabel.TextAlign = System.Drawing.ContentAlignment.MiddleRight;
            // 
            // label4
            // 
            this.label4.AutoSize = true;
            this.label4.Location = new System.Drawing.Point(12, 74);
            this.label4.Name = "label4";
            this.label4.Size = new System.Drawing.Size(74, 13);
            this.label4.TabIndex = 36;
            this.label4.Text = "Actual Primes:";
            this.label4.TextAlign = System.Drawing.ContentAlignment.MiddleLeft;
            // 
            // estPrimesLabel
            // 
            this.estPrimesLabel.BorderStyle = System.Windows.Forms.BorderStyle.Fixed3D;
            this.estPrimesLabel.Location = new System.Drawing.Point(97, 47);
            this.estPrimesLabel.Name = "estPrimesLabel";
            this.estPrimesLabel.Size = new System.Drawing.Size(74, 20);
            this.estPrimesLabel.TabIndex = 35;
            this.estPrimesLabel.TextAlign = System.Drawing.ContentAlignment.MiddleRight;
            // 
            // label2
            // 
            this.label2.AutoSize = true;
            this.label2.Location = new System.Drawing.Point(12, 51);
            this.label2.Name = "label2";
            this.label2.Size = new System.Drawing.Size(62, 13);
            this.label2.TabIndex = 34;
            this.label2.Text = "Est. Primes:";
            this.label2.TextAlign = System.Drawing.ContentAlignment.MiddleLeft;
            // 
            // maxNumberTextBox
            // 
            this.maxNumberTextBox.Location = new System.Drawing.Point(97, 14);
            this.maxNumberTextBox.Name = "maxNumberTextBox";
            this.maxNumberTextBox.Size = new System.Drawing.Size(74, 20);
            this.maxNumberTextBox.TabIndex = 30;
            this.maxNumberTextBox.Text = "10000";
            this.maxNumberTextBox.TextAlign = System.Windows.Forms.HorizontalAlignment.Right;
            // 
            // label1
            // 
            this.label1.AutoSize = true;
            this.label1.Location = new System.Drawing.Point(12, 17);
            this.label1.Name = "label1";
            this.label1.Size = new System.Drawing.Size(70, 13);
            this.label1.TabIndex = 33;
            this.label1.Text = "Max Number:";
            // 
            // findPrimesButton
            // 
            this.findPrimesButton.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Right)));
            this.findPrimesButton.Location = new System.Drawing.Point(247, 12);
            this.findPrimesButton.Name = "findPrimesButton";
            this.findPrimesButton.Size = new System.Drawing.Size(75, 23);
            this.findPrimesButton.TabIndex = 31;
            this.findPrimesButton.Text = "Find Primes";
            this.findPrimesButton.UseVisualStyleBackColor = true;
            this.findPrimesButton.Click += new System.EventHandler(this.btnFindPrimes_Click);
            // 
            // primesTextBox
            // 
            this.primesTextBox.Anchor = ((System.Windows.Forms.AnchorStyles)((((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom) 
            | System.Windows.Forms.AnchorStyles.Left) 
            | System.Windows.Forms.AnchorStyles.Right)));
            this.primesTextBox.Location = new System.Drawing.Point(15, 93);
            this.primesTextBox.Multiline = true;
            this.primesTextBox.Name = "primesTextBox";
            this.primesTextBox.ScrollBars = System.Windows.Forms.ScrollBars.Vertical;
            this.primesTextBox.Size = new System.Drawing.Size(307, 156);
            this.primesTextBox.TabIndex = 38;
            // 
            // frm85SieveOfEratosthenes
            // 
            this.AcceptButton = this.findPrimesButton;
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(334, 261);
            this.Controls.Add(this.primesTextBox);
            this.Controls.Add(this.actualPrimesLabel);
            this.Controls.Add(this.label4);
            this.Controls.Add(this.estPrimesLabel);
            this.Controls.Add(this.label2);
            this.Controls.Add(this.maxNumberTextBox);
            this.Controls.Add(this.label1);
            this.Controls.Add(this.findPrimesButton);
            this.Name = "frm85SieveOfEratosthenes";
            this.Text = "SieveOfEratosthenes";
            this.ResumeLayout(false);
            this.PerformLayout();

        }

        #endregion

        private System.Windows.Forms.Label actualPrimesLabel;
        private System.Windows.Forms.Label label4;
        private System.Windows.Forms.Label estPrimesLabel;
        private System.Windows.Forms.Label label2;
        private System.Windows.Forms.TextBox maxNumberTextBox;
        private System.Windows.Forms.Label label1;
        private System.Windows.Forms.Button findPrimesButton;
        private System.Windows.Forms.TextBox primesTextBox;
    }
}