Cod sursa(job #591794)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 25 mai 2011 16:55:51
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>

#define min(a,b) (a<b ? a : b)
#define max(a,b) (a>b ? a : b)
#define N 1000005

bool prim[N];
short nr[N],nrr,fact[1000002][6];
long long r,sum;
int m,n,mi,ma;

void fa(int q) {
	int i;
	for(i=1;i<=nrr;++i)
		if(q%nr[i]==0) {
			fact[q][++fact[q][0]]=nr[i];
		}
}

void era() {
	int i,j;
	for(i=2;i*i<=5000;++i)
		if(!prim[i])
			for(j=2*i;j<=5000;j+=i)
				prim[j]=true;
	for(i=2;i<=5000;++i)
		if(!prim[i])
			nr[++nrr]=i;
}

int main () {
	int i,j,k,ver;
	freopen("mins.in","r",stdin);
	freopen("mins.out","w",stdout);
	scanf("%d%d",&n,&m);
	--n; --m;
	era();
	mi=min(n,m); ma=max(n,m);
	for(i=1;i<=mi;++i)
		fa(i);
	for(i=2;i<=mi;++i)
		for(j=1;j<=i;++j) {
			ver=0;
			for(k=1;k<=fact[j][0];++k)
				if(i%fact[j][k]==0)
					ver=1;
			if(ver==0)
				++sum;
		}
	sum*=2;
	for(i=mi+1;i<=ma;++i)
		for(j=1;j<=i;++j) {
			ver=0;
			for(k=1;k<=fact[j][0];++k)
				if(i%fact[j][k]==0)
					ver=1;
			if(ver==0)
				++sum;
		}
	printf("%lld",sum);
    return 0;
}