ZOJ 2723 Semi-Prime ||ZOJ 2060 Fibonacci Again 水水水！

两题水题：

1.如果一个数能被分解为两个素数的乘积，则称为Semi-Prime，给你一个数，让你判断是不是Semi-Prime数。

2.定义F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2) 让你判断第n项是否能被3整除。

1.ZOJ 2723 Semi-Prime

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1723

打表即可。

#include<cstdio>

const int MAXN=500000+10;

bool prime[MAXN]={0};

int num[MAXN],len;

int main()

{

	for(int i=2;i*i<MAXN;i++)

		if(!prime[i])

		for(int j=i;j*i<MAXN;j++)

			prime[i*j]=1;

	for(int i=2;i<MAXN;i++)

		if(!prime[i])

			num[len++]=i;

	int n;

	while(~scanf("%d",&n))

	{

		int cnt=0,cur=0;

		while(n!=1)

		{

			while( n % num[cur]==0)

			{

				cnt++;

				n/=num[cur];

			}

			cur++;

			if(cur >= len /*|| cnt >2*/ )

			 break;

		}

		if(cnt==2)

			puts("Yes");

		else

			puts("No");

	}

	return 0;

}

2.ZOJ 2060 Fibonacci Again

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1060

不mod 3 会溢出。

方法1：直接打表

#include<cstdio>

const int MAXN=1000000+2;

int f[MAXN];

int main()

{

	f[0]=7%3;f[1]=11%3;

	for(int i=2;i<MAXN;i++)

		f[i]=(f[i-1]%3+f[i-2]%3)%3;

	int n;

	while(~scanf("%d",&n))

	{

		if(f[n] ==0)

			puts("yes");

		else

			puts("no");

	}

	return 0;

}

方法2：

看上面的打表，可发现每8项一循环。

#include<cstdio>

const int MAXN=8;

int f[MAXN];

int main()

{

	f[0]=7%3;f[1]=11%3;

	for(int i=2;i<8;i++)

		f[i]=(f[i-1]%3+f[i-2]%3)%3;

	int n;

	while(~scanf("%d",&n))

	{

		if(f[n % 8] ==0)

			puts("yes");

		else

			puts("no");

	}

	return 0;

}