C# 查找[m,n]范围内的所有素数

     static int[] FindPrime(int m, int n)
        {
            if (m < 2 || n < m)
                return new int[0];
 
            List<int> result = new List<int>(n - m + 1);
            int i, j, t;
            // 如果m为偶数则加一，因为偶数不可能为素数（除去2）
            if ((m & 1) == 0)
            {
                // 如果为2则需要添加返回结果
                if (m == 2)
                    result.Add(m);
                ++m;
            }
            bool status = true;
            // 从奇数开始遍历，每次加2，保证每次判断的数都是奇数
            for (i = m; i <= n; i += 2)
            {
                // 开根号的原因：两个数的乘积为i，只需要判断到根号i即可，不需要判断完，完全没得必要
                t = (int)Math.Sqrt(i);
                status = true;
 
                /* 证明：
                 * 可以将其表示为 (2k + 1) * n，其中 n 是另一个数；
                 * 展开乘法得到：(2k + 1) * n = 2kn + n = 2kn + n；
                 * 可以看到，无论 n 是奇数还是偶数，2kn 部分一定是偶数，而 n 部分保持不变。偶数加上一个奇数仍然是奇数。因此，奇数的乘积一定是奇数。
                 * 对于任意给定的奇数与其他数相乘，乘积一定是奇数。这是奇数性质的一个特例。
                 */
                // 因此这里判断从奇数3开始，每次都加2，只需要判断这个奇数能否被另外一个奇数整除，如果不能被整除则为素数
                for (j = 3; j <= t; j += 2)
                {
                    // 是否能被整除，如果是则不是素数
                    if (i % j == 0)
                    {
                        status = false;
                        break;
                    }
                }
                if (status)
                    result.Add(i);
            }
            return result.ToArray();
        }

时间复杂度：O((n-m) * √n)，其中 n 和 m 分别是输入的上限和下限。