线性筛分算法

Question

是否有一个简单的 pari/gp 程序可以筛选 k*n+c 形式的数字（其中 n 和 c 固定）直到某个素数 p 并且 k 被限制在某个范围内（a.k.a.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 整除。然后测试下一个素数等等。这样做直到达到筛子的极限 return，或打印候选人名单。感谢您的帮助！

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])

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

线性筛分算法

Linear sieving algorithm

sieve

pari