寻找素数的程序

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, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
    Enumerable.Range(2, num-1).ToList(), 
    (result, index) => { 
        var bp = result[index]; var sqr = bp * bp;
        result.RemoveAll(i => i >= sqr && i % bp == 0); 
        return result; 
    }
);

这里使用的素数的近似公式是?(x) < 1.26 x / ln(x).我们只需要通过不大于的素数进行测试x = sqrt(num).

请注意,Eratosthenes的筛网比试验分区具有更好的运行时间复杂度(num如果正确实施,应该更快地运行更大的值).

Answer 2

试试这个:

void prime_num(long num)
{

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

Answer 3

您只需要检查奇数除数,直到数字的平方根.换句话说,你的内循环需要开始:

for (int j = 3; j <= Math.Sqrt(i); j+=2) { ... }

一旦发现数字不是素数,你也可以打破这个功能,你不需要检查任何更多的除数(我看你已经这样做了!).

这仅在num大于2时才有效.

没有Sqrt

您可以通过保持运行总和来完全避免Sqrt.例如:

int square_sum=1;
for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}

这是因为数字1+(3 + 5)+(7 + 9)的总和将给出一系列奇数正方形(1,9,25等).因此j代表了平方根square_sum.只要square_sum不到i那么j小于平方根.

Answer 4

人们已经提到了一些有效实现这一目标的构建模块,但没有人真正将这些部分组合在一起.Eratosthenes的筛子是一个很好的开始,但是在你达到你设定的极限之前很久你就会失去记忆.这并不意味着它没用 - 当你做循环时,你真正关心的是主要的除数.因此,您可以首先使用筛子来创建素数除数的基数,然后使用循环中的那些来测试数字的首要性.

但是,当你编写循环时,你真的不希望我们在循环条件中使用sqrt(i),因为有几个答案已经提出.您和我知道sqrt是一个"纯"函数,如果给出相同的输入参数,它总是给出相同的答案.不幸的是,编译器不知道,所以如果在循环条件中使用类似'<= Math.sqrt(x)'的东西,它将在循环的每次迭代中重新计算数字的sqrt.

您可以通过几种不同的方式避免这种情况.您可以在循环之前预先计算sqrt,并在循环条件中使用预先计算的值,或者您可以在另一个方向上工作,并更改i<Math.sqrt(x)为i*i<x.就个人而言,我预先计算了平方根 - 我认为它更清晰,可能更快一点 - 但这取决于循环的迭代次数(i*i意味着它仍然在循环中进行乘法运算).只需几次迭代,i*i通常会更快.通过足够的迭代,i*i每次迭代的损失超过了sqrt在循环外执行一次的时间.

这可能足以满足你正在处理的数字的大小 - 15位数的限制意味着平方根是7或8位数,这适合相当合理的内存量.另一方面,如果你想要处理这个范围内的数字很多,你可能想看一些更复杂的质数检查算法,比如Pollard或Brent的算法.这些更复杂(温和地说)但对于大数字来说要快得多.

还有其他算法可用于更大的数字(二次筛,一般数字筛)但我们暂时不会进入它们 - 它们要复杂得多,而且实际上只对处理非常大的数字有用( GNFS在100多位数范围内开始有用).

Answer 5

第一步:编写扩展方法以确定输入是否为素数

public static bool isPrime(this int number ) {

    for (int i = 2; i < number; i++) { 
        if (number % i == 0) { 
            return false; 
        } 
    }

    return true;   
}

2步:编写将打印介于0和数字输入之间的所有素数的方法

public static void getAllPrimes(int number)
{
    for (int i = 0; i < number; i++)
    {
        if (i.isPrime()) Console.WriteLine(i);
    }
}

Answer 6

EDIT_ADD: 如果Will Ness是正确的,问题的目的只是在程序运行时输出连续的素数流(按暂停/中断暂停,任何键重新开始),没有任何严重的希望那个上限,那么代码应该写成没有上限参数,并且第一个'i'for循环的范围检查为"true".另一方面,如果问题想要实际打印质数达到一个限制,那么下面的代码将更有效地使用Trial Division进行奇数操作,其优点是它根本不使用内存(它也可以按照上面的方式转换为连续循环):

static void primesttt(ulong top_number) {
  Console.WriteLine("Prime:  2");
  for (var i = 3UL; i <= top_number; i += 2) {
    var isPrime = true;
    for (uint j = 3u, lim = (uint)Math.Sqrt((double)i); j <= lim; j += 2) {
      if (i % j == 0)  {
        isPrime = false;
        break;
      }
    }
    if (isPrime) Console.WriteLine("Prime:  {0} ", i);
  }
}

首先,问题代码不产生输出,因为它的循环变量是整数,并且测试的极限是一个巨大的长整数,这意味着循环不可能达到产生内循环EDITED的限制: 其中变量'j'循环回到负数; 当'j'变量回到-1时,测试数字未通过主要测试,因为所有数字均可被-1 END_EDIT整除 .即使这被纠正,问题代码也会产生非常慢的输出,因为它会被大量复合数字(所有偶数加上奇数复合数)的64位除以整个数字范围直到顶部对于它可能产生的每个素数,十个幂增加到十六个幂.上面的代码是有效的,因为它将计算限制为仅奇数,并且仅模数除以当前正在测试的数字的平方根.

这需要一个小时左右的时间来显示高达十亿的素数,因此可以想象将所有质数显示到一万亿(10提升到十六分之一)所需的时间量,特别是当计算变慢时随着范围的增加. END_EDIT_ADD

虽然@SLaks使用Linq的单线(一种)答案起作用,但它并不是真正的Eratosthenes的Sieve,因为它只是一个未经优化的试验版本,未经优化,因为它不会消除奇数素数,无法启动在找到的基本素数的平方上,并且不会停止剔除大于顶部数字的平方根的基本素数来筛选.由于多个嵌套的枚举操作,它也很慢.

它实际上是滥用Linq Aggregate方法,并没有有效地使用生成的两个Linq Range中的第一个.它可以成为一个优化的试验部门,具有较少的枚举开销,如下所示:

static IEnumerable<int> primes(uint top_number) {
  var cullbf = Enumerable.Range(2, (int)top_number).ToList();
  for (int i = 0; i < cullbf.Count; i++) {
    var bp = cullbf[i]; var sqr = bp * bp; if (sqr > top_number) break;
    cullbf.RemoveAll(c => c >= sqr && c % bp == 0);
  } return cullbf; }

它的运行速度比SLaks的速度快很多倍.但是,由于List生成和多个枚举以及多重除法(模数隐含)操作,它仍然很慢并且内存密集.

以下真正的Eratosthenes实现的Sieve运行速度提高了大约30倍并且占用的内存要少得多,因为它只对每个筛选的数字使用一位表示并将其枚举限制为最终的迭代器序列输出,并且优化仅处理奇数复合,并且只从基本素数的平方中剔除基本素数直到最大数的平方根,如下所示:

static IEnumerable<uint> primes(uint top_number) {
  if (top_number < 2u) yield break;
  yield return 2u; if (top_number < 3u) yield break;
  var BFLMT = (top_number - 3u) / 2u;
  var SQRTLMT = ((uint)(Math.Sqrt((double)top_number)) - 3u) / 2u;
  var buf = new BitArray((int)BFLMT + 1,true);
  for (var i = 0u; i <= BFLMT; ++i) if (buf[(int)i]) {
      var p = 3u + i + i; if (i <= SQRTLMT) {
        for (var j = (p * p - 3u) / 2u; j <= BFLMT; j += p)
          buf[(int)j] = false; } yield return p; } }

上面的代码在Intel i7-2700K(3.5 GHz)上计算出大约77毫秒内所有质数到千万范围.

可以使用using语句和静态Main方法调用和测试两个静态方法中的任何一个,如下所示:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

static void Main(string[] args) {
  Console.WriteLine("This program generates prime sequences.\r\n");

  var n = 10000000u;

  var elpsd = -DateTime.Now.Ticks;

  var count = 0; var lastp = 0u;
  foreach (var p in primes(n)) { if (p > n) break; ++count; lastp = (uint)p; }

  elpsd += DateTime.Now.Ticks;
  Console.WriteLine(
    "{0} primes found <= {1}; the last one is {2} in {3} milliseconds.",
    count, n, lastp,elpsd / 10000);

  Console.Write("\r\nPress any key to exit:");
  Console.ReadKey(true);
  Console.WriteLine();
}

这将显示序列中的素数数量达到极限,最后找到的素数,以及计算那么远的时间.

EDIT_ADD: 但是,为了产生一个小于万万(10到16的幂)的素数的枚举问题,需要使用多核处理的分段分页方法,但即使使用C++和非常高度优化的PrimeSieve,这将需要超过400小时才能产生所发现的素数,并且需要数十倍的长时间来列举所有这些素数以便在一年之内完成问题所要求的问题.为了使用未经优化的试验分区算法进行尝试,即使使用优化的试验分区算法也需要超长时间和非常长的时间,例如在十亿到二百万电力年(这是两百万零年! !).

当他试用它时,他的台式机只是坐着并且停滞不动也就不足为奇了!如果他尝试了一个较小的范围,如一百万,他仍然会发现它需要在实施的秒范围内.

我在这里发布的解决方案不会削减它,因为即使是最后一个Eratosthenes的Sieve也需要大约640TB的内存.

这就是为什么只有像PrimeSieve那样的页面分段方法可以处理所有指定范围的这类问题,甚至需要很长时间,如几周到几年,除非有人可以访问超级计算机数十万个核心. END_EDIT_ADD

Answer 7

这可能只是我的观点,但是你的程序中还有另一个严重的错误(抛开给定的'素数'问题,已经得到了彻底的回答).

和其他响应者一样,我假设这是家庭作业,这表明你想成为一名开发人员(大概).

您需要学习划分代码.这不是你在项目中总是需要做的事情,但知道如何去做是件好事.

你的方法prime_num(long num)可以代表一个更好,更具描述性的名字.如果它应该找到小于给定数字的所有素数,它应该将它们作为列表返回.这样可以更轻松地分离显示和功能.

如果它只是返回一个包含素数的IList,那么你可以在主函数中显示它们(可能调用另一个外部函数来打印它们)或者在进一步的计算中使用它们.

所以我最好的建议就是这样做:

public void main(string args[])
{
    //Get the number you want to use as input
    long x = number;//'number' can be hard coded or retrieved from ReadLine() or from the given arguments

    IList<long> primes = FindSmallerPrimes(number);

    DisplayPrimes(primes);
}

public IList<long> FindSmallerPrimes(long largestNumber)
{
    List<long> returnList = new List<long>();
    //Find the primes, using a method as described by another answer, add them to returnList
    return returnList;
}

public void DisplayPrimes(IList<long> primes)
{
    foreach(long l in primes)
    {
        Console.WriteLine ( "Prime:" + l.ToString() );
    }
}

即使你最终在某个不需要这种拼版的地方工作,最好知道怎么做.

Answer 8

闻起来更像是家庭作业.我非常古老的图形计算器有一个像这样的主要程序.技术上,内部划分检查循环只需要运行到i ^(1/2).你需要找到0到L之间的"全部"素数吗？另一个主要问题是你的循环变量是"int",而你的输入数据是"长",这将导致溢出使你的循环甚至一次都无法执行.修复循环变量.