sieve - 线性筛分算法

Question

是否有一个简单的 pari/gp 程序可以筛选 k*n+c 形式的数字（其中 n 和 c 固定）直到某个素数 p 并且 k 被限制在某个范围内（又名 for(k=1,10000 ,)?

伪代码：

n = (some number);
c = (some number);
T=[all k values];
forprime(p=2,100000000, for(i=1,#List if((T[i]*n+c)%p==0, (remove the number T[i] from the list)

换句话说，从整数列表 T 开始测试素数范围 p 中的第一个素数，并从列表 T 中删除整数 k，使得 k*n+c 可以被 p 整除。然后测试下一个素数，依此类推。这样做直到达到筛子返回的极限，或打印候选者列表。感谢帮助！

Answer 1

您提供的伪代码似乎是合理的。与其从列表中删除，不如仅复制它可能更容易且更有效。使用该功能select保留那些应该保留而不是删除的元素。

一些实际代码：

sieve(n,c,plimit,L)={forprime(p=2, plimit, L=select(t->(t*n+c)%p, L); if(!#L, break)); L}
sieve(8, 3, 70000, [1..10000])

如果列表为空，我还在循环中添加了一个检查以退出循环。在我尝试过的情况下，这似乎发生了。