Semi-Prime(半素数）

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2723

Semi-Prime

Time Limit: 2 Seconds Memory Limit: 65536 KB

Prime Number Definition
An integer greater than one is called a prime number if its only
positive divisors (factors) are one and itself. For instance, 2, 11, 67,
89 are prime numbers but 8, 20, 27 are not.

Semi-Prime Number Definition
An integer greater than one is called a semi-prime number if it can be
decompounded to TWO prime numbers. For example, 6 is a semi-prime number
but 12 is not.

Your task is just to determinate whether a given number is a semi-prime number.

Input

There are several test cases in the input. Each case contains a single integer N (2 <= N <= 1,000,000)

Output

One line with a single integer for each case. If the number is a semi-prime number, then output "Yes", otherwise "No".

Sample Input

3
4
6
12

Sample Output

No
Yes
Yes
No

思路：如果一个数能分解为两个素数的乘积（大于1），那么这个数就是半素数。建立一个【2，500000】的素数集合，在建立一个【1，1000000】的半素数集合，

set是平衡检索二叉树，检索速度足够。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

#include <vector>

#include <set>

#include <map>

#include <algorithm>

using namespace std;

typedef long long ll;

vector<int>v;

set<int>s;

void get_prime(int b)

{

    int a[];

    memset(a,,sizeof(a));

    a[]=;

    for(int i=;i<=b;i++)

    {

        if(a[i]==) continue;

        v.push_back(i);

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

        {

            a[i*j]=;

        }

    }

}

void get_no_prime(int a)

{

    for(int i=;i<v.size();i++)

    {

        for(int j=;j<v.size();j++)

        {

            int ans=v[i]*v[j];

            if(ans<a) s.insert(ans);

            else break;

        }

    }

}

int main()

{

    int n;

    get_prime();

    get_no_prime();

    while(scanf("%d",&n)!=EOF)

    {

        puts(s.find(n)!=s.end()?"Yes":"No");

    }

    return ;

}

巴特西

Semi-Prime(半素数）

最新文章

热门文章