如何使用 6*k +- 1 规则生成素数
How do I generate Primes Using 6*k +- 1 rule
我们知道所有大于 3 的素数都可以用以下方法生成：
6 * k + 1
6 * k - 1
但是我们从上面的公式生成的所有数字都不是质数。
For Example:
6 * 6 - 1 = 35 which is clearly divisible by 5.
为了消除这种情况，我使用了筛选法并删除了作为上述公式生成的数字因子的数字。
使用事实：
A number is said to be prime if it has no prime factors.
- 因为我们可以使用上面的公式生成所有素数。
- 如果我们可以删除上述数字的所有倍数，我们只剩下质数。
生成1000以下的素数。
ArrayList<Integer> primes = new ArrayList<>();
primes.add(2);//explicitly add
primes.add(3);//2 and 3
int n = 1000;
for (int i = 1; i <= (n / 6) ; i++) {
//get all the numbers which can be generated by the formula
int prod6k = 6 * i;
primes.add(prod6k - 1);
primes.add(prod6k + 1);
}
for (int i = 0; i < primes.size(); i++) {
int k = primes.get(i);
//remove all the factors of the numbers generated by the formula
for(int j = k * k; j <= n; j += k)//changed to k * k from 2 * k, Thanks to DTing
{
int index = primes.indexOf(j);
if(index != -1)
primes.remove(index);
}
}
System.out.println(primes);
但是，此方法确实可以正确生成素数。这以更快的方式运行，因为我们不需要检查我们在 Sieve 中检查的所有数字。
我的问题是我是否遗漏了任何边缘情况？这会好很多，但我从未见过有人使用它。我做错了什么吗？
这种方法可以更优化吗？
取 boolean[] 比取 ArrayList 快得多。
int n = 100000000;
boolean[] primes = new boolean[n + 1];
for (int i = 0; i <= n; i++)
primes[i] = false;
primes[2] = primes[3] = true;
for (int i = 1; i <= n / 6; i++) {
int prod6k = 6 * i;
primes[prod6k + 1] = true;
primes[prod6k - 1] = true;
}
for (int i = 0; i <= n; i++) {
if (primes[i]) {
int k = i;
for (int j = k * k; j <= n && j > 0; j += k) {
primes[j] = false;
}
}
}
for (int i = 0; i <= n; i++)
if (primes[i])
System.out.print(i + " ");
有几处可以优化。
对于初学者来说，ArrayList 上的 "contains" 和 "removeAll" 操作是相当昂贵的操作（前者是线性操作，后者是最坏情况下的二次操作），因此您可能不想使用 ArrayList为了这。 Hash- 或 TreeSet 对此具有更好的复杂性，几乎恒定（哈希复杂性很奇怪）并且我认为是对数的
如果你想要一个更有效的筛总计，你可以查看 Eratosthenes 的筛子，但这不是你关于 6k +-1 技巧的问题的重点。与您的解决方案相比，它的内存消耗略有增加但并不明显，但速度更快。
Can this approach be much more optimized?
答案是肯定的。
我首先要说 在一定范围内的数字子集上使用筛子是一个好主意，你的建议正是这样做的。
正在阅读有关 generating Primes 的内容：
...Furthermore, based on the sieve formalisms, some integer sequences
(sequence A240673 in OEIS) are constructed which they also could be used for generating primes in certain intervals.
这段话的意思是，你从整数的缩减列表开始的方法确实被学院采用了，但他们的技术更有效（但自然也更复杂）。
您不需要将所有可能的候选项都添加到数组中。您可以创建一个 Set 来存储所有非素数。
您也可以从 k * k 开始检查，而不是 2 * k
public void primesTo1000() {
Set<Integer> notPrimes = new HashSet<>();
ArrayList<Integer> primes = new ArrayList<>();
primes.add(2);//explicitly add
primes.add(3);//2 and 3
for (int i = 1; i < (1000 / 6); i++) {
handlePossiblePrime(6 * i - 1, primes, notPrimes);
handlePossiblePrime(6 * i + 1, primes, notPrimes);
}
System.out.println(primes);
}
public void handlePossiblePrime(
int k, List<Integer> primes, Set<Integer> notPrimes) {
if (!notPrimes.contains(k)) {
primes.add(k);
for (int j = k * k; j <= 1000; j += k) {
notPrimes.add(j);
}
}
}
未经测试的代码，检查角落
这里是 the answer referenced by @Will Ness 中建议的筛子的压缩版本。而不是 return 第 n 个 素数，这个版本 return 是 n:
的素数列表
public List<Integer> primesTo(int n) {
List<Integer> primes = new ArrayList<>();
if (n > 1) {
int limit = (n - 3) >> 1;
int[] sieve = new int[(limit >> 5) + 1];
for (int i = 0; i <= (int) (Math.sqrt(n) - 3) >> 1; i++)
if ((sieve[i >> 5] & (1 << (i & 31))) == 0) {
int p = i + i + 3;
for (int j = (p * p - 3) >> 1; j <= limit; j += p)
sieve[j >> 5] |= 1 << (j & 31);
}
primes.add(2);
for (int i = 0; i <= limit; i++)
if ((sieve[i >> 5] & (1 << (i & 31))) == 0)
primes.add(i + i + 3);
}
return primes;
}
您更新的代码中似乎有一个使用布尔数组的错误（它不是 return 所有素数）。
public static List<Integer> booleanSieve(int n) {
boolean[] primes = new boolean[n + 5];
for (int i = 0; i <= n; i++)
primes[i] = false;
primes[2] = primes[3] = true;
for (int i = 1; i <= n / 6; i++) {
int prod6k = 6 * i;
primes[prod6k + 1] = true;
primes[prod6k - 1] = true;
}
for (int i = 0; i <= n; i++) {
if (primes[i]) {
int k = i;
for (int j = k * k; j <= n && j > 0; j += k) {
primes[j] = false;
}
}
}
List<Integer> primesList = new ArrayList<>();
for (int i = 0; i <= n; i++)
if (primes[i])
primesList.add(i);
return primesList;
}
public static List<Integer> bitPacking(int n) {
List<Integer> primes = new ArrayList<>();
if (n > 1) {
int limit = (n - 3) >> 1;
int[] sieve = new int[(limit >> 5) + 1];
for (int i = 0; i <= (int) (Math.sqrt(n) - 3) >> 1; i++)
if ((sieve[i >> 5] & (1 << (i & 31))) == 0) {
int p = i + i + 3;
for (int j = (p * p - 3) >> 1; j <= limit; j += p)
sieve[j >> 5] |= 1 << (j & 31);
}
primes.add(2);
for (int i = 0; i <= limit; i++)
if ((sieve[i >> 5] & (1 << (i & 31))) == 0)
primes.add(i + i + 3);
}
return primes;
}
public static void main(String... args) {
Executor executor = Executors.newSingleThreadExecutor();
executor.execute(() -> {
for (int i = 0; i < 10; i++) {
int n = (int) Math.pow(10, i);
Stopwatch timer = Stopwatch.createUnstarted();
timer.start();
List<Integer> result = booleanSieve(n);
timer.stop();
System.out.println(result.size() + "\tBoolean: " + timer);
}
for (int i = 0; i < 10; i++) {
int n = (int) Math.pow(10, i);
Stopwatch timer = Stopwatch.createUnstarted();
timer.start();
List<Integer> result = bitPacking(n);
timer.stop();
System.out.println(result.size() + "\tBitPacking: " + timer);
}
});
}
0 Boolean: 38.51 μs
4 Boolean: 45.77 μs
25 Boolean: 31.56 μs
168 Boolean: 227.1 μs
1229 Boolean: 1.395 ms
9592 Boolean: 4.289 ms
78491 Boolean: 25.96 ms
664116 Boolean: 133.5 ms
5717622 Boolean: 3.216 s
46707218 Boolean: 32.18 s
0 BitPacking: 117.0 μs
4 BitPacking: 11.25 μs
25 BitPacking: 11.53 μs
168 BitPacking: 70.03 μs
1229 BitPacking: 471.8 μs
9592 BitPacking: 3.701 ms
78498 BitPacking: 9.651 ms
664579 BitPacking: 43.43 ms
5761455 BitPacking: 1.483 s
50847534 BitPacking: 17.71 s
您可以用轮子生成您的试验编号，交替添加 2 和 4，这消除了 6 * k +/- 1 中的乘法。
public void primesTo1000() {
Set<Integer> notPrimes = new HashSet<>();
ArrayList<Integer> primes = new ArrayList<>();
primes.add(2); //explicitly add
primes.add(3); //2 and 3
int step = 2;
int num = 5 // 2 and 3 already handled.
while (num < 1000) {
handlePossiblePrime(num, primes, notPrimes);
num += step; // Step to next number.
step = 6 - step; // Step by 2, 4 alternately.
}
System.out.println(primes);
}
5 是您的条件生成的第一个数字。我们来看看最多生成25的数字：
5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
现在，让我们看看这些相同的数字，当我们使用 Eratosthenes 算法时：
5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
删除 2 后：
5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
删除 3 后：
5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
这和第一套一样！请注意，它们都包括 25，这不是质数。如果我们考虑一下，这是一个显而易见的结果。考虑任意一组 6 个连续数字：
6k - 3, 6k - 2, 6k - 1, 6k, 6k + 1, 6k + 2
如果我们分解一点，我们得到：
3*(2k - 1), 2*(3k - 1), 6k - 1, 6*(k), 6k + 1, 2*(3k + 1)
任意一组6个连续数，其中3个能被2整除，2个能被3整除。这些正是我们到目前为止删除的数字！因此：
你的算法只使用 6k - 1 和 6k + 1 与 Erathosthenes 筛法的前两轮完全相同。
与 Sieve 相比，这也是一个相当不错的速度改进，因为我们不必为了删除它们而添加所有这些额外元素。这解释了为什么您的算法有效以及为什么它不会遗漏任何情况；因为它和筛子完全一样。
无论如何，我同意一旦你生成素数，你的 boolean 方法是 迄今为止最快的。 我已经使用你的 ArrayList 方式，你的 boolean[] 方式，以及我自己使用 LinkedList 和 iterator.remove() 的方式（因为在 LinkedList 中移除速度很快。这是我的测试工具的代码。请注意，我 运行 测试了 12 次以确保 JVM 已预热，并且我打印列表的大小并更改 n 的大小以试图防止太多 branch prediction优化。您还可以通过在初始种子中使用 += 6 而不是 prod6k:
来提高所有三种方法的速度
import java.util.*;
public class PrimeGenerator {
public static List<Integer> generatePrimesArrayList(int n) {
List<Integer> primes = new ArrayList<>(getApproximateSize(n));
primes.add(2);// explicitly add
primes.add(3);// 2 and 3
for (int i = 6; i <= n; i+=6) {
// get all the numbers which can be generated by the formula
primes.add(i - 1);
primes.add(i + 1);
}
for (int i = 0; i < primes.size(); i++) {
int k = primes.get(i);
// remove all the factors of the numbers generated by the formula
for (int j = k * k; j <= n; j += k)// changed to k * k from 2 * k, Thanks
// to DTing
{
int index = primes.indexOf(j);
if (index != -1)
primes.remove(index);
}
}
return primes;
}
public static List<Integer> generatePrimesBoolean(int n) {
boolean[] primes = new boolean[n + 5];
for (int i = 0; i <= n; i++)
primes[i] = false;
primes[2] = primes[3] = true;
for (int i = 6; i <= n; i+=6) {
primes[i + 1] = true;
primes[i - 1] = true;
}
for (int i = 0; i <= n; i++) {
if (primes[i]) {
int k = i;
for (int j = k * k; j <= n && j > 0; j += k) {
primes[j] = false;
}
}
}
int approximateSize = getApproximateSize(n);
List<Integer> primesList = new ArrayList<>(approximateSize);
for (int i = 0; i <= n; i++)
if (primes[i])
primesList.add(i);
return primesList;
}
private static int getApproximateSize(int n) {
// Prime Number Theorem. Round up
int approximateSize = (int) Math.ceil(((double) n) / (Math.log(n)));
return approximateSize;
}
public static List<Integer> generatePrimesLinkedList(int n) {
List<Integer> primes = new LinkedList<>();
primes.add(2);// explicitly add
primes.add(3);// 2 and 3
for (int i = 6; i <= n; i+=6) {
// get all the numbers which can be generated by the formula
primes.add(i - 1);
primes.add(i + 1);
}
for (int i = 0; i < primes.size(); i++) {
int k = primes.get(i);
for (Iterator<Integer> iterator = primes.iterator(); iterator.hasNext();) {
int primeCandidate = iterator.next();
if (primeCandidate == k)
continue; // Always skip yourself
if (primeCandidate == (primeCandidate / k) * k)
iterator.remove();
}
}
return primes;
}
public static void main(String... args) {
int initial = 4000;
for (int i = 0; i < 12; i++) {
int n = initial * i;
long start = System.currentTimeMillis();
List<Integer> result = generatePrimesArrayList(n);
long seconds = System.currentTimeMillis() - start;
System.out.println(result.size() + "\tArrayList Seconds: " + seconds);
start = System.currentTimeMillis();
result = generatePrimesBoolean(n);
seconds = System.currentTimeMillis() - start;
System.out.println(result.size() + "\tBoolean Seconds: " + seconds);
start = System.currentTimeMillis();
result = generatePrimesLinkedList(n);
seconds = System.currentTimeMillis() - start;
System.out.println(result.size() + "\tLinkedList Seconds: " + seconds);
}
}
}
以及最近几次试验的结果：
3432 ArrayList Seconds: 430
3432 Boolean Seconds: 0
3432 LinkedList Seconds: 90
3825 ArrayList Seconds: 538
3824 Boolean Seconds: 0
3824 LinkedList Seconds: 81
4203 ArrayList Seconds: 681
4203 Boolean Seconds: 0
4203 LinkedList Seconds: 100
4579 ArrayList Seconds: 840
4579 Boolean Seconds: 0
4579 LinkedList Seconds: 111
可能最适合埃拉托色尼筛法的标准数据结构是 BitSet。这是我的解决方案：
static BitSet genPrimes(int n) {
BitSet primes = new BitSet(n);
primes.set(2); // add 2 explicitly
primes.set(3); // add 3 explicitly
for (int i = 6; i <= n ; i += 6) { // step by 6 instead of multiplication
primes.set(i - 1);
primes.set(i + 1);
}
int max = (int) Math.sqrt(n); // don't need to filter multiples of primes bigger than max
// this for loop enumerates all set bits starting from 5 till the max
// sieving 2 and 3 is meaningless: n*6+1 and n*6-1 are never divisible by 2 or 3
for (int i = primes.nextSetBit(5); i >= 0 && i <= max; i = primes.nextSetBit(i+1)) {
// The actual sieve algorithm like in your code
for(int j = i * i; j <= n; j += i)
primes.clear(j);
}
return primes;
}
用法：
BitSet primes = genPrimes(1000); // generate primes up to 1000
System.out.println(primes.cardinality()); // print number of primes
// print all primes like {2, 3, 5, ...}
System.out.println(primes);
// print all primes one per line
for(int prime = primes.nextSetBit(0); prime >= 0; prime = primes.nextSetBit(prime+1))
System.out.println(prime);
// print all primes one per line using java 8:
primes.stream().forEach(System.out::println);
基于布尔的版本对于较小的 n 值可能工作得更快，但是如果您需要，例如，一百万个素数，BitSet 将在数倍内胜过它并且确实有效正确。这是蹩脚的基准：
public static void main(String... args) {
long start = System.nanoTime();
BitSet res = genPrimes(10000000);
long diff = System.nanoTime() - start;
System.out.println(res.cardinality() + "\tBitSet Seconds: " + diff / 1e9);
start = System.nanoTime();
List<Integer> result = generatePrimesBoolean(10000000); // from durron597 answer
diff = System.nanoTime() - start;
System.out.println(result.size() + "\tBoolean Seconds: " + diff / 1e9);
}
输出：
664579 BitSet Seconds: 0.065987717
664116 Boolean Seconds: 0.167620323
664579 是 the correct number 个小于 10000000 的素数。
下面的方法展示了如何使用 6k+/-1 逻辑查找素数
这是在 python 3.6
中编写的
def isPrime(n):
if(n<=1):
return 0
elif(n<4): #2 , 3 are prime
return 1
elif(n%2==0): #already excluded no.2 ,so any no. div. by 2 cant be prime
return 0
elif(n<9): #5, 7 are prime and 6,8 are excl. in the above step
return 1
elif(n%3==0):
return 1
f=5 #Till now we have checked the div. of n with 2,3 which means with 4,6,8 also now that is why f=5
r=int(n**.5) #rounding of root n, i.e: floor(sqrt(n)) r*r<=n
while(f<=r):
if(n%f==0): #checking if n has any primefactor lessthan sqrt(n), refer LINE 1
return 0
if(n%(f+2)==0): #remember her we are not incrementing f, see the 6k+1 rule to understand this while loop steps ,you will see that most values of f are prime
return 0
f=f+6
return 1
def prime_nos():
counter=2 #we know 2,3 are prime
print(2)
print(3) #we know 2,3 are prime
i=1
s=5 #sum 2+3
t=0
n=int(input("Enter the upper limit( should be > 3: "))
n=(n-1)//6 #finding max. limit(n=6*i+1) upto which I(here n on left hand side) should run
while(i<n):#2*(10**6)):
if (isPrime(6*i-1)):
counter=counter+1
print(6*i-1) #prime no
if(isPrime(6*i+1)):
counter=counter+1
print(6*i+1) #prime no
i+=1
prime_nos() #fn. call
你的素数公式在数学上不正确。取 96 它可整除为 6 96/6=16 所以按照这个逻辑 97 和 95 必须是素数如果平方根通过但 95 的平方根是 9.7467...（通过）所以它是“素数”。但是 95 在 c#
中显然可以被 5 快速算法整除
int n=100000000;
bool [] falseprimes = new bool[n + 2];
int ed=n/6;
ed = ed * 6;
int md = (int)Math.Sqrt((double)ed);
for (int i = ed; i > md; i-=6)
{
falseprimes[i + 1] = true;
falseprimes[i - 1] = true;
}
md = md / 6;
md = md * 5;
for (int i = md; i > 5; i -= 6)
{
falseprimes[i + 1] = true;
falseprimes[i - 1] = true;
falseprimes[(i + 1)* (i + 1)] = false;
falseprimes[(i-1) * (i-1)] = false;
}
falseprimes[2] = true;
falseprimes[3] = true;
要使用 6 * k + - 1 规则生成质数，请使用此算法：
int n = 100000000;
int j,jmax=n/6;
boolean[] primes5m6 = new boolean[jmax+1];
boolean[] primes1m6 = new boolean[jmax+1];
for (int i = 1; i <= (int)((Math.sqrt(n)+1)/6)+1; i++){
if (!primes5m6[i]){
for (j = 6*i*i; j <= jmax; j+=6*i-1){
primes5m6[j]=true;
primes1m6[j-2*i]=true;
}
for (; j <= jmax+2*i; j+=6*i-1)
primes1m6[j-2*i]=true;
}
if (!primes1m6[i]){
for (j = 6*i*i; j <= jmax-2*i; j+=6*i+1){
primes5m6[j]=true;
primes1m6[j+2*i]=true;
}
for (; j <= jmax; j+=6*i+1)
primes5m6[j]=true;
}
}
System.out.print(2 + " ");
System.out.print(3 + " ");
for (int i = 1; i <= jmax; i++){
if (!primes5m6[i])
System.out.print((6*i-1) + " ");
if (!primes1m6[i])
System.out.print((6*i+1) + " ");
}
我们知道所有大于 3 的素数都可以用以下方法生成：
6 * k + 1
6 * k - 1
但是我们从上面的公式生成的所有数字都不是质数。
For Example:
6 * 6 - 1 = 35 which is clearly divisible by 5.
为了消除这种情况，我使用了筛选法并删除了作为上述公式生成的数字因子的数字。
使用事实：
A number is said to be prime if it has no prime factors.
- 因为我们可以使用上面的公式生成所有素数。
- 如果我们可以删除上述数字的所有倍数，我们只剩下质数。
生成1000以下的素数。
ArrayList<Integer> primes = new ArrayList<>();
primes.add(2);//explicitly add
primes.add(3);//2 and 3
int n = 1000;
for (int i = 1; i <= (n / 6) ; i++) {
//get all the numbers which can be generated by the formula
int prod6k = 6 * i;
primes.add(prod6k - 1);
primes.add(prod6k + 1);
}
for (int i = 0; i < primes.size(); i++) {
int k = primes.get(i);
//remove all the factors of the numbers generated by the formula
for(int j = k * k; j <= n; j += k)//changed to k * k from 2 * k, Thanks to DTing
{
int index = primes.indexOf(j);
if(index != -1)
primes.remove(index);
}
}
System.out.println(primes);
但是，此方法确实可以正确生成素数。这以更快的方式运行，因为我们不需要检查我们在 Sieve 中检查的所有数字。
我的问题是我是否遗漏了任何边缘情况？这会好很多，但我从未见过有人使用它。我做错了什么吗？
这种方法可以更优化吗？
取 boolean[] 比取 ArrayList 快得多。
int n = 100000000;
boolean[] primes = new boolean[n + 1];
for (int i = 0; i <= n; i++)
primes[i] = false;
primes[2] = primes[3] = true;
for (int i = 1; i <= n / 6; i++) {
int prod6k = 6 * i;
primes[prod6k + 1] = true;
primes[prod6k - 1] = true;
}
for (int i = 0; i <= n; i++) {
if (primes[i]) {
int k = i;
for (int j = k * k; j <= n && j > 0; j += k) {
primes[j] = false;
}
}
}
for (int i = 0; i <= n; i++)
if (primes[i])
System.out.print(i + " ");
有几处可以优化。
对于初学者来说，ArrayList 上的 "contains" 和 "removeAll" 操作是相当昂贵的操作（前者是线性操作，后者是最坏情况下的二次操作），因此您可能不想使用 ArrayList为了这。 Hash- 或 TreeSet 对此具有更好的复杂性，几乎恒定（哈希复杂性很奇怪）并且我认为是对数的
如果你想要一个更有效的筛总计，你可以查看 Eratosthenes 的筛子，但这不是你关于 6k +-1 技巧的问题的重点。与您的解决方案相比，它的内存消耗略有增加但并不明显，但速度更快。
Can this approach be much more optimized?
答案是肯定的。
我首先要说 在一定范围内的数字子集上使用筛子是一个好主意，你的建议正是这样做的。
正在阅读有关 generating Primes 的内容：
...Furthermore, based on the sieve formalisms, some integer sequences (sequence A240673 in OEIS) are constructed which they also could be used for generating primes in certain intervals.
这段话的意思是，你从整数的缩减列表开始的方法确实被学院采用了，但他们的技术更有效（但自然也更复杂）。
您不需要将所有可能的候选项都添加到数组中。您可以创建一个 Set 来存储所有非素数。
您也可以从 k * k 开始检查，而不是 2 * k
public void primesTo1000() {
Set<Integer> notPrimes = new HashSet<>();
ArrayList<Integer> primes = new ArrayList<>();
primes.add(2);//explicitly add
primes.add(3);//2 and 3
for (int i = 1; i < (1000 / 6); i++) {
handlePossiblePrime(6 * i - 1, primes, notPrimes);
handlePossiblePrime(6 * i + 1, primes, notPrimes);
}
System.out.println(primes);
}
public void handlePossiblePrime(
int k, List<Integer> primes, Set<Integer> notPrimes) {
if (!notPrimes.contains(k)) {
primes.add(k);
for (int j = k * k; j <= 1000; j += k) {
notPrimes.add(j);
}
}
}
未经测试的代码，检查角落
这里是 the answer referenced by @Will Ness 中建议的筛子的压缩版本。而不是 return 第 n 个 素数，这个版本 return 是 n:
的素数列表public List<Integer> primesTo(int n) {
List<Integer> primes = new ArrayList<>();
if (n > 1) {
int limit = (n - 3) >> 1;
int[] sieve = new int[(limit >> 5) + 1];
for (int i = 0; i <= (int) (Math.sqrt(n) - 3) >> 1; i++)
if ((sieve[i >> 5] & (1 << (i & 31))) == 0) {
int p = i + i + 3;
for (int j = (p * p - 3) >> 1; j <= limit; j += p)
sieve[j >> 5] |= 1 << (j & 31);
}
primes.add(2);
for (int i = 0; i <= limit; i++)
if ((sieve[i >> 5] & (1 << (i & 31))) == 0)
primes.add(i + i + 3);
}
return primes;
}
您更新的代码中似乎有一个使用布尔数组的错误（它不是 return 所有素数）。
public static List<Integer> booleanSieve(int n) {
boolean[] primes = new boolean[n + 5];
for (int i = 0; i <= n; i++)
primes[i] = false;
primes[2] = primes[3] = true;
for (int i = 1; i <= n / 6; i++) {
int prod6k = 6 * i;
primes[prod6k + 1] = true;
primes[prod6k - 1] = true;
}
for (int i = 0; i <= n; i++) {
if (primes[i]) {
int k = i;
for (int j = k * k; j <= n && j > 0; j += k) {
primes[j] = false;
}
}
}
List<Integer> primesList = new ArrayList<>();
for (int i = 0; i <= n; i++)
if (primes[i])
primesList.add(i);
return primesList;
}
public static List<Integer> bitPacking(int n) {
List<Integer> primes = new ArrayList<>();
if (n > 1) {
int limit = (n - 3) >> 1;
int[] sieve = new int[(limit >> 5) + 1];
for (int i = 0; i <= (int) (Math.sqrt(n) - 3) >> 1; i++)
if ((sieve[i >> 5] & (1 << (i & 31))) == 0) {
int p = i + i + 3;
for (int j = (p * p - 3) >> 1; j <= limit; j += p)
sieve[j >> 5] |= 1 << (j & 31);
}
primes.add(2);
for (int i = 0; i <= limit; i++)
if ((sieve[i >> 5] & (1 << (i & 31))) == 0)
primes.add(i + i + 3);
}
return primes;
}
public static void main(String... args) {
Executor executor = Executors.newSingleThreadExecutor();
executor.execute(() -> {
for (int i = 0; i < 10; i++) {
int n = (int) Math.pow(10, i);
Stopwatch timer = Stopwatch.createUnstarted();
timer.start();
List<Integer> result = booleanSieve(n);
timer.stop();
System.out.println(result.size() + "\tBoolean: " + timer);
}
for (int i = 0; i < 10; i++) {
int n = (int) Math.pow(10, i);
Stopwatch timer = Stopwatch.createUnstarted();
timer.start();
List<Integer> result = bitPacking(n);
timer.stop();
System.out.println(result.size() + "\tBitPacking: " + timer);
}
});
}
0 Boolean: 38.51 μs
4 Boolean: 45.77 μs
25 Boolean: 31.56 μs
168 Boolean: 227.1 μs
1229 Boolean: 1.395 ms
9592 Boolean: 4.289 ms
78491 Boolean: 25.96 ms
664116 Boolean: 133.5 ms
5717622 Boolean: 3.216 s
46707218 Boolean: 32.18 s
0 BitPacking: 117.0 μs
4 BitPacking: 11.25 μs
25 BitPacking: 11.53 μs
168 BitPacking: 70.03 μs
1229 BitPacking: 471.8 μs
9592 BitPacking: 3.701 ms
78498 BitPacking: 9.651 ms
664579 BitPacking: 43.43 ms
5761455 BitPacking: 1.483 s
50847534 BitPacking: 17.71 s
您可以用轮子生成您的试验编号，交替添加 2 和 4，这消除了 6 * k +/- 1 中的乘法。
public void primesTo1000() {
Set<Integer> notPrimes = new HashSet<>();
ArrayList<Integer> primes = new ArrayList<>();
primes.add(2); //explicitly add
primes.add(3); //2 and 3
int step = 2;
int num = 5 // 2 and 3 already handled.
while (num < 1000) {
handlePossiblePrime(num, primes, notPrimes);
num += step; // Step to next number.
step = 6 - step; // Step by 2, 4 alternately.
}
System.out.println(primes);
}
5 是您的条件生成的第一个数字。我们来看看最多生成25的数字：
5,
6, 7,8,9,10, 11,12, 13,14,15,16, 17,18, 19,20,21,22, 23,24, 25
现在，让我们看看这些相同的数字，当我们使用 Eratosthenes 算法时：
5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
删除 2 后：
5,
6, 7,8, 9,10, 11,12, 13,14, 15,16, 17,18, 19,20, 21,22, 23,24, 25
删除 3 后：
5,
6, 7,8,9,10, 11,12, 13,14,15,16, 17,18, 19,20,21,22, 23,24, 25
这和第一套一样！请注意，它们都包括 25，这不是质数。如果我们考虑一下，这是一个显而易见的结果。考虑任意一组 6 个连续数字：
6k - 3, 6k - 2, 6k - 1, 6k, 6k + 1, 6k + 2
如果我们分解一点，我们得到：
3*(2k - 1), 2*(3k - 1), 6k - 1, 6*(k), 6k + 1, 2*(3k + 1)
任意一组6个连续数，其中3个能被2整除，2个能被3整除。这些正是我们到目前为止删除的数字！因此：
你的算法只使用 6k - 1 和 6k + 1 与 Erathosthenes 筛法的前两轮完全相同。
与 Sieve 相比，这也是一个相当不错的速度改进，因为我们不必为了删除它们而添加所有这些额外元素。这解释了为什么您的算法有效以及为什么它不会遗漏任何情况；因为它和筛子完全一样。
无论如何，我同意一旦你生成素数，你的 boolean 方法是 迄今为止最快的。 我已经使用你的 ArrayList 方式，你的 boolean[] 方式，以及我自己使用 LinkedList 和 iterator.remove() 的方式（因为在 LinkedList 中移除速度很快。这是我的测试工具的代码。请注意，我 运行 测试了 12 次以确保 JVM 已预热，并且我打印列表的大小并更改 n 的大小以试图防止太多 branch prediction优化。您还可以通过在初始种子中使用 += 6 而不是 prod6k:
import java.util.*;
public class PrimeGenerator {
public static List<Integer> generatePrimesArrayList(int n) {
List<Integer> primes = new ArrayList<>(getApproximateSize(n));
primes.add(2);// explicitly add
primes.add(3);// 2 and 3
for (int i = 6; i <= n; i+=6) {
// get all the numbers which can be generated by the formula
primes.add(i - 1);
primes.add(i + 1);
}
for (int i = 0; i < primes.size(); i++) {
int k = primes.get(i);
// remove all the factors of the numbers generated by the formula
for (int j = k * k; j <= n; j += k)// changed to k * k from 2 * k, Thanks
// to DTing
{
int index = primes.indexOf(j);
if (index != -1)
primes.remove(index);
}
}
return primes;
}
public static List<Integer> generatePrimesBoolean(int n) {
boolean[] primes = new boolean[n + 5];
for (int i = 0; i <= n; i++)
primes[i] = false;
primes[2] = primes[3] = true;
for (int i = 6; i <= n; i+=6) {
primes[i + 1] = true;
primes[i - 1] = true;
}
for (int i = 0; i <= n; i++) {
if (primes[i]) {
int k = i;
for (int j = k * k; j <= n && j > 0; j += k) {
primes[j] = false;
}
}
}
int approximateSize = getApproximateSize(n);
List<Integer> primesList = new ArrayList<>(approximateSize);
for (int i = 0; i <= n; i++)
if (primes[i])
primesList.add(i);
return primesList;
}
private static int getApproximateSize(int n) {
// Prime Number Theorem. Round up
int approximateSize = (int) Math.ceil(((double) n) / (Math.log(n)));
return approximateSize;
}
public static List<Integer> generatePrimesLinkedList(int n) {
List<Integer> primes = new LinkedList<>();
primes.add(2);// explicitly add
primes.add(3);// 2 and 3
for (int i = 6; i <= n; i+=6) {
// get all the numbers which can be generated by the formula
primes.add(i - 1);
primes.add(i + 1);
}
for (int i = 0; i < primes.size(); i++) {
int k = primes.get(i);
for (Iterator<Integer> iterator = primes.iterator(); iterator.hasNext();) {
int primeCandidate = iterator.next();
if (primeCandidate == k)
continue; // Always skip yourself
if (primeCandidate == (primeCandidate / k) * k)
iterator.remove();
}
}
return primes;
}
public static void main(String... args) {
int initial = 4000;
for (int i = 0; i < 12; i++) {
int n = initial * i;
long start = System.currentTimeMillis();
List<Integer> result = generatePrimesArrayList(n);
long seconds = System.currentTimeMillis() - start;
System.out.println(result.size() + "\tArrayList Seconds: " + seconds);
start = System.currentTimeMillis();
result = generatePrimesBoolean(n);
seconds = System.currentTimeMillis() - start;
System.out.println(result.size() + "\tBoolean Seconds: " + seconds);
start = System.currentTimeMillis();
result = generatePrimesLinkedList(n);
seconds = System.currentTimeMillis() - start;
System.out.println(result.size() + "\tLinkedList Seconds: " + seconds);
}
}
}
以及最近几次试验的结果：
3432 ArrayList Seconds: 430
3432 Boolean Seconds: 0
3432 LinkedList Seconds: 90
3825 ArrayList Seconds: 538
3824 Boolean Seconds: 0
3824 LinkedList Seconds: 81
4203 ArrayList Seconds: 681
4203 Boolean Seconds: 0
4203 LinkedList Seconds: 100
4579 ArrayList Seconds: 840
4579 Boolean Seconds: 0
4579 LinkedList Seconds: 111
可能最适合埃拉托色尼筛法的标准数据结构是 BitSet。这是我的解决方案：
static BitSet genPrimes(int n) {
BitSet primes = new BitSet(n);
primes.set(2); // add 2 explicitly
primes.set(3); // add 3 explicitly
for (int i = 6; i <= n ; i += 6) { // step by 6 instead of multiplication
primes.set(i - 1);
primes.set(i + 1);
}
int max = (int) Math.sqrt(n); // don't need to filter multiples of primes bigger than max
// this for loop enumerates all set bits starting from 5 till the max
// sieving 2 and 3 is meaningless: n*6+1 and n*6-1 are never divisible by 2 or 3
for (int i = primes.nextSetBit(5); i >= 0 && i <= max; i = primes.nextSetBit(i+1)) {
// The actual sieve algorithm like in your code
for(int j = i * i; j <= n; j += i)
primes.clear(j);
}
return primes;
}
用法：
BitSet primes = genPrimes(1000); // generate primes up to 1000
System.out.println(primes.cardinality()); // print number of primes
// print all primes like {2, 3, 5, ...}
System.out.println(primes);
// print all primes one per line
for(int prime = primes.nextSetBit(0); prime >= 0; prime = primes.nextSetBit(prime+1))
System.out.println(prime);
// print all primes one per line using java 8:
primes.stream().forEach(System.out::println);
基于布尔的版本对于较小的 n 值可能工作得更快，但是如果您需要，例如，一百万个素数，BitSet 将在数倍内胜过它并且确实有效正确。这是蹩脚的基准：
public static void main(String... args) {
long start = System.nanoTime();
BitSet res = genPrimes(10000000);
long diff = System.nanoTime() - start;
System.out.println(res.cardinality() + "\tBitSet Seconds: " + diff / 1e9);
start = System.nanoTime();
List<Integer> result = generatePrimesBoolean(10000000); // from durron597 answer
diff = System.nanoTime() - start;
System.out.println(result.size() + "\tBoolean Seconds: " + diff / 1e9);
}
输出：
664579 BitSet Seconds: 0.065987717
664116 Boolean Seconds: 0.167620323
664579 是 the correct number 个小于 10000000 的素数。
下面的方法展示了如何使用 6k+/-1 逻辑查找素数
这是在 python 3.6
中编写的def isPrime(n):
if(n<=1):
return 0
elif(n<4): #2 , 3 are prime
return 1
elif(n%2==0): #already excluded no.2 ,so any no. div. by 2 cant be prime
return 0
elif(n<9): #5, 7 are prime and 6,8 are excl. in the above step
return 1
elif(n%3==0):
return 1
f=5 #Till now we have checked the div. of n with 2,3 which means with 4,6,8 also now that is why f=5
r=int(n**.5) #rounding of root n, i.e: floor(sqrt(n)) r*r<=n
while(f<=r):
if(n%f==0): #checking if n has any primefactor lessthan sqrt(n), refer LINE 1
return 0
if(n%(f+2)==0): #remember her we are not incrementing f, see the 6k+1 rule to understand this while loop steps ,you will see that most values of f are prime
return 0
f=f+6
return 1
def prime_nos():
counter=2 #we know 2,3 are prime
print(2)
print(3) #we know 2,3 are prime
i=1
s=5 #sum 2+3
t=0
n=int(input("Enter the upper limit( should be > 3: "))
n=(n-1)//6 #finding max. limit(n=6*i+1) upto which I(here n on left hand side) should run
while(i<n):#2*(10**6)):
if (isPrime(6*i-1)):
counter=counter+1
print(6*i-1) #prime no
if(isPrime(6*i+1)):
counter=counter+1
print(6*i+1) #prime no
i+=1
prime_nos() #fn. call
你的素数公式在数学上不正确。取 96 它可整除为 6 96/6=16 所以按照这个逻辑 97 和 95 必须是素数如果平方根通过但 95 的平方根是 9.7467...（通过）所以它是“素数”。但是 95 在 c#
中显然可以被 5 快速算法整除 int n=100000000;
bool [] falseprimes = new bool[n + 2];
int ed=n/6;
ed = ed * 6;
int md = (int)Math.Sqrt((double)ed);
for (int i = ed; i > md; i-=6)
{
falseprimes[i + 1] = true;
falseprimes[i - 1] = true;
}
md = md / 6;
md = md * 5;
for (int i = md; i > 5; i -= 6)
{
falseprimes[i + 1] = true;
falseprimes[i - 1] = true;
falseprimes[(i + 1)* (i + 1)] = false;
falseprimes[(i-1) * (i-1)] = false;
}
falseprimes[2] = true;
falseprimes[3] = true;
要使用 6 * k + - 1 规则生成质数，请使用此算法：
int n = 100000000;
int j,jmax=n/6;
boolean[] primes5m6 = new boolean[jmax+1];
boolean[] primes1m6 = new boolean[jmax+1];
for (int i = 1; i <= (int)((Math.sqrt(n)+1)/6)+1; i++){
if (!primes5m6[i]){
for (j = 6*i*i; j <= jmax; j+=6*i-1){
primes5m6[j]=true;
primes1m6[j-2*i]=true;
}
for (; j <= jmax+2*i; j+=6*i-1)
primes1m6[j-2*i]=true;
}
if (!primes1m6[i]){
for (j = 6*i*i; j <= jmax-2*i; j+=6*i+1){
primes5m6[j]=true;
primes1m6[j+2*i]=true;
}
for (; j <= jmax; j+=6*i+1)
primes5m6[j]=true;
}
}
System.out.print(2 + " ");
System.out.print(3 + " ");
for (int i = 1; i <= jmax; i++){
if (!primes5m6[i])
System.out.print((6*i-1) + " ");
if (!primes1m6[i])
System.out.print((6*i+1) + " ");
}