SGU 113: Nearly prime numbers

题目链接：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

• 全局相关文章
• 相关文章