题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=113

题目大意：

      如果一个数可以分解成2个素数的乘积，那么就输出yes否则输出no.

解题思路：

      先筛选出素数，然后判断找到那个能整除这个数的素数，判断商是否为素数就行啦！起先题目给看错了以为是相邻的素数的积。

解题代码：

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
#define Max 50000
bool isprime[Max];
int prime[Max];
int cp;
void mkprime(){
	cp=1;
	memset(isprime,true,Max);
	prime[0]=2;
	for(int i=2;i<Max;i++){
		if(isprime[i]==true){
			prime[cp++]=i;
			for(int j=1;i*j<Max;j++)
				isprime[i*j]=false;
		}
	}
}
bool isp(int n){
	if(n==1) return false;
	if(((n!=2)&&!(n%2))||((n!=3)&&!(n%3))||
	   ((n!=5)&&!(n%5))||((n!=7)&&!(n%7)))
			return false;
	int t=sqrt(n);
	for(int i=2;i<t;i++)
		if(n%i==0)
			return false;
	return true;
}
int main(){
	mkprime();
	int cas;
	cin>>cas;
	while(cas--){
		int n;
		cin>>n;
		int flag=0;
		for(int i=0;i<cp;i++){
			if(n%prime[i]==0)
				if(isp(n/prime[i])){
						flag=1;
						break;
				}
		}
		if(flag)
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
	return 0;
}

扩展知识：http://en.wikipedia.org/wiki/Primality_test

题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=102

题目大意：

     求不大于N且与N互质的数的个数。

解题思路：

      刚开始就想到暴力法，枚举每个数看看是不是gcd(n,i)==1。

      后来想到了欧拉函数，这不就是典型的欧拉函数题，先分解素数然后求欧拉函数。

      欧拉函数法用的时间是暴力法的一半。

解题代码：

#include<iostream>
using namespace std;
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
int main(){
	int n;
	while(cin>>n){
		int sum=0;
		for(int i=1;i<=n;i++){
			if(gcd(n,i)==1)
				sum++;
		}
		cout<<sum<<endl;
	}
}

#include<iostream>
#include<cstring>
using namespace std;
#define Max 10000
bool isprime[Max+10];
int  prime[Max+10];
int  countp;
void mkprime(int n){
	countp=1;
	memset(isprime,true,Max+10);
	prime[0]=2;
	for(int i=3;i<=n;i+=2){
		if(isprime[i]==true){
			prime[countp++]=i;
			for(int j=1;i*j<=n;j++)
				isprime[i*j]=false;
		}
	}
}
int eular(int n){
	for(int i=0;prime[i]<=n&&i<countp;i++)
		if(n%prime[i]==0){
			n/=prime[i];
			n*=prime[i]-1;
		}
	return n;
}
int main(){
	int n;
	while(cin>>n){
		mkprime(n);
		if(n==1)
			cout<<1<<endl;
		else
			cout<<eular(n)<<endl;
	}
}

 扩展知识：

http://en.wikipedia.org/wiki/Euler%27s_totient_function

http://linuxsir.org/bbs/showthread.php?t=278294