OJ Board

Code: Select all

Removed after AC!

Code: Select all

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

#define MAX 65005

char a[MAX]={0};

int fact[100];

void prime();
bool isprime(int n);
bool iscarmichael(int n);



int buildPrimeFactor(int n)
{
	int i,j;

	for(i=1,j=0;i<=n;i++)
		if(!(n%i)&&isprime(i))
			fact[j++]=i,n/=i,i=1;
	
	return j-1;
}


int main()
{
	int n;
	
	prime();
	
	while(1)
	{
		scanf("%d",&n);

		if(n==0)
			break;

		if(isprime(n))
			printf("%d is normal.\n",n);
		else
		{
			if(n%2)
			{
				if(iscarmichael(n))
					printf("The number %d is a Carmichael number.\n",n);
				else
					printf("%d is normal.\n",n);
			}
			else
				printf("%d is normal.\n",n);

		}
	}
	
	return 0;
}


void prime()
{
	int i,j,sq;

	for(i=4;i<MAX;i+=2)
		a[i]=1;
	
	sq=(int)sqrt(MAX);
	
	for(i=3;i<=sq;i+=2)
		for(j=i+i;j<MAX;j+=i)
			a[j]=1;
}

bool isprime(int n)
{
	if(a[n]==0)
		return true;

	return false;
}


bool iscarmichael(int n)
{
	int numFactor=buildPrimeFactor(n),i;

	bool flag=true;

	if(numFactor<3)
		flag= false;
	else
		for(i=0;i<numFactor;i++)
			if(i!=numFactor-1&&fact[i]==fact[i+1])
				flag= false;
	
	return flag;
}

Code: Select all

    #include<stdio.h>
    #include<math.h>
    #define M 80000

    char prime[M];

    int main()
    {
        long n,i,c,l,flag;
        sieve();
        while(1)
        {
            scanf("%ld",&n); if(n==0) break;
            printf("AC");
        }
        return 0;
    }