我试图通过避免删除重复的素数倍数来改进基本的埃拉托色尼筛法算法,但结果比我的预期更糟
我已经实现了两个返回范围 [2..max) 内的素数的方法
基础筛
public static List<int> Sieve22Max_Basic(int n) {
var primes = new List<int>();
var sieve = new BitArray(n, true); // default all number are prime
//int crossTotal = 0;
int sqrt_n = (int)Math.Sqrt(n) + 1;
for (int p = 2; p < sqrt_n; ++p) {
if (sieve[p]) {
primes.Add(p);
//var cross = new List<int>();
int inc = p == 2 ? p : 2 * p;
for (int mul = p * p; mul < n; mul += inc) {
// cross out multiple of prime p
// cross.Add(mul);
//++crossTotal;
sieve[mul] = false;
}
//if (cross.Count > 0)
// Console.WriteLine($"Prime {p}, cross out: {string.Join(' ', cross)}");
}
}
//Console.WriteLine($"crossTotal: {crossTotal:n0}");
for (int p = sqrt_n; p < n; ++p)
if (sieve[p])
primes.Add(p);
return primes;
}
运行 Sieve22Max_Basic(100)
,看到一些倍数超过一个(例如:45, 75, 63
)
Prime 2, cross out: 4 6 8 ... 96 98
Prime 3, cross out: 9 15 21 27 33 39 45 51 57 63 69 75 81 87 93 99
Prime 5, cross out: 25 35 45 55 65 75 85 95
Prime 7, cross out: 49 63 77 91
增强筛分
然后,我尝试通过使用存储 smallest prime divisor
的数组来改进( spd
) 每个数字。
45 = 3 x 5 // spd[45] = 3
75 = 3 x 5 x 5 // spd[75] = 3
63 = 3 x 3 x 7 // spd[63] = 3
当遍历素数 p 的倍数时,我不会划掉数字 mul
有 spd[mul] < p
因为mul
被spd[mul]
划掉了之前
public static List<int> Sieve22Max_Enh(int n) {
var sieve = new BitArray(n, true);
var spd = new int[n];
for (int i = 0; i < n; ++i) spd[i] = i;
var primes = new List<int>();
//int crossTotal = 0;
int sqrt_n = (int)Math.Sqrt(n) + 1;
for (int p = 2; p < sqrt_n; ++p) {
if (sieve[p]) {
primes.Add(p);
//var cross = new List<int>();
int inc = p == 2 ? 1 : 2;
for (long mul = p; mul * p < n; mul += inc) {
if (spd[mul] >= p) {
sieve[(int)(mul * p)] = false;
spd[mul * p] = p;
//++crossTotal;
//cross.Add((int)(mul * p));
}
}
//if (cross.Count > 0)
// Console.WriteLine($"Prime {p}, cross out: {string.Join(' ', cross)}");
}
}
//Console.WriteLine($"crossTotal: {crossTotal:n0}");
for (int p = sqrt_n; p < n; ++p)
if (sieve[p])
primes.Add(p);
return primes;
}
测试
我在笔记本电脑(核心 i7 - 2.6 Ghz)上进行测试,n = 10 亿
Sieve22Max_Basic
Sieve22Max_Enh
仅需 6 秒需要超过 10 秒才能完成
var timer = new Stopwatch();
int n = 1_000_000_000;
timer.Restart();
Console.WriteLine("==== Sieve22Max_Basic ===");
var list = Sieve22Max_Basic(n);
Console.WriteLine($"Count: {list.Count:n0}, Last: {list[list.Count - 1]:n0}, elapsed: {timer.Elapsed}");
Console.WriteLine();
timer.Restart();
Console.WriteLine("==== Sieve22Max_Enh ===");
list = Sieve22Max_Enh(n);
Console.WriteLine($"Count: {list.Count:n0}, Last: {list[list.Count - 1]:n0}, elapsed: {timer.Elapsed}");
您可以尝试 https://onlinegdb.com/tWfMuDDK0
为什么会变慢?
最佳答案
比较原始版本和改进版本的两个循环。
原文:
int inc = p == 2 ? p : 2 * p;
for (int mul = p * p; mul < n; mul += inc) {
sieve[mul] = false;
}
改进:
int inc = p == 2 ? 1 : 2;
for (long mul = p; mul * p < n; mul += inc) {
if (spd[mul] >= p) {
sieve[(int)(mul * p)] = false;
spd[mul * p] = p;
}
}
一些观察:
- 两个循环运行相同数量的迭代。
- 对于每次迭代,原始循环执行三个非常快速的操作:1) 更改
BitArray
中的值,mul += inc
并检查mul < n
. - 对于改进循环的每次迭代,我们执行更多操作:检查
spd[mul] >= p
,mul += inc
,mul * p
(在 for 循环条件下),检查mul * p < n
. - 增量
+=
并循环条件检查<
在两个循环中是相同的;检查spd[mul] >= p
并更改BitArray
中的值在他们花费的时间上具有可比性;但是额外的操作mul * p
在第二个循环中,条件是乘法——它很昂贵! - 但是还有,对于第二个循环的每次迭代,如果
spd[mul] >= p
是true
,然后我们也执行:mul * p
(再次!),转换为int
, 更改BitArray
中的值,mul * p
(第三次!),我假设再次转换为int
在spd
的索引中, 并在数组中赋值spd
.
总而言之,您的第二个改进循环的每次迭代在计算上都“更重”。这就是为什么您的改进版本速度较慢的原因。
关于c# - Eratosthenes 筛法改进后运行速度变慢,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/71152909/