该程序旨在在用户按下esc键之前运行；届时它将生成一个包含所有素数的文件。该文件的路径需要配置为目录结构的值。当我重新启动程序时，它将接受一个素数文本文件作为参数，并从其中断处开始读取它。并行处理部分和实现用于查找质数的筛子是我对木料刨削感兴趣的部分。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading.Tasks;
namespace Prime
{
public class Program
{
public static void Main(string[] args)
{
List<UInt64> primes = new List<UInt64>();
primes.Add(2);
UInt64 numberToCheck = 3;
if (args.Count() > 0)
{
numberToCheck = ReadPrimesToList(args[0].ToString(), out primes) +2;
}
try
{
bool quit = false;
Console.WriteLine("Prime Number Search");
while (!quit)
{
if (Console.KeyAvailable)
quit = Console.ReadKey().Key == ConsoleKey.Escape;
Console.Write("Processing: " + numberToCheck);
if (CheckForPrime(numberToCheck, primes))
{
primes.Add(numberToCheck);
Console.WriteLine(" Prime Found!");
}
else
Console.WriteLine(" Not Prime :(");
if (numberToCheck < UInt64.MaxValue)
numberToCheck+=2;
else
break;
}
Console.WriteLine("Exiting");
WritePrimesToFile(primes);
Console.WriteLine("< Press Any Key To Exit >");
Console.ReadKey();
}
catch
{
if (primes.Count > 0)
WritePrimesToFile(primes);
}
}
private static UInt64 ReadPrimesToList(string fileName, out List<UInt64> primes)
{
primes = new List<UInt64>();
FileInfo file = new FileInfo(fileName);
StreamReader reader = new StreamReader(file.OpenRead());
String lineIn = String.Empty;
while (!reader.EndOfStream)
{
lineIn = reader.ReadLine();
String[] numberStrings = lineIn.Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
foreach (String numberString in numberStrings)
{
primes.Add(UInt64.Parse(numberString));
}
}
return primes[primes.Count() - 1];
}
private static void WritePrimesToFile(List<UInt64> primes)
{
String dateAndTime = DateTime.Now.ToString("yyyyMMddhhmm");
String fileName = String.Format(@"<substitute your path here>\primes [{0}].txt", dateAndTime);
FileInfo file = new FileInfo(fileName);
using (StreamWriter writer = file.CreateText())
{
int maxLength = primes[primes.Count - 1].ToString().Length;
String line = String.Empty;
const int maxColumn = 16;
int column = 0;
foreach (UInt64 number in primes)
{
string numberString = number.ToString();
int numberLength = numberString.Length;
line += numberString.PadLeft(maxLength, ' ') + ((column < (maxColumn-1)) ? " " : String.Empty);
column++;
if (column == maxColumn)
{
writer.WriteLine(line);
line = string.Empty;
column = 0;
}
}
if (line.Length > 0)
writer.WriteLine(line);
writer.Flush();
writer.Close();
}
}
private static bool CheckForPrime(UInt64 numberToCheck, List<UInt64> primes)
{
if ((numberToCheck % 2) == 0)
return false;
UInt64 halfway = (UInt64)(Math.Ceiling((float)numberToCheck / 2F));
bool isprime = false;
UInt64 factor = 0;
Parallel.ForEach<UInt64>(primes, (prime, loopState) =>
{
if (prime > halfway)
{
isprime = true;
loopState.Stop();
}
if ((numberToCheck % prime) == 0)
{
factor = prime;
isprime = false;
loopState.Stop();
}
});
return (isprime && factor == 0);
}
}
}
#1 楼
到目前为止，没有答案告诉您此代码是完全错误的：if (prime > halfway)
{
isprime = true;
loopState.Stop();
}
您不能在
Parallel.Foreach上执行此操作-无法保证执行顺序。这就是并行循环的全部要点！ if (prime > halfway)
{
loopState.Break(); // join all 'previous' jobs
return; // terminate *this* job, not caring about others
}
另一个重要的事情是，对于此特定任务，简单的连续顺序for（...）很可能胜过并行版本。
我在Mono上测试的结果为1234567890，（愚蠢的我）
我在Mono 2上测试的结果为2 ^ 31-1，
if (prime >= halfway)
编辑：我看到一些报告暗示Mono上的Parallel.ForEach实现异常缓慢-希望能从Win dudes中获得一些替代结果。
关于“打乱内存边界”的注意事项：
我达到了从2到1339484197的内存限制
让我们做一个有趣的数学游戏：
小于N的素数的数量由
N / ln(N)估算。 我们的最大列表容量为
2GB（类似32/64位）。如果在32位上运行，则整个过程的可用内存总共为2GB。因此，您甚至无法拥有它。 我们正在使用
long，所以每个素数都占用8 bytes。为了增加更多的弊端，我们没有预先分配列表大小，因此我们在加倍模式下进行操作。这意味着，每当我们有2 ^ N个元素时，我们就会为2 * 2 ^ N个空间分配更多的空间，因此会暂时使用实际列表所需空间的3倍。那么这里发生了什么呢？
我们在
N = 1339484197处，所以列表中有〜N/ln(N)个元素=>〜64M primes 每个素数都占用8个字节，所以我们在消耗
~500MB的内存。/>现在我们增加了更多项目，需要加倍，因此我们必须分配
1GB more。总共是1.5GB。太多了。现在是个好消息：通过将
x3传递给List c'tor，我们可以获得更多MAX_SIZE素数。确实，我们可以得到x6，因为上述数学游戏的一个侧面含义是，我们可以安全地使用UInt32。 #2 楼
Console.Write非常慢。我的意思是还不错，但是比您想象的要糟。尝试类似的方法：在不经常更新控制台的情况下，可以大大提高速度。一个好的规则是每秒更新控制台的次数不要超过几次。
评论
\ $ \ begingroup \ $
实际上，过多使用控制台会导致（afaik无法捕获）异常，尤其是在主应用程序线程中使用时。
\ $ \ endgroup \ $
– Fge
2011年3月2日在13:33
\ $ \ begingroup \ $
@Fge如果发生这种情况，则会引发一个错误。不应假设您必须尝试避免使用控制台来避免异常。
\ $ \ endgroup \ $
– Paul
2012年11月14日，0：03
\ $ \ begingroup \ $
也许在这里也很有趣：stackoverflow.com/questions/21947452/…
\ $ \ endgroup \ $
–Vogel612♦
2014年5月14日晚上8:55
#3 楼
要检查多个数字的素数，应使用Eratosthenes筛。这是两个可以并行化的简单循环，时间复杂度仅为O（n log（n）log log（n））。正如Hannesh所说，写入控制台的速度非常慢，我想您可能应该避免编写“处理一些数字”，而只写最后处理的最后一个数字。
控制台功能也会造成瓶颈，特别是如果您在每个数字之后都进行检查，我会在询问用户是否按下键之前，请先检查1000或10000的数量。
#4 楼
这是我在一本书中看到的超可爱的实现。如果您希望可以对其进行优化。IEnumerable<int> numbers = Enumerable.Range(3, 100000);
var parallelQuery =
from n in numbers.AsParallel()
where Enumerable.Range(2, (int)Math.Sqrt(n)).All(i => n % i > 0)
select n;
int[] primes = parallelQuery.ToArray();
#5 楼
嗯...为了加快速度，我考虑了其他素数测试，例如Miller Rabin测试或AKS测试。这里是用C＃编写的Miller Rabin算法的代码示例。也许它可以并行化并且比您目前使用的方法更快？评论
\ $ \ begingroup \ $
昨晚我跌到了顶峰，素数从2到1339484197的组合内存使用量迫使运行时抛出System.OutOfMemoryException。因此，我不得不将素数可能要成批地写到文件中，并且只能保留足够的素数来测试SqRt。或考虑实施您建议的替代测试之一。
\ $ \ endgroup \ $
–clichekiller
2011-2-18在21:12
#6 楼
您可以考虑在达到> = sqrt（numberToTest）的素数后立即调整素数测试以纾困。证明（非常宽松地）是，总可以将一个复数写为两个整数因子（每个> 1）的乘积。在两个因子中，一个必须必然<=另一个。因此，当达到最坏情况的上限（即测试编号的平方根）时，您可以停止测试。还可以使用其他更有效的方法来测试素数，但是此调整所需的代码非常少。以下是我的调整的摘要：
删除了“中途”和“因素”变量及其用法。它们可能具有调试目的的价值，但是它们似乎有损于该方法的总体目标。
默认的isprime为true-如果我们一直通过候选因子进行全过程而未发现可整除的因子，则isprime = true是要返回的正确值。
通过将条件更改为首先对候选因子求平方，并在LINQ Where调用中将结果与numberToCheck进行比较，避免计算numberToCheck的平方根。如果重复的乘法运算超过计算整数平方根的成本，那么在测试更大的数字时可能会耗费时间。
我选择使用LINQ过滤质数的方式在哪里可能会对性能产生负面影响， TPL划分工作。我记得TPL团队读过一篇文章，他们对可索引IEnumerables的工作进行了不同的划分，我想在这里提供链接，但是我很难找到它。简而言之，这可能抵消了先前提供的性能改进。
无论如何，这是上述调整（未经测试）：
private static bool CheckForPrime(UInt64 numberToCheck, List<UInt64> primes)
{
if ((numberToCheck % 2) == 0)
return false;
bool isprime = true;
Parallel.ForEach(primes.Where(prime => prime*prime < numberToCheck),
(prime, loopState) =>
{
if ((numberToCheck % prime) == 0)
{
isprime = false;
loopState.Stop();
}
});
return isprime;
}
评论
\ $ \ begingroup \ $
因为定购了素数，所以可以用TakeWhile替换Where。
\ $ \ endgroup \ $
– CodesInChaos
2012年11月13日22:10
\ $ \ begingroup \ $
@CodesInChaos-TakeWhile是一项出色的改进。 +1
\ $ \ endgroup \ $
– devgeezer
2012年11月14日14:51
评论
\ $ \ begingroup \ $
但是您可以使用AsOrdered（）。
\ $ \ endgroup \ $
–亚当
2012年11月13日在22:58