寻找素数的程序

Question

寻找素数的程序

我想找到介于0和长变量之间的素数，但我无法获得任何输出。

该计划是

using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace ConsoleApplication16{
    class Program
    {
        void prime_num(long num)
        {
            bool isPrime = true;
            for (int i = 0; i <= num; i++)
            {
                for (int j = 2; j <= num; j++)
                {
                    if (i != j && i % j == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    Console.WriteLine ( "Prime:" + i );
                }
                isPrime = true;
            }
        }

        static void Main(string[] args)
        {
            Program p = new Program();
            p.prime_num (999999999999999L);
            Console.ReadLine();
        }
    }}

任何人都可以帮助我找出程序中可能出现的错误吗？

Answer 1

您可以使用近似最佳的试验分割筛在一条（长）线上更快地完成此操作，如下所示：Enumerable.Range(0,&nbsp;Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate( &nbsp;&nbsp;&nbsp;&nbsp;Enumerable.Range(2,&nbsp;num-1).ToList(),&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;(result,&nbsp;index)&nbsp;=>&nbsp;{&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;bp&nbsp;=&nbsp;result[index];&nbsp;var&nbsp;sqr&nbsp;=&nbsp;bp&nbsp;*&nbsp;bp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result.RemoveAll(i&nbsp;=>&nbsp;i&nbsp;>=&nbsp;sqr&nbsp;&&&nbsp;i&nbsp;%&nbsp;bp&nbsp;==&nbsp;0);&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;result;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;});这里使用的素数的近似公式是π(x) < 1.26 x / ln(x)。我们只需要通过不大于的素数进行测试x = sqrt(num)。请注意，Eratosthenes的筛网比试验分区具有更好的运行时间复杂度（num如果正确实施，应该更快地运行更大的值）。

Answer 2

试试这个：void&nbsp;prime_num(long&nbsp;num){ &nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;bool&nbsp;isPrime&nbsp;=&nbsp;true; &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(long&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<=&nbsp;num;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bool&nbsp;isPrime&nbsp;=&nbsp;true;&nbsp;//&nbsp;Move&nbsp;initialization&nbsp;to&nbsp;here &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(long&nbsp;j&nbsp;=&nbsp;2;&nbsp;j&nbsp;<&nbsp;i;&nbsp;j++)&nbsp;//&nbsp;you&nbsp;actually&nbsp;only&nbsp;need&nbsp;to&nbsp;check&nbsp;up&nbsp;to&nbsp;sqrt(i) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(i&nbsp;%&nbsp;j&nbsp;==&nbsp;0)&nbsp;//&nbsp;you&nbsp;don't&nbsp;need&nbsp;the&nbsp;first&nbsp;condition &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;isPrime&nbsp;=&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(isPrime) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Console.WriteLine&nbsp;(&nbsp;"Prime:"&nbsp;+&nbsp;i&nbsp;); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;isPrime&nbsp;=&nbsp;true; &nbsp;&nbsp;&nbsp;&nbsp;}}

Answer 3

您只需要检查奇数除数，直到数字的平方根。换句话说，你的内循环需要开始：for&nbsp;(int&nbsp;j&nbsp;=&nbsp;3;&nbsp;j&nbsp;<=&nbsp;Math.Sqrt(i);&nbsp;j+=2)&nbsp;{&nbsp;...&nbsp;}一旦发现数字不是素数，你也可以打破这个功能，你不需要检查任何更多的除数（我看你已经这样做了！）。这仅在num大于2时才有效。没有Sqrt您可以通过保持运行总和来完全避免Sqrt。例如：int&nbsp;square_sum=1;for&nbsp;(int&nbsp;j=3;&nbsp;square_sum<i;&nbsp;square_sum+=4*(j++-1))&nbsp;{...}这是因为数字1+（3 + 5）+（7 + 9）的总和将给出一系列奇数正方形（1,9,25等）。因此j代表了平方根square_sum。只要square_sum不到i那么j小于平方根。