Eratosthenes的素数比同时更快？

Question

我目前正在编写一个程序，该程序首先由Eratosthenes筛选顺序生成素数，然后同时生成素数。该算法的并发版本应该比顺序版本更快，但在我的情况下，并发版本约为。慢10倍。我想知道在顺序解决方案中与主线程相比，我将更多工作放在我的线程上。这是我的程序（准备阅读一下！）：

Primes.java：

public abstract class Primes {

    byte[] bitArr;

    int maxNum;

    final int[] BITMASK = { 1, 2, 4, 8, 16, 32, 64 };

    final int[] BITMASK2 = { 255 - 1, 255 - 2, 255 - 4, 255 - 8, 

                             255 - 16, 255 - 32, 255 - 64 };

    void setAllPrime() {

        for (int i = 0; i < bitArr.length; i++) {

            bitArr[i] = (byte) 127;

        }

    }

    void crossOut(int i) {

        bitArr[i/14] = (byte) (bitArr[i/14] - BITMASK[((i/2)%7)]);

    }

    boolean isPrime(int i) {

        if(i == 2){

            return true;

        }

        if((i%2) == 0){

            return false;

        }

        return (bitArr[i/14] & BITMASK[(i%14)>>1]) != 0;

    }

    int nextPrime(int i) {

        int k;

        if ((i%2) == 0){

            k =i+1;

        }

        else {

            k = i+2;

        }

        while (!isPrime(k) && k < maxNum){

            k+=2;

        }

        return k;

    }

    void printAllPrimes() {

        for (int i = 2; i <= maxNum; i++){

            if (isPrime(i)){

                System.out.println("Prime: " + i);

            }

        }

    }

}

PrimesSeq.java：

import java.util.ArrayList;

public class PrimesSeq extends Primes{

    PrimesSeq(int maxNum) {

        this.maxNum = maxNum;

        bitArr = new byte[(maxNum / 14) + 1];

        setAllPrime();

        generatePrimesByEratosthenes();

    }

如果有人能告诉我并发程序的瓶颈在哪里，我会非常高兴。提前致谢！

Answer 1

我不是JAVA编码器所以我坚持使用C ++。这也不是你的问题的直接答案（对不起，但我不能调试JAVA）把这作为一些指针去哪个方向或检查...Eratosthenes的筛子并行化是可能的，但速度增益不够大。相反，我使用更多的筛选标签，每个筛选器都有自己的子分区，每个表大小是所有子除数的共同乘法。这样你只需要启动一次表，然后检查它们O(1)并行在检查了所有的筛子后，我会使用线程对所有未使用的除数进行明显的除法测试memoize的如果你有所有找到的素数的有效表，那么除以素数并添加所有找到的素数我正在使用非并行素数搜索，这对我来说足够快......您可以根据并行代码进行调整......[Edit1]更新了代码//---------------------------------------------------------------------------int bits(DWORD p)&nbsp; &nbsp; {&nbsp; &nbsp; DWORD m=0x80000000; int b=32;&nbsp; &nbsp; for (;m;m>>=1,b--)&nbsp; &nbsp; &nbsp;if (p>=m) break;&nbsp; &nbsp; return b;&nbsp; &nbsp; }//---------------------------------------------------------------------------DWORD sqrt(const DWORD &x)&nbsp; &nbsp; {&nbsp; &nbsp; DWORD m,a;&nbsp; &nbsp; m=(bits(x)>>1);&nbsp; &nbsp; if (m) m=1<<m; else m=1;&nbsp; &nbsp; for (a=0;m;m>>=1) { a|=m; if (a*a>x) a^=m; }&nbsp; &nbsp; return a;&nbsp; &nbsp; }//---------------------------------------------------------------------------List<int> primes_i32;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// list of precomputed primesconst int primes_map_sz=4106301;&nbsp; &nbsp; &nbsp; &nbsp; // max size of map for speedup search for primes max(LCM(used primes per bit)) (not >>1 because SOE is periodic at double LCM size and only odd values are stored 2/2=1)const int primes_map_N[8]={ 4106301,3905765,3585337,4026077,3386981,3460469,3340219,3974653 };const int primes_map_i0=33;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// first index of prime not used in maskconst int primes_map_p0=137;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // biggest prime used in maskBYTE primes_map[primes_map_sz];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// factors map for first i0-1 primesbool primes_i32_alloc=false;int isprime(int p)&nbsp; &nbsp; {&nbsp; &nbsp; int i,j,a,b,an,im[8]; BYTE u;&nbsp; &nbsp; an=0;&nbsp; &nbsp; if (!primes_i32.num)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // init primes vars&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.allocate(1024*1024);&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add(&nbsp; 2); for (i=1;i<primes_map_sz;i++) primes_map[i]=255; primes_map[0]=254;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add(&nbsp; 3); for (u=255-&nbsp; 1,j=&nbsp; 3,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add(&nbsp; 5); for (u=255-&nbsp; 2,j=&nbsp; 5,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add(&nbsp; 7); for (u=255-&nbsp; 4,j=&nbsp; 7,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 11); for (u=255-&nbsp; 8,j= 11,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 13); for (u=255- 16,j= 13,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 17); for (u=255- 32,j= 17,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 19); for (u=255- 64,j= 19,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 23); for (u=255-128,j= 23,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 29); for (u=255-&nbsp; 1,j=137,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 31); for (u=255-&nbsp; 2,j=131,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 37); for (u=255-&nbsp; 4,j=127,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 41); for (u=255-&nbsp; 8,j=113,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 43); for (u=255- 16,j= 83,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 47); for (u=255- 32,j= 61,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 53); for (u=255- 64,j=107,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 59); for (u=255-128,j=101,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 61); for (u=255-&nbsp; 1,j=103,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 67); for (u=255-&nbsp; 2,j= 67,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 71); for (u=255-&nbsp; 4,j= 37,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 73); for (u=255-&nbsp; 8,j= 41,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 79); for (u=255- 16,j= 43,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 83); for (u=255- 32,j= 47,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 89); for (u=255- 64,j= 53,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add( 97); for (u=255-128,j= 59,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add(101); for (u=255-&nbsp; 1,j= 97,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add(103); for (u=255-&nbsp; 2,j= 89,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add(107); for (u=255-&nbsp; 4,j=109,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add(109); for (u=255-&nbsp; 8,j= 79,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add(113); for (u=255- 16,j= 73,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add(127); for (u=255- 32,j= 71,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add(131); for (u=255- 64,j= 31,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add(137); for (u=255-128,j= 29,i=j>>1;i<primes_map_sz;i+=j) primes_map[i]&=u;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; if (!primes_i32_alloc)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if (p&nbsp; <=1) return 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// ignore too small walues&nbsp; &nbsp; &nbsp; &nbsp; if (p&1==0) return 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// not prime if even&nbsp; &nbsp; &nbsp; &nbsp; if (p>primes_map_p0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j=p>>1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i=j; if (i>=primes_map_N[0]) i%=primes_map_N[0]; if (!(primes_map[i]&&nbsp; 1)) return 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i=j; if (i>=primes_map_N[1]) i%=primes_map_N[1]; if (!(primes_map[i]&&nbsp; 2)) return 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i=j; if (i>=primes_map_N[2]) i%=primes_map_N[2]; if (!(primes_map[i]&&nbsp; 4)) return 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i=j; if (i>=primes_map_N[3]) i%=primes_map_N[3]; if (!(primes_map[i]&&nbsp; 8)) return 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i=j; if (i>=primes_map_N[4]) i%=primes_map_N[4]; if (!(primes_map[i]& 16)) return 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i=j; if (i>=primes_map_N[5]) i%=primes_map_N[5]; if (!(primes_map[i]& 32)) return 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i=j; if (i>=primes_map_N[6]) i%=primes_map_N[6]; if (!(primes_map[i]& 64)) return 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i=j; if (i>=primes_map_N[7]) i%=primes_map_N[7]; if (!(primes_map[i]&128)) return 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; an=primes_i32[primes_i32.num-1];&nbsp; &nbsp; if (an>=p)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; // linear table search&nbsp; &nbsp; &nbsp; &nbsp; if (p<127)&nbsp; // 31st prime&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (an>=p) for (i=0;i<primes_i32.num;i++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a=primes_i32[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (a==p) return 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (a> p) return 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; // approximation table search&nbsp; &nbsp; &nbsp; &nbsp; else{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (j=1,i=primes_i32.num-1;j<i;j<<=1); j>>=1; if (!j) j=1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (i=0;j;j>>=1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i|=j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (i>=primes_i32.num) { i-=j; continue; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a=primes_i32[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (a==p) return 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (a> p) i-=j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; a=an; a+=2;&nbsp; &nbsp; for (j=a>>1,i=0;i<8;i++) im[i]=j%primes_map_N[i];&nbsp; &nbsp; an=(1<<((bits(p)>>1)+1))-1; if (an<=0) an=1;&nbsp; &nbsp; an=an+an;&nbsp; &nbsp; for (;a<=p;a+=2)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; for (j=1,i=0;i<8;i++,j<<=1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// check if map is set&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (!(primes_map[im[i]]&j)) { j=-1; break; }&nbsp; &nbsp;// if not dont bother with division&nbsp; &nbsp; &nbsp; &nbsp; for (i=0;i<8;i++) { im[i]++; if (im[i]>=primes_map_N[i]) im[i]-=primes_map_N[i]; }&nbsp; &nbsp; &nbsp; &nbsp; if (j<0) continue;&nbsp; &nbsp; &nbsp; &nbsp; for (i=primes_map_i0;i<primes_i32.num;i++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; b=primes_i32[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (b>an) break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ((a%b)==0) { i=-1; break; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if (i<0) continue;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32.add(a);&nbsp; &nbsp; &nbsp; &nbsp; if (a==p) return 1;&nbsp; &nbsp; &nbsp; &nbsp; if (a> p) return 0;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; return 0;&nbsp; &nbsp; }//---------------------------------------------------------------------------void getprimes(int p)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// compute and allocate primes up to p&nbsp; &nbsp; {&nbsp; &nbsp; if (!primes_i32.num) isprime(3);&nbsp; &nbsp; int p0=primes_i32[primes_i32.num-1];&nbsp; &nbsp; // biggest prime computed yet&nbsp; &nbsp; if (p>p0+10000)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// if too big difference use sieves to fast precompute&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; // T((0.3516+0.5756*log10(n))*n) -> O(n.log(n))&nbsp; &nbsp; &nbsp; &nbsp; // sieves N/16 bytes p=100 000 000 t=1903.031 ms&nbsp; &nbsp; &nbsp; &nbsp; //&nbsp; ------------------------------&nbsp; &nbsp; &nbsp; &nbsp; //&nbsp; &nbsp;0&nbsp; 1&nbsp; 2&nbsp; 3&nbsp; 4&nbsp; 5&nbsp; 6&nbsp; 7 bit&nbsp; &nbsp; &nbsp; &nbsp; //&nbsp; ------------------------------&nbsp; &nbsp; &nbsp; &nbsp; //&nbsp; &nbsp;1&nbsp; 3&nbsp; 5&nbsp; 7&nbsp; 9 11 13 15 +-> +2&nbsp; &nbsp; &nbsp; &nbsp; //&nbsp; 17 19 21 23 25 27 29 31 |&nbsp; &nbsp; &nbsp; &nbsp; //&nbsp; 33 35 37 39 41 43 45 47 V +16&nbsp; &nbsp; &nbsp; &nbsp; //&nbsp; ------------------------------&nbsp; &nbsp; &nbsp; &nbsp; int N=(p|15),M=(N>>4);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // store only odd values 1,3,5,7,... each bit ...&nbsp; &nbsp; &nbsp; &nbsp; char *m=new char[M+1];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // m[i] ->&nbsp; is 1+i+i prime? (factors map)&nbsp; &nbsp; &nbsp; &nbsp; int i,j,k,n;&nbsp; &nbsp; &nbsp; &nbsp; // init sieves&nbsp; &nbsp; &nbsp; &nbsp; m[0]=254; for (i=1;i<=M;i++) m[i]=255;&nbsp; &nbsp; &nbsp; &nbsp; for(n=sqrt(p),i=1;i<=n;)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int a=m[i>>4];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(a&&nbsp; 1)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(a&&nbsp; 2)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(a&&nbsp; 4)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(a&&nbsp; 8)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(a& 16)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(a& 32)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(a& 64)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(a&128)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; // compute primes&nbsp; &nbsp; &nbsp; &nbsp; i=p0&0xFFFFFFF1; k=m[i>>4]; // start after last found prime in list&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k&&nbsp; 1)!=0)&&(i>p0)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k&&nbsp; 2)!=0)&&(i>p0)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k&&nbsp; 4)!=0)&&(i>p0)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k&&nbsp; 8)!=0)&&(i>p0)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k& 16)!=0)&&(i>p0)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k& 32)!=0)&&(i>p0)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k& 64)!=0)&&(i>p0)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k&128)!=0)&&(i>p0)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; for(j=i>>4;j<M;i+=16,j++)&nbsp; &nbsp;// continue with 16-blocks&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; k=m[j];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (!k) continue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(k&&nbsp; 1)!=0) primes_i32.add(i&nbsp; &nbsp;);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(k&&nbsp; 2)!=0) primes_i32.add(i+ 2);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(k&&nbsp; 4)!=0) primes_i32.add(i+ 4);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(k&&nbsp; 8)!=0) primes_i32.add(i+ 6);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(k& 16)!=0) primes_i32.add(i+ 8);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(k& 32)!=0) primes_i32.add(i+10);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(k& 64)!=0) primes_i32.add(i+12);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (int(k&128)!=0) primes_i32.add(i+14);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; k=m[j]; // do the last primes&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k&&nbsp; 1)!=0)&&(i<=p)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k&&nbsp; 2)!=0)&&(i<=p)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k&&nbsp; 4)!=0)&&(i<=p)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k&&nbsp; 8)!=0)&&(i<=p)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k& 16)!=0)&&(i<=p)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k& 32)!=0)&&(i<=p)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k& 64)!=0)&&(i<=p)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; if ((int(k&128)!=0)&&(i<=p)) primes_i32.add(i); i+=2;&nbsp; &nbsp; &nbsp; &nbsp; delete[] m;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; else{&nbsp; &nbsp; &nbsp; &nbsp; bool b0=primes_i32_alloc;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32_alloc=true;&nbsp; &nbsp; &nbsp; &nbsp; isprime(p);&nbsp; &nbsp; &nbsp; &nbsp; primes_i32_alloc=false;&nbsp; &nbsp; &nbsp; &nbsp; primes_i32_alloc=b0;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }//---------------------------------------------------------------------------解决了矿井代码中的一些溢出漏洞（筛子周期......）还有一些进一步的优化添加了一个getprimes(p)功能，primes<=p如果它们还没有那么快就可以快速添加到列表中在前1000万个质数上测试正确性（最多15 485 863）getprimes(15 485 863) 我的设置在175.563毫秒解决了它isprime 这种粗糙的方式比较慢primes_i32是一个动态的ints 列表primes_i32.num是int列表中的s 数primes_i32[i]是i-thint i = <0,primes_i32.num-1>primes_i32.add(x)添加x到列表的末尾primes_i32.allocate(N)为N列表中的项预先分配空间以避免重新分配减速[笔记]我使用这个非并行版本的欧拉问题10（所有素数的总和低于2000000）&nbsp; &nbsp; ----------------------------------------------------------------------------------&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Time&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ID&nbsp; &nbsp; &nbsp; Reference&nbsp; &nbsp; | My solution&nbsp; &nbsp;| Note&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; ----------------------------------------------------------------------------------&nbsp; &nbsp; [&nbsp; 35.639 ms] Problem010. 142913828922 | 142913828922&nbsp; | 64_bit筛选标签每个都作为primes_map[]阵列中的位片，并且仅使用奇数值（甚至不需要记住筛子）。如果你想要找到所有素数的最大速度，那么只需调用isprime(max value)并读取其中的内容primes_i32[]我使用一半的比特大小而不是sqrt来提高速度希望我没有忘记在这里复制一些东西

Answer 2

只是一些想法：（i）你的Primes类不是线程安全的 -&nbsp;crossOut例如不是线程安全的 - 所以很可能你的并行线程必须做更多的工作，因为他们没有看到其他人做了什么（ ii）即使这样有效，你也会做更多的工作，因为你可以在划掉17和19之前检查17 * 19（而在顺序算法中，这是不可能发生的）（iii）如果你的程序很快完成（比如说）几百秒的ms），启动线程的时间可能会超过任何收益。

Answer 3

您遇到其他问题时很可能会遇到错误的共享。此外，2*processors线程可能太多了。从两个线程开始，看看是否能为您提供正确的结果和性能提升。然后增加线程数。