OJ Board

Code: Select all

#include<stdio.h>
#include<math.h>
#define MAX 1000001


struct st
{
	long fact;
	long mu;
	long M;
}
arr[MAX+5];
void make()
{
	long i,j,k,count=0;
	for(i=2;i<MAX;i++)
	{
		if(arr[i].fact==0)
		{
			for(j=i;j<MAX;j+=i)
			{
				k=j;
				count=0;
				while(k%i==0)
				{
					arr[j].fact++;
					k/=i;
					count++;
				}
				if(count>1)
					arr[j].mu = -2;
			}
		}
	}
	arr[1].fact=0;
	for(i=1;i<MAX;i++)
	{
		if(arr[i].mu==-2)
			arr[i].mu=0;
		else if(arr[i].fact%2==0)
			arr[i].mu=1;
		else
			arr[i].mu=-1;
	}
	for(i=1;i<MAX;i++)
		arr[i].M=arr[i-1].M+arr[i].mu;
}
main()
{
	long input;

	make();
	while(1)
	{
		scanf("%ld",&input);
		if(input==0)
			break;
		printf("%8ld%8ld%8ld\n",input,arr[input].mu,arr[input].M);
	}
	return 0;
}

Code: Select all

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

#define  MAX           1000000

long Factor[MAX + 1] = {0};
bool SqureFree[MAX + 1] = {false};
long mu[MAX + 1]={0,1,-1,-1,0},M[MAX + 1]={0,1,0,-1,0};
long prime[ MAX ] = {0};

int main()
{
	long i,t,n,j,s;
	//seeving
	s =(long) sqrt(MAX) + 1;
	for(i=2;i<s;i++)
		if(prime[i]==0)
			for(j=2;i*j<=MAX;j++)
				prime[i*j] = 1;
	prime[0]=2;  //took prime serialy
	n=1;
	for(i=3;i<MAX;i=i+2)
		if(prime[i]==0)
			prime[n++]=i;
	prime[n] = 0;

	for(i=0;i<n;i++)
	{
		t = prime[i];
		for(j=1;t<=MAX;j++)
		{
			t = prime[i]*j;
			Factor[t] += 1;
		}
	}

	for(i=0;i<=s;i++)
	{		
		t = prime[i]*prime[i];

		for(j=t;j<=MAX;j+=t)
			SqureFree[j] = true;
	}
	
	for(i=4;i<=MAX;i++)
	{
		if(SqureFree[i]==true)
			mu[i] = 0;
		else if( Factor[i]%2 )
			mu[i] = -1;
		else
			mu[i] = 1;
		M[i] = M[i-1] + mu[i];
	}
	
	while( scanf("%ld",&n),n )
		printf("%8ld%8ld%8ld\n",n,mu[n],M[n]);
	return 0;
}

Code: Select all

   50000       0      23
  100000       0     -48
 1000000       0     212