计划寻找素数

我想find0和一个长variables之间的素数，但我不能得到任何输出。

该计划是

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)的素数来testing。

请注意， 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的筛子是一个很好的开始，但是在你达到你设定的极限之前，你将会用尽记忆。 这并不意味着它是无用的 – 当你在做循环时，你真正关心的是素数因子。 因此，您可以开始使用筛子来创build素数因子的基数，然后使用循环中的数字来testing数字以确定首位。

然而，当你写循环时，你真的不希望我们sqrt（i）在循环条件下，有几个答案build议。 你和我知道sqrt是一个“纯粹”的function，如果给定相同的input参数，它总是给出相同的答案。 不幸的是，编译器不知道，所以如果在循环条件中使用类似'<= Math.sqrt（x）'的东西，它将在循环的每次迭代中重新计算数字的sqrt。

你可以避免这种情况。 你可以在循环之前预先计算sqrt，并且在循环条件中使用预先计算的值，或者你可以在另一个方向上工作，并且改变iii意味着它仍然在循环中进行乘法运算。

这对于处理数字的大小来说可能是足够的–15位数字的限制意味着平方根是7或8位数，这个数字适合于相当合理的内存量。 另一方面，如果你想处理这个范围内的数字，你可能需要看一些更复杂的素数检查algorithm，比如Pollard或者Brentalgorithm 。 这些比较复杂（比较温和），但是对于大数量来说要快得多。

还有其他algorithm甚至更大的数字（ 二次筛选 ， 通用数字场筛 ），但我们暂时不会进入他们 – 他们是更复杂，真的只有处理真正的大数字（ GNFS开始在100多位数字范围内有用）。

Answer 5

这可能只是我的意见，但是在你的程序中还有一个严重的错误（抛开给定的“素数”问题，这个问题已经得到了彻底的回答）。

像其他的反应者一样，我假设这是作业，这表明你想成为一名开发者（大概）。

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

你的方法prime_num（long num）可以是一个更好，更具描述性的名字。 如果它应该find所有小于给定数字的素数，则应将其作为列表返回。 这使得更容易分离您的显示器和您的function。

如果它简单地返回一个包含素数的IList，则可以将它们显示在主函数中（也许调用另一个外函数来打印它们），或者在进一步的计算中使用它们。

所以我最好的build议是做这样的事情：

 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 6

第一步：编写一个扩展方法来确定input是否为素数

 public static bool isPrime(this int number ) { for (int i = 2; i < number; i++) { if (number % i == 0) { return false; } } return true; } 

第2步：写出将打印0和input数字之间的所有素数的方法

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

Answer 7

闻起来像更多的功课。 我非常非常老的graphics计算器有这样的主要计划。 从技术上来说，内部的devision检查循环只需要运行到i ^（1/2）。 你需要find0到L之间的“所有”素数吗？ 另一个主要的问题是你的循环variables是“int”，而你的input数据是“long”，这将导致溢出，使你的循环不能执行一次。 修复循环variables。

Answer 8

EDIT_ADD：如果Will Ness是正确的，那么问题的目的只是在程序运行的时候输出一个连续的质数据stream（按暂停/断点暂停，任何键可以重新开始），而没有严重的希望，该上限，那么代码应写入没有上限参数和第一个“我”for循环的范围检查“真”。 另一方面，如果问题想要实际打印质数达到极限，那么下面的代码将只使用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); } } 

首先，问题代码不会产生输出，因为它的循环variables是整数，testing的极限是一个巨大的长整数，这意味着循环不可能达到产生内部循环的极限EDITED：由此variables“j”循环回到负数; 当'j'variables回到-1时，被testing的数字不能通过初步testing，因为所有的数字都被-1 END_EDIT整除。 即使这个问题得到解决，问题代码也会产生非常慢的输出，因为它被绑定到64位的非常大数量的合成数字（所有的偶数加上奇数的合成）除以整个范围的数字十个数量提高到十六分之一的能力，对于它可能产生的每个素数。 上面的代码是可行的，因为它将计算限制为只有奇数，并且只对模数进行除数，直到当前被测数字的平方根。

这需要一个小时左右的时间才能显示高达10亿的素数，所以我们可以想象，显示所有素数达到万兆（10次提高到十六次方）需要花费的时间，特别是当计算速度变慢随着范围的增加。 END_EDIT_ADD

尽pipe@SLaks使用Linq的方法来回答这个问题，但这并不是Eratosthenes的Sieve，因为它只是Trial Division的一个未经优化的版本，没有被优化，因为它并没有消除奇素数，也没有开始在find的基本素数的平方，并且不停止剔除大于要筛选的最大数字的平方根的基本素数。 由于多重嵌套枚举操作，这也很慢。

这实际上是Linq Aggregate方法的滥用，并没有有效地使用两个Linq Range的第一个生成的。 它可以成为一个优化的试用部门，具有较less的枚举开销如下：

 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的答案快很多倍。 然而，由于列表生成和多重枚举以及多重分割（由模数隐含）操作，它仍然是缓慢的和内存密集的。

以下的Eratosthenes实现的Sieve运行速度提高了大约30倍，并且占用的内存也less得多，因为它只使用每筛选一位的表示，并将其枚举限制为最终的迭代器序列输出，并且优化只处理奇怪的合成，只能从基本素数的平方剔除基本素数，直到最大数的平方根，如下所示：

 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; } } 

上述代码在英特尔i7-2700K（3.5 GHz）上在大约77毫秒内计算出一千万个质量的所有质数。

可以使用using语句和静态Main方法调用和testing两个静态方法中的任一个，如下所示：

 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(); } 

它将显示序列中达到限制的素数数目，find的最后一个素数，以及列举的最长时间。

EDIT_ADD：然而，为了产生一个不到万兆（十到十六次方）的质数的问题，需要使用多核处理的分段分页方法，但是即使使用C ++和高度优化的PrimeSieve ，这将需要超过400小时的时间来产生发现的素数，并且长达数十倍的时间来列举所有这些超过一年的问题。 为了做到这一点，使用未经优化的试algorithmalgorithm，即使使用经过优化的试algorithmalgorithm，也需要超长的时间和非常长的时间，就像在百万分之一至二百万年（即两百万年！ ！）。

他的桌上型电脑刚试过时就坐下来，并不奇怪！ 如果他尝试了一个更小的范围，比如100万，他仍然会发现在实施过程中需要花费几秒钟的时间。

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

这就是为什么只有像PrimeSieve这样的页面分割方法才能够处理这种范围的问题，甚至需要很长的时间，比如几周到几年，除非有人能够访问超级计算机数十万个核心。 END_EDIT_ADD

Answer 9

Eratosthenes的答案上面的答案是不完全正确的。 正如所写，它会find1到1000000之间的所有素数。要find1和num之间的所有素数，请使用：

 private static IEnumerable Primes01(int num) { return Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num)))) .Aggregate(Enumerable.Range(1, num).ToList(), (result, index) => { result.RemoveAll(i => i > result[index] && i%result[index] == 0); return result; } ); } 

聚合的种子应该是范围1到数字，因为这个列表将包含最终的素数列表。 Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num))))是种子被清除的次数。

Answer 10

ExchangeCore论坛有一个很好的控制台应用程序列表，看起来写入find素数的文件，它看起来像你也可以使用同一个文件作为一个起点，所以你不必重新从2find素数，他们提供下载那个文件全部find了1亿的质数，所以这将是一个好的开始。

在页面上的algorithm也采取了几个捷径（奇数，只有检查到平方根），这使得它非常有效，它可以让你计算长数字。

Answer 11

C＃中的一行代码： –

 Console.WriteLine(String.Join(Environment.NewLine, Enumerable.Range(2, 300) .Where(n => Enumerable.Range(2, (int)Math.Sqrt(n) - 1) .All(nn => n % nn != 0)).ToArray())); 

Answer 12

所以这基本上只是两个错别字 ，一个是最不幸的， for (int j = 2; j <= num; j++)这就是非生产性testing的原因1%2,1%3 ... 1%(10^15-1)持续很长时间，所以OP没有得到“任何输出” 。 它应该是j < i; 代替。 另一个比较小的是i应该从2开始，而不是从0开始：

 for( i=2; i <= num; i++ ) { for( j=2; j < i; j++ ) // j <= sqrt(i) is really enough .... 

当然，在任何合理的时间框架内完成28万亿素数的控制台打印是不能合理预期的。 所以，问题的原意显然是无限期地打印出一连串的素数。 因此，提出简单使用Eratosthenes滤网的所有解决scheme在这里完全没有任何价值，因为Eratosthenes的简单滤网是有界限的 – 必须事先设定一个界限。

在这里可以做的是优化的试验部门，它可以在发现它们时保存质数，并且对质数进行检验，而不仅仅是候选人以下的所有数字。

第二种select，复杂得多（即更快）是使用Eratosthenes的分段筛 。 这是增量和无限的。

这两种scheme都会使用双阶段素数生产 ：一种是生产和保存素数，在另一个阶段用于testing（或筛分），远高于第一阶段的限制（在其正方形之下） – 自动延长第一阶段，因为第二阶段会越来越远）。

Answer 13

坦率地说，一些build议的解决scheme真的很慢，因此是不好的build议。 为了testing一个单一的数字是素数，你需要一些除法/模运算符，但计算范围，你不必。

基本上，你只是排除早期发现的素数的倍数的数字，因为（根据定义）不是素数本身。

我不会给出完整的实现，因为这很容易，这是伪代码的方法。 （在我的机器上，实际的实现在8秒内计算Sytem.Int32（2亿）的所有素数。

 public IEnumerable<long> GetPrimes(long max) { // we safe the result set in an array of bytes. var buffer = new byte[long >> 4]; // 1 is not a prime. buffer[0] = 1; var iMax = (long)Math.Sqrt(max); for(long i = 3; i <= iMax; i +=2 ) { // find the index in the buffer var index = i >> 4; // find the bit of the buffer. var bit = (i >> 1) & 7; // A not set bit means: prime if((buffer[index] & (1 << bit)) == 0) { var step = i << 2; while(step < max) { // find position in the buffer to write bits that represent number that are not prime. } } // 2 is not in the buffer. yield return 2; // loop through buffer and yield return odd primes too. } } 

解决scheme需要对按位操作有一个很好的理解。 但它的方式和方式更快。 如果您需要以后使用，您也可以将结果的结果保存在光盘上。 1 * 17 * 10 ^ 9的结果可以用1 GB来保护，结果集的计算最多约2分钟。

Answer 14

非常相似 – 从一个练习实施Eratosthenes筛在C＃中：

 public class PrimeFinder { readonly List<long> _primes = new List<long>(); public PrimeFinder(long seed) { CalcPrimes(seed); } public List<long> Primes { get { return _primes; } } private void CalcPrimes(long maxValue) { for (int checkValue = 3; checkValue <= maxValue; checkValue += 2) { if (IsPrime(checkValue)) { _primes.Add(checkValue); } } } private bool IsPrime(long checkValue) { bool isPrime = true; foreach (long prime in _primes) { if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue)) { isPrime = false; break; } } return isPrime; } } 

Answer 15

总理帮手非常快速的计算

 public static class PrimeHelper { public static IEnumerable<Int32> FindPrimes(Int32 maxNumber) { return (new PrimesInt32(maxNumber)); } public static IEnumerable<Int32> FindPrimes(Int32 minNumber, Int32 maxNumber) { return FindPrimes(maxNumber).Where(pn => pn >= minNumber); } public static bool IsPrime(this Int64 number) { if (number < 2) return false; else if (number < 4 ) return true; var limit = (Int32)System.Math.Sqrt(number) + 1; var foundPrimes = new PrimesInt32(limit); return !foundPrimes.IsDivisible(number); } public static bool IsPrime(this Int32 number) { return IsPrime(Convert.ToInt64(number)); } public static bool IsPrime(this Int16 number) { return IsPrime(Convert.ToInt64(number)); } public static bool IsPrime(this byte number) { return IsPrime(Convert.ToInt64(number)); } } public class PrimesInt32 : IEnumerable<Int32> { private Int32 limit; private BitArray numbers; public PrimesInt32(Int32 limit) { if (limit < 2) throw new Exception("Prime numbers not found."); startTime = DateTime.Now; calculateTime = startTime - startTime; this.limit = limit; try { findPrimes(); } catch{/*Overflows or Out of Memory*/} calculateTime = DateTime.Now - startTime; } private void findPrimes() { /* The Sieve Algorithm http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes */ numbers = new BitArray(limit, true); for (Int32 i = 2; i < limit; i++) if (numbers[i]) for (Int32 j = i * 2; j < limit; j += i) numbers[j] = false; } public IEnumerator<Int32> GetEnumerator() { for (Int32 i = 2; i < 3; i++) if (numbers[i]) yield return i; if (limit > 2) for (Int32 i = 3; i < limit; i += 2) if (numbers[i]) yield return i; } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } // Extended for Int64 public bool IsDivisible(Int64 number) { var sqrt = System.Math.Sqrt(number); foreach (var prime in this) { if (prime > sqrt) break; if (number % prime == 0) { DivisibleBy = prime; return true; } } return false; } private static DateTime startTime; private static TimeSpan calculateTime; public static TimeSpan CalculateTime { get { return calculateTime; } } public Int32 DivisibleBy { get; set; } } 

Answer 16

  public static void Main() { Console.WriteLine("enter the number"); int i = int.Parse(Console.ReadLine()); for (int j = 2; j <= i; j++) { for (int k = 2; k <= i; k++) { if (j == k) { Console.WriteLine("{0}is prime", j); break; } else if (j % k == 0) { break; } } } Console.ReadLine(); } 

Answer 17

 static void Main(string[] args) { int i,j; Console.WriteLine("prime no between 1 to 100"); for (i = 2; i <= 100; i++) { int count = 0; for (j = 1; j <= i; j++) { if (i % j == 0) { count=count+1; } } if ( count <= 2) { Console.WriteLine(i); } } Console.ReadKey(); } 

Answer 18

U可以使用正常的素数概念，只有两个因素（一个和它本身）。 所以，这样做，简单的方法

 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace PrimeNUmber { class Program { static void FindPrimeNumber(long num) { for (long i = 1; i <= num; i++) { int totalFactors = 0; for (int j = 1; j <= i; j++) { if (i % j == 0) { totalFactors = totalFactors + 1; } } if (totalFactors == 2) { Console.WriteLine(i); } } } static void Main(string[] args) { long num; Console.WriteLine("Enter any value"); num = Convert.ToInt64(Console.ReadLine()); FindPrimeNumber(num); Console.ReadLine(); } } } 

Answer 19

该解决scheme显示0到100之间的所有素数。

  int counter = 0; for (int c = 0; c <= 100; c++) { counter = 0; for (int i = 1; i <= c; i++) { if (c % i == 0) { counter++; } } if (counter == 2) { Console.Write(c + " "); } } 

Answer 20

这是计算C＃素数的最快方法。

  void PrimeNumber(long number) { bool IsprimeNumber = true; long value = Convert.ToInt32(Math.Sqrt(number)); if (number % 2 == 0) { IsprimeNumber = false; } for (long i = 3; i <= value; i=i+2) { if (number % i == 0) { // MessageBox.Show("It is divisible by" + i); IsprimeNumber = false; break; } } if (IsprimeNumber) { MessageBox.Show("Yes Prime Number"); } else { MessageBox.Show("No It is not a Prime NUmber"); } } 

Answer 21

我知道这是一个安静的老问题，但在阅读这里之后： Eratosthenes维基

这是我从理解该algorithm写出来的方式：

 void SieveOfEratosthenes(int n) { bool[] primes = new bool[n + 1]; for (int i = 0; i < n; i++) primes[i] = true; for (int i = 2; i * i <= n; i++) if (primes[i]) for (int j = i * 2; j <= n; j += i) primes[j] = false; for (int i = 2; i <= n; i++) if (primes[i]) Console.Write(i + " "); } 

在第一个循环中，我们使用true来填充布尔数组。

第二个for循环将从2开始，因为1不是素数，并将检查素数是否仍然没有变化，然后将false指定给j的索引。

最后一个循环，我们只是打印时，它是素数。