C#版 - Leetcode204. Count Primes - 题解

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

99999999

5761455

100156172

5769933

public readonly int MaxNum = 1000000;
var numbers = new BitArray(MaxNum, true);

using System;

namespace Leetcode204_GetPrime_SieveMethod
{
    public class Solution
    {
        public int CountPrimes(int n)
        {
            int count = 0;
            bool[] isDelete = new bool[n];

            for (int i = 2; i * i < n; i++)
            {
                if (!isDelete[i])
                {
                    for (int j = i; i * j < n; j++)  // Use j to record times(倍数).
                    {
                        isDelete[i*j] = true;
                    }
                }
            }

            for (int i = 2; i < n; i++)
            {
                if (isDelete[i] == false)
                    count++;
            }

            return count;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            // 以下为测试
            Solution sol = new Solution();
            var result = sol.CountPrimes(100156150);
            Console.WriteLine(sol);
        }
    }
}

    public class Solution
    {
        public int CountPrimes(int n)
        {
            if (n < 2) return 0;
            bool[] isDelete = new bool[n];
            int max = (int) Math.Sqrt(n);
            var count = 0;
            for (int i = 2; i < n; i++)
            {
                if (isDelete[i])
                    continue;
                count++;
                if (i > max)
                    continue;
                for (int j = i * i; j < n; j += i)
                    isDelete[j] = true;
            }
            return count;
        }
    }

using System.Diagnostics;
Stopwatch stopWatch = new Stopwatch();
stopWatch.Start();

//Code

stopWatch.Stop();
// Get the elapsed time as a TimeSpan value.
TimeSpan ts = stopWatch.Elapsed;

// Format and display the TimeSpan value.
string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}", ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10);
Console.WriteLine(elapsedTime, "RunTime");