- 注册时间
- 2007-12-26
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 539
- 在线时间
- 小时
|
发表于 2008-3-13 15:56:24
|
显示全部楼层
|
//jjww 说不清， 这个是没有太多优化的java版本，采用的是分段筛选法
// 缓存大小可以自己调节，暂时不考虑输出， 运行PI(2^31) 耗时 6s
// 上面的附件是 C++多线程版本, 也是筛选法(不只是统计个数)。
// 其实不喜欢用java些， 运行命令
// java PrimeNumber (单线程，不输出)
// java PrimeNumber 2 (多线程)
// java PrimeNumber 2 2 (输出素数, 超级慢)
public class PrimeNumber
{
static final int FACT = 255255; //3 * 5 * 7 * 11 * 13 * 17 = 255255
static final int SP = 7;
static final int BLOCKSIZE = FACT << 2;
static final int MOVE = 5;
static final int MASK = (1 << (MOVE - 1)) - 1;
static final int MAXN = 1 << 30;
static final int MAXM = ((BLOCKSIZE >> MOVE) + 2);
static final int MAX_THREADS = 4;
static final byte[] multp = { 6, 4, 2, 4, 2, 4, 6, 2 };
static boolean printout = false;
static int[] prime = new int[4794];
static char[] BaseTpl = new char[MAXM];
static byte[] bits = new byte[1 << (MASK + 1)];
static byte[] tablep30 = new byte[32];
static char MASKN(int n)
{
return (char)(1 << ((n >> 1) & MASK));
}
static int sieve( )
{
int i, pnums = 1;
int QMAXN = (int)Math.sqrt((double)MAXN) + 20;
prime[0] = 2;
for (i = 3; i < QMAXN; i += 2){
if ( (BaseTpl[i >> MOVE] & MASKN(i)) == 0 ){
prime[pnums++] = i;
for (int p = i * i; p < QMAXN && p > 0; p += i << 1)
BaseTpl[p >> MOVE] |= MASKN(p);
}
}
for (i = 0; i < MAXM; i++)
BaseTpl[i] = (char)0;
for (i = 1; i < SP; i++){
for (int p = prime[i]; p < BLOCKSIZE; p += prime[i] << 1)
BaseTpl[p >> MOVE] |= MASKN(p);
}
return pnums;
}
static int getBlocks(int start, int len)
{
int next, pnums = 0;
int maxp = (int)Math.sqrt((float)start + len) + 1;
char[] block = new char[MAXM];
for (int i = 0; i < (len >> MOVE) + 1; ++i)
block[i] = BaseTpl[i];
block[len >> MOVE] |= (char)~(MASKN(len) - 1);
for (int i = SP, p = prime[SP]; p < maxp; p = prime[++i]){
if (start > 0){
next = (p - (start - 1) % p) - 1;
if ((next & 1) == 0)
next += p;
}
else
next = p * p;
/*
int[] buf = {1, 2, 3, 4, 5, 6, 7, 8};
int mrid = ((start + next) / p) % 30;
for (int k = 0; k < 8; k++)
buf[k] = p * multp[k];
while (tablep30[mrid] == 0){
next += p << 1;
mrid = (mrid + 2) % 30;
}
int st = (tablep30[mrid] + 6) & 7;
//for (; next < len; next += buf[st = nexti[st]])
for (; next < len; next += buf[++st & 7])
block[next >> MOVE] |= (char)(1 << ((next >> 1) & MASK));
*/
int mrid = (start + next) / p;
if ((mrid %= 6) == 3){
next += 2 * p;
mrid += 2;
}
int nex1 = next + ((mrid == 1) ? (p << 2) : (p << 1));
p *= 6;
for (; nex1 < len; nex1 += p, next += p){
block[next >> MOVE] |= (char)(1 << ((next >> 1) & 15));
block[nex1 >> MOVE] |= (char)(1 << ((nex1 >> 1) & 15));
}
//for (; next < len; next += p)
if (next < len)
block[next >> MOVE] |= MASKN(next);
}
pnums += outPrint(block, start, len); //too slow
return pnums;
}
static int outPrint(char mask[], int start, int len)
{
int pnums = 0;
if (printout == false){
len >>= MOVE;
for (int k = 0; k <= len; k++)
pnums += bits[mask[k]];
}
else{
for (int i = 1; i <= len; i += 2){
if ((mask[i >> 5] & MASKN(i)) == 0){
System.out.println(start + i);
pnums ++;
}
}
}
return pnums;
}
static int[] table = new int[MAXN / BLOCKSIZE + 1];
static int getPrimes(int beg, int end)
{
int pnums = 0;
int _end = end;
if (beg < 2)
beg = 2;
for (int j = SP - 1; j >= 0 && beg <= prime[j]; j--){
if (end >= prime[j])
pnums++;
}
// int size = end % BLOCKSIZE;
// if (size != 0)
// pnums += getBlocks(end - size, size + 1);
int size = beg % BLOCKSIZE;
if (size != 0)
pnums -= getBlocks(beg - size, size);
beg /= BLOCKSIZE;
end /= BLOCKSIZE;
for (int i = beg; i < end; i++){
if (table[i] == 0)
table[i] = getBlocks(i * BLOCKSIZE, BLOCKSIZE);
pnums += table[i];
}
if (_end % BLOCKSIZE != 0)
pnums += getBlocks(end * BLOCKSIZE, _end % BLOCKSIZE + 1);
return pnums;
}
private static int multiThread()
{
int i;
int nThread = MAX_THREADS;
int totalCount = 0;
Worker[] works = new Worker[nThread];
for (i = 0; i < nThread; ++i){
works[i] = new Worker();
works[i].setStart(MAXN / nThread * i);
works[i].setEnd(MAXN / nThread * (i + 1));
}
works[nThread - 1].setEnd(MAXN);
Thread[] threads = new Thread[nThread];
for (i = 0; i < nThread; ++i){
threads[i] = new Thread(works[i]);
threads[i].start();
}
try
{
for (i = 0; i < nThread; ++i){
threads[i].join();
totalCount += works[i].getCount();
}
}
catch (Exception e) { }
return totalCount;
}
static class Worker implements Runnable
{
int count, start, end;
public void run(){
count = getPrimes(start, end);
System.out.println("Java : PI[" + start + ", " + (end) + "]: primes = " + count);
}
public void setStart(int n) { start = n; }
public void setEnd(int n) { end = n; }
public int getCount() { return count; }
};
public static void main(String[] args)
{
long start = System.currentTimeMillis();
int i, totalCount;
sieve( );
byte[] pri30 = { 1, 7, 11, 13, 17, 19, 23, 29 };
for (i = 0; i < 8; i++)
tablep30[pri30[i] % 30] = (byte)(i + 1);
for (i = 1; i < bits.length; i++)
bits[i] = (byte)(bits[i >> 1] + (i & 1));
for (i = 0; i < bits.length; i++)
bits[i] = (byte)( (1 << ( MOVE - 1)) - bits[i]);
if (args.length == 1)
totalCount = multiThread();
else{
if (args.length == 2)
printout = true;
totalCount = getPrimes(0, MAXN);
}
System.out.println("PI[0, " + (MAXN) + "]: primes = " + totalCount + ", time use " + (System.currentTimeMillis() - start) + " ms");
//for test
for (i = 2; i < 31; i++){
start = System.currentTimeMillis();
totalCount = getPrimes(0, 1 << i);
start = System.currentTimeMillis() - start;
System.out.println("PI(" + (1 << i) + ") = " + totalCount);
System.out.println("It take " + start + " ms");
}
}
} |
|
楼主: 无心人
IP卡
狗仔卡
显身卡
发表于 2008-3-13 15:59:58
