Четвёртый открытый Зеленоградский турнир 2008

#include <stdio.h>
char isPrimeRabin( unsigned n )
{
	char b = '0';

asm (
	"mov %7,%2;\
	mov %2,%1;\
	dec %1;\
	bsf %1, %4;\
	mov %4, %%ebp;\
	shr %%cl, %1;\
	mov %1, %4;\
	mov %1, %6;\
	and $0x1F, %4;\
	mov $1, %1;\
	shl %%cl, %1;\
	mov $5, %%cl;\
	shr %%cl, %6;\
	jz exit;\
	mov %1, %4;\
	inc %5;\
	xor %1, %1;\
	div %2;\
cycle:;\
	shr $1, %6;\
	jz last;\
	jnc mulx;\
	mov %5, %3;\
	mov %4, %1;\
	mul %3;\
	div %2;\
	mov %5, %4;\
	mov %3, %5;\
mulx:;\
	mov %5, %1;\
	mul %1;\
	div %2;\
	jmp cycle;\
last:;\
	mov %5, %1;\
	mul %4;\
exit:;\
	div %2;\
	cmp $1, %5;\
	jz prime;\
	lea 1(%5), %1;\
	cmp %2, %1;\
	jz prime;\
nexts:;\
	mov %5, %1;\
	mul %1;\
	div %2;\
	lea 1(%5), %1;\
	cmp %2, %1;\
	jz prime;\
	dec %%ebp;\
	jnz nexts;\
	jmp end;\
prime:;\
	movb $49, %0;\
end:;"
		: "=m"(b)
		: "a"(0),"S"(0),"b"(0),"c"(0),"d"(0),"D"(0),"r"(n));

	return b;
}

unsigned wrong[] = { 0x3E12, 0x1A5FA, 0x98470, 0xF2120, 0x21092C, 0x29BBA0, 
	0x2B78FC, 0x2C6B16, 0x3E1CA0, 0x5512DA, 0x5EA25B, 0x5F50FE, 0x64AA92, 
	0x6C5665, 0x83A85A, 0x83E965, 0x9DC169, 0xA8CB0D, 0xAC0BB9, 0xB1C077, 
	0xB86A83, 0xC33A18, 0xCA2200, 0xD35247, 0xD9B9F6, 0xD9DF44, 0xDCA764, 
	0xDD7680, 0xE667DC, 0xEE2D44, 0xF5B8D8, 0xFAEF20, 0x10E3958, 0x11EEAD0, 
	0x124A253, 0x12F8054, 0x12FC124, 0x14552FC, 0x146DB39, 0x14C0996, 
	0x15C9ED4, 0x16B06C8, 0x18ED5AF, 0x19756F0, 0x19AD84B, 0x1A15824, 
	0x1A9FAE8, 0x1B25E4C, 0x1D4892A, 0x1DC288D, 0x1E8F4C2, 0x1FA6127, 0x1FB11DA };
char output[1001];
#define _countof(A) sizeof(A)/sizeof(A[0])
int main()
{
	unsigned int a = 1, j = 0, t = 1;
	char b = '0';

	do
	{
		output[j++] = b;
		
		if ( j == _countof( output ) - 1 )
		{
			fputs( output, stdout );
			j = 0;
		}
		
		a = ( a + 1234567890 ) & 0x7fffffff;
		asm("movl %1, %5;mov $0xAAAAAAAB,%2;mul %5;and $0xC0000000,%2;jz 1f;mov $0xCCCCCCCD,%2;
		mul %5;and $0xC0000000,%2;and $1,%4;or %4,%2;jz 1f;movl $0x24924925,%2;mull %5;
		movl %5,%2;subl %4,%2;shrl $1,%2;addl %4,%2;shrl $2,%2;leal (,%2,8),%3;subl %2,%3;
		cmpl %3,%5;jz 1f;movl $0xBA2E8BA3,%2;mull %5;shrl $3,%4;imull $0xB,%4,%4;cmpl %4,%5;
		jz 1f;movl $0x4EC4EC4F,%2;mull %5;shrl $2,%4;imull $0xD,%4,%4;cmpl %5,%4;jz 1f;
		movl $0xF0F0F0F1,%2;mull %5;shrl $4,%4;movl %4,%2;shll $4,%2;addl %4,%2;cmpl %5,%2;
		jz 1f;movl $0xAF286BCB,%2;mull %5;movl %5,%2;subl %4,%2;shrl $1,%2;addl %4,%2;
		shrl $4,%2;imull $0x13,%2,%2;cmpl %5,%2;jz 1f;movl $0xB21642C9,%2;mull %5;shrl $4,%4;
		imull $0x17,%4,%4;cmpl %4,%5;jz 1f;movl $0x8D3DCB09,%2;mull %5;shrl $4,%4;
		imull $0x1D,%4,%4;cmpl %4,%5;jz 1f;movl $0x8421085,%2;mull %5;movl %5,%2;subl %4,%2;
		shrl $1,%2;addl %4,%2;shrl $4,%2;movl %2,%4;shll $5,%4;subl %2,%4;cmpl %4,%5;jz 1f;
		movl $0xBACF914D,%2;mull %5;movl %5,%3;subl %4,%3;shrl $1,%3;addl %4,%3;shrl $5,%3;
		imull $0x25,%3,%3;cmpl %3,%5;jz 1f;movl $0xC7CE0C7D,%2;mull %5;shrl $5,%4;
		imull $0x29,%4,%4;cmpl %4,%5;jz 1f;movl $0x2FA0BE83,%2;mull %5;shrl $3,%4;
		imull $0x2B,%4,%4;cmpl %4,%5;jz 1f;movl $0xAE4C415D,%2;mull %5;shrl $5,%4;
		imull $0x2F,%4,%4;cmpl %4,%5;jz 1f;movl $0x3521CFB3,%2;mull %5;movl %5,%3;
		subl %4,%3;shrl $1,%3;addl %4,%3;shrl $5,%3;imull $0x35,%3,%3;cmpl %3,%5;jz 1f;
		movl $0x8AD8F2FC,%2;mull %5;shrl $5,%4;imull $0x3B,%4,%4;cmp %4,%5;jz 1f;
		movl $0x864B8A7E,%2;mull %5;shrl $5,%4;leal (%4,%4,2),%3;shll $6,%4;subl %3,%4;
		cmp %4,%5;jz 1f;movl $0xF4898D60,%2;mull %5;shrl $6,%4;leal (%4,%4,2),%3;shll $6,%4;
		addl %3,%4;cmp %4,%5;jz 1f;movl $0xE6C2B448,%2;leal 1(%5),%4;mull %4;shrl $6,%4;
		imull $0x47,%4,%4;cmpl %4,%5;jz 1f;xorl %2,%2;jmp 2f;1:;movb $0x30,%%al;2:;
		movb %%al,%0;" : "=m"(b) : "m"(a), "a"(0), "c"(0), "d"(0), "S"(0));

		if ( b )
			continue;

		b = isPrimeRabin( a );

		if ( b == '1' )
		{
			int Lb = 0, Rb = _countof( wrong ) - 1;

			while( Lb <= Rb )
			{
				unsigned M = ( Lb + Rb ) >> 1;

				if ( t < wrong[ M ] )
					Rb = M - 1;
				else if ( t > wrong[ M ] )
					Lb = M + 1;
				else
				{
					b = '0';
					break;
				}
			}
		}

	}
	while( ++t <= 33333333 );

	output[j] = 0;
	fputs( output, stdout );
	return 0;
}