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

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MOD 2147483648
 
inline int mul_mod(int a, int b, int c)
{
	int div, mod;
	asm ("mul %3; div %4": "=a" (div), "=&d" (mod): "a" (a), "r" (b), "r" (c));
	return mod;
//	int res, div;
//	asm volatile("mull %%ebx; div %%ecx" : "=a"(div), "=d"(res) : "a"(x), "b"(y), "c"(n));
//	return res;
}
 
static unsigned powmod(unsigned long long int a, unsigned long long int k, unsigned int n)
{
	unsigned long long int b=1;
	while (k) 
	{
		if (!(k & 1)) 
		{
			k = k>>1;
//			asm volatile("divl %%ebx" : "=a"(k) : "a"(k), "b"(2));
			a = mul_mod(a,a,n);
		}
		else 
		{
			--k;
			b = mul_mod(b,a,n);
		}
	}
	return b;
}

int isprime(unsigned int m)
{
	int t=m-1;
	int s=0;
	while (!(t & 1))
	{
		++s;
		t = t >> 1;
	}
	unsigned int a = 3;
	unsigned long long int z = powmod (a,t,m);
	if (z != 1)
	{
		int k;
		for (k = s; k > 0; --k)
		{
			if (z == m-1)
			{
				return 1;
			}
			z= powmod(z,2,m);
		}
		return 0;
	}
	return 1;
}
 /*
16760697
16921010
17223855
17353014
17396745
18525293
19178066
19410253
19431849
19517126
19872927*/
int main()
{
	putchar('0');
	unsigned int a=1;
	int i;
	int j=1;
	int x[]={-1, 1814223, 2302519,5802139, 6018531, 6748041, 7376997, 8331288, 8384744, 
	8482997, 8684368, 8906901, 9351608, 9639741, 10514661,10537443, 10833847, 11729322, 
	11817290, 11938308, 12241470, 12581970, 14088293, 14385240, 14747267, 15942193, 
	16697128, 16760697, 16921010, 17223855, 17353014, 17396745, 18525293, 0};
	
	while (x[j])
	{
		for (i = x[j-1]+1; i < x[j] ; ++i)
    	{
       		a = (a + 1234567890)%(MOD);
			 
			if (!(a%5)||!(a%3)||!(a%7)||!(a%11)||!(a%13)||!(a%17)||!(a%19)||!(a%23)||!(a%29)
				||!(a%31)||!(a%37)||!(a%41)||!(a%43)||!(a%47)||!(a%53)
				||!(a%59)||!(a%61)||!(a%67)||!(a%71)) putchar('0');
			else 
				if (isprime (a)) putchar('1');
						else putchar('0');
		//printf ("%d", isprime (a));
		}
		putchar('0');
		a = (a + 1234567890)%(MOD);
		++j;
	}
	return 0;
}