Sgu/113

对n暴力质因数分解,暴力判断第一次分解出的两个因子是否都是质数(其中有一个实际上不用判断 见下面注释).

//P*M
#include<cstdio>
#include<cstring>
#include<cmath>
int n, p1, p2, x;
bool flag;
int gcd(int a, int b){
  if(b == 0)return a; else return gcd(b, a % b);  
}
bool prime(int a){//暴力n^(1/2)判断
  bool flag = true;
  for(int i = 1; i <= int(sqrt(a)); i++){
    if(gcd(a, i) > 1){flag = false; break;}
  }
  return flag;
}
int main(){
  freopen("sgu113.in", "r", stdin);
  freopen("sgu113.out", "w", stdout);
  scanf("%d", &n);
  for(int i = 1; i <= n; i++){
    scanf("%d", &x);
    if(x <= 0){printf("No\n"); continue;};
    p1 = 0;
    for(int j = 2; j <= int(sqrt(x)); j++){//暴力n^(1/2)分解
      if(x % j == 0){p1 = j; p2 = x/j; break;}
    }
    flag = false;//p1作为最小非1因子一定是一个质数 只要判断p2
    if(p1){if(prime(p2)){flag = true;}}
    if(flag){printf("Yes\n");}else{printf("No\n");}
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}

我用上述方法，结果超时。于是还是先处理出来所有的质数再操作，代码如下：

//Silver_Wings
#include<cstring>
#include<iostream>
using namespace std;
 
bool flag[100020], mark;
int t, t1, t2, num, n, prime[100000];
 
bool jp(int v)
{
  if (v <= 100000){
    return flag[v];
  }
 
  for (int i = 1; i <= num; ++i){
    if (v % prime[i] == 0) {return false;}
  }
  return true;
}
 
int main()
{
  num = 0;
  memset(flag, false, sizeof(flag));
  for (int i = 2; i <= 100000; ++i){
    mark = true;
    for (int j = 1; j <= num; ++j){
      if (i % prime[j] == 0) {mark = false; break;}
    }
    if (mark) {num++; prime[num] = i; flag[i] = true;}
  }  
 
  cin >> n;     
  for (int i = 1; i <= n; ++i) {
    cin >> t;    
    if (t <= 0) {cout << "No" << endl; continue;}
    mark = true;
    for (int j = 1; j <= num; ++j) {
      t2 = t % prime[j];
      if (t2 == 0) {
        t1 = t / prime[j];
        if (jp(t1)) {cout << "Yes";}
                       else {cout << "No";}
        mark = false; break;
      }      
    }
    if (mark) {cout << "No";}
    cout << endl;
  }
 
  return 0;
}

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
 
const int size = 111111;
 
int prime[size], check[size] = {0}, tot = 0;
 
void get_prime() {
	for (int i = 2; i < size; i++) {
		if (!check[i]) prime[tot++] = i;
		for (int j = i + i; j < size; j += i)
			check[j] = 1;
	}
}
 
bool is_prime(int x) {
	for (int i = 0; prime[i] * prime[i] <= x; i++)
		if (x % prime[i] == 0) return false;
	return true;
}
int main() {
	get_prime();
	int n, m;
	scanf("%d", &n);
	while (n--) {
		scanf("%d", &m);
		bool flag = false;
		for (int i = 0; prime[i] * prime[i] <= m; i++)
			if (m % prime[i] == 0 && is_prime(m / prime[i])) {
				puts("Yes"); flag = true; break;
			}
		if (!flag) puts("No");	
	}
	return 0;
}

更简洁的做法

放一个简洁的代码 暴力枚举a的因子，在此基础上进行了一定优化

#include<iostream>
using namespace std;
int n,a;bool ok;
bool prime(int x)
{
	for(int i=2;i*i<=x;i++) if(x%i==0) return false;
	return true;
}
int main()
{
	cin>>n;
	while(n--)
	{
		cin>>a;ok=false;
		for(int i=2;i*i<=a;i++)
			if(a%i==0)//找到a的因子 i 和 a/i ，很容易知道 i 一定是素数（因为没有一个比i小的整数能被a整除） 
				if(prime(a/i)) {ok=true;break;}//判断因子 a/i 是否为素数 
				else break; 	// 如果不是 那么 a/i=p1*p2*p3*...*pn ->a/i一定能写成多个素数相乘，那么a 一定能写成p1*p2*p3*...*pn*i，由此可知a不可能写成a=p1*p2 
		if(ok) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}