具有 Biginteger 计算的控制台应用程序冻结
A console app with Biginteger calculation freezes
问题
具有 Biginteger 计算的控制台应用程序冻结
详情
我正在用 C# 开发一个控制台应用程序，它测试非常大的数字（10 的几十到几百次方）是否是质数。由于默认整数类型最多只能处理 10^19（long、ulong）的数字，因此我使用 BitInteger class。但是当我 运行 应用程序处于 Visual Studio 的调试模式时，应用程序冻结了。
static void Main(string[] args)
{
int exp = 100;
var bi = BigInteger.Pow(10, exp);
var sw = new Stopwatch();
sw.Start();
for (int i = 0; i < 1000; i++)
{
bi++;
Console.WriteLine($"{i}th try : {bi} ({sw.Elapsed.ToString("mm\:ss\.ff")})");
bool b = IsPrime(bi);
if (b)
{
Console.WriteLine($"{bi} is a prime number");
}
//GC.Collect();
}
sw.Stop();
Console.Read();
}
static private bool IsPrime(BigInteger n)
{
if (n <= 1)
return false;
else if (n <= 3)
return true;
else if (n % 2 == 0 || n % 3 == 0)
return false;
for (BigInteger i = 5; i * i <= n; i += 6)
{
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
程序是否卡顿取决于变量exp。我测试了 exp.
的几个值
- （
exp 的值）：（i 程序冻结）
- 10 : 没有冻结（应用程序在不到一秒内完成
- 15 : 没有冻结（但是控制台 window 每 2 秒刷新一次）
- 17 : 没有冻结（但是控制台 window 每 17 秒才刷新一次）
- 20 : 39
- 25 : 13
- 30 : 37
- 50 : 27
- 100 : 37
奇怪的是 i 不会随着 exp 的增加而单调上升。所以我 运行 程序 exp = 100 三次但得到相同的结果。这些数字似乎是可重现和可靠的。
我知道有比这个更好的测试素数的算法，但我稍后会尝试它们。首先，我想检查程序的整个行为。
我用谷歌搜索 "biginteger console freeze c#" 这个问题，找到了两篇文章。
- C# BigInteger and int How to save memory?
第一个说 "freeze" 和 "Biginteger" 但答案没有太大帮助。第二个提到节省内存，所以我认为问题是关于垃圾收集的。然后我在 for 循环（注释掉的行）的末尾添加了 GC.Collect() 但这并没有解决问题。我得到了相同的结果。
我该如何解决这个问题？
环境
- Windows 8
- Visual Studio 2017
- C#
- .NET Framework 4.6.1
你的算法基本上说：
are you divisible by 2? what about 3? what about 5? 7? 11? 13? 17? 19?
等等等等
对于小输入值，检查所有这些排列很快。对于大输入值，如果大输入值具有小因子（例如 2、3、5 或 37），它 可以 很快。
但是如果大输入缺少一个小因子（要么因为它是质数，要么因为它的最小因子很大），你的算法必须做一个lot 检查。基本上它必须检查三分之一（即每六个中的两个）数字直到输入的平方根（直到找到匹配项）。对于大数，这涉及 lot 的计算。
如果花费的时间太长，您需要编写更好/更快的 IsPrime 算法。 This answer 在这方面可能会有所帮助。
您还可以考虑存储 known large 个素数的 some 列表，以使这些数字能够可以快速查找（例如从数据库中）而不是 'calculated'.
回复：
(however the console window refreshes only every 17 seconds)
这是因为一些输入确实是质数 - 因此需要 17 秒左右的时间来验证（即检查每个排列）。在您看来，看起来 控制台仅每 17 秒刷新一次，但实际上它 计算 17 秒。然后后续的计算速度非常快（因为它们不是素数） - 所以看起来它们会出来 'as a batch'.
问题
具有 Biginteger 计算的控制台应用程序冻结
详情
我正在用 C# 开发一个控制台应用程序，它测试非常大的数字（10 的几十到几百次方）是否是质数。由于默认整数类型最多只能处理 10^19（long、ulong）的数字，因此我使用 BitInteger class。但是当我 运行 应用程序处于 Visual Studio 的调试模式时，应用程序冻结了。
static void Main(string[] args)
{
int exp = 100;
var bi = BigInteger.Pow(10, exp);
var sw = new Stopwatch();
sw.Start();
for (int i = 0; i < 1000; i++)
{
bi++;
Console.WriteLine($"{i}th try : {bi} ({sw.Elapsed.ToString("mm\:ss\.ff")})");
bool b = IsPrime(bi);
if (b)
{
Console.WriteLine($"{bi} is a prime number");
}
//GC.Collect();
}
sw.Stop();
Console.Read();
}
static private bool IsPrime(BigInteger n)
{
if (n <= 1)
return false;
else if (n <= 3)
return true;
else if (n % 2 == 0 || n % 3 == 0)
return false;
for (BigInteger i = 5; i * i <= n; i += 6)
{
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
程序是否卡顿取决于变量exp。我测试了 exp.
- （
exp的值）：（i程序冻结） - 10 : 没有冻结（应用程序在不到一秒内完成
- 15 : 没有冻结（但是控制台 window 每 2 秒刷新一次）
- 17 : 没有冻结（但是控制台 window 每 17 秒才刷新一次）
- 20 : 39
- 25 : 13
- 30 : 37
- 50 : 27
- 100 : 37
奇怪的是 i 不会随着 exp 的增加而单调上升。所以我 运行 程序 exp = 100 三次但得到相同的结果。这些数字似乎是可重现和可靠的。
我知道有比这个更好的测试素数的算法，但我稍后会尝试它们。首先，我想检查程序的整个行为。
我用谷歌搜索 "biginteger console freeze c#" 这个问题，找到了两篇文章。
- C# BigInteger and int How to save memory?
第一个说 "freeze" 和 "Biginteger" 但答案没有太大帮助。第二个提到节省内存，所以我认为问题是关于垃圾收集的。然后我在 for 循环（注释掉的行）的末尾添加了 GC.Collect() 但这并没有解决问题。我得到了相同的结果。
我该如何解决这个问题？
环境
- Windows 8
- Visual Studio 2017
- C#
- .NET Framework 4.6.1
你的算法基本上说：
are you divisible by 2? what about 3? what about 5? 7? 11? 13? 17? 19?
等等等等
对于小输入值，检查所有这些排列很快。对于大输入值，如果大输入值具有小因子（例如 2、3、5 或 37），它 可以 很快。
但是如果大输入缺少一个小因子（要么因为它是质数，要么因为它的最小因子很大），你的算法必须做一个lot 检查。基本上它必须检查三分之一（即每六个中的两个）数字直到输入的平方根（直到找到匹配项）。对于大数，这涉及 lot 的计算。
如果花费的时间太长，您需要编写更好/更快的 IsPrime 算法。 This answer 在这方面可能会有所帮助。
您还可以考虑存储 known large 个素数的 some 列表，以使这些数字能够可以快速查找（例如从数据库中）而不是 'calculated'.
回复：
(however the console window refreshes only every 17 seconds)
这是因为一些输入确实是质数 - 因此需要 17 秒左右的时间来验证（即检查每个排列）。在您看来，看起来 控制台仅每 17 秒刷新一次，但实际上它 计算 17 秒。然后后续的计算速度非常快（因为它们不是素数） - 所以看起来它们会出来 'as a batch'.