USACO Training Section1.5 Prime Palindromes(2)ふるい方が速い

また,問題提示はまず返事文を求めて素数かどうかを判断する.逆にすれば可能ですが、素数の計算範囲は1000000以内でなければなりませんが、メモリがオーバーします.整数、bool、char配列の代わりにビット操作を用いてスクリーンプロセスを記録することができる.次の2つのスクリーンルーチンを見てください.

char is_prime[_max_];
int bis_prime[(_max_+31)>>5];
void char_sifter()
{
	for(register int i=2; i<=sqrt(float(_max_)); ; i++){
		if( !is_prime[i] )
			continue ;
		for( register int cur=i<<1; cur<_max_; cur+=i )
			is_prime[cur]=0 ;
	}
}

void bit_sifter()
{
	for(register int i=2; i<=sqrt(float(_max_)); i++){
		if( !( ((bis_prime[i>>5]) >> (i & 0x1f)) &1 ) )
			continue ;
		for( register int cur=i<<1; cur<_max_; cur+=i )
			bis_prime[cur>>5] &= ~(1<<(cur&0x1f)) ;
	}
}

一般にcharで走るのはビットストレージより速いと考えられますが、事実は逆です.
bit_Sifter比char_Sifterは2倍以上速い.原因:32ビットアーキテクチャではchar操作は事前に32ビットに変換する必要があり、その効率は直接のビット操作に及ばない(基本的にアセンブリ命令に対応する).
bit_でSifterはふるい法をして素数を得てから返事を得た後に判断し,0.302秒であった.以前のプログラムでは,素数であるか否かを直接返信を得,0.794秒であった.メモリ使用は,前者が4152 KB,後者が2916 KBと大きく異なる.
いっそ直接ふるい法を使って素数を判断してから回数を判断するプログラムを書いて、1回テストして合格して、限界の下で0.389 secs、4148 KB.また、このプログラムには偶数ビットの数値はスキップされていません.スキップすれば、もっと速くなります.

/*
ID: blackco3
TASK: pprime
LANG: C++
*/
#include <fstream>
#include <memory.h>
#include <math.h>
using namespace std;

#define _max_ 10000000
int bis_prime[(_max_+31)>>5];
const int sifter_gate=sqrt(float(_max_));
void bit_sifter( ) {
	for(register int i=2; i<=sifter_gate; i++){
		if( !( ((bis_prime[i>>5]) >> (i & 0x1f)) &1 ) )
			continue ;
		for( register int cur=i<<1; cur<_max_; cur+=i )
			bis_prime[cur>>5] &= ~(1<<(cur&0x1f)) ;
	}
}

int main()
{	
	ifstream fin("pprime.in");
	int low, up ;
	fin >> low >> up;
	up = up>_max_ ? _max_ : up ;
	ofstream fout("pprime.out");
	memset( bis_prime, 0xff, sizeof(bis_prime) ); 
	bit_sifter();
	register int *p_prime=bis_prime+(low>>5);
	register int bit = low&0x1f, i;
	int digit[8], rank, tmp, found ;
	for( int cur=low; cur<=up; cur++){
		if( (*p_prime >> bit)&1 ){
			rank=0 , tmp=cur;
			while( tmp ) 
				digit[rank++] = tmp%10, tmp /= 10 ;
			for( found=1, i=0; i<(rank>>1); i++)
				if( digit[i]!=digit[rank-1-i] ){
					found=0;
					break ;
				}
			if( found )
				fout << cur << endl;
		}
		if( ++bit==32 )
			bit=0, p_prime++ ;
	}
	return 0;
}