113_1.c

平时acm训练时ac的源代码

/*
113. Nearly prime numbers 
.C Accepted 133 ms 118 kb 
*/

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

int main()
{
	int *zy;
	int N, an[10], i, ti, j, y, k;
	long t, z;
	zy = (int *)malloc(sizeof(int)*3401);
	zy[0] = 2;
	for (ti=1, i=3; i<31608; i++)
	{
		N=1;
		for (j=2; j<=sqrt(i); j++)
		{
			if (0==i%j)
			{
				N=0;
				break;
			}
		}
		if (1==N)
		{
			zy[ti]=i;
			ti++;
		}
	}
	scanf("%d", &N);
	for (i=0; i<N; i++)
	{
		an[i]=0;
		ti=0;
		scanf("%ld", &t);
		for (j=0;j<3401 && 1!=t; j++)
		{
			if (0==t%zy[j])
			{
				if (t!=zy[j])
				{
					an[i]=1;
				}
				t = t/zy[j];
				break;
			}
		}
		k=sqrt(t);
		for (j=2; j<=k && 1==an[i]; j++)
		{
			if (0==t%j)
			{
				an[i] = 0;
				break;
			}
		}
	}
	for (i=0; i<N; i++)
	{
		if (1==an[i])
		{
			printf("Yes\n");
		}
		else
		{
			printf("No\n");
		}
	}
}