陈维晃的个人主页

Semi-Prime

Time Limit: 1 Seconds Memory Limit: 32768 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

Output for Sample Input

No
Yes
Yes
No

Source: Zhejiang University Local Contest 2006, Preliminary

本题要求判断一个数是否是半素数.凡能分解成两个素数相乘的数就是半素数.
因为数据量很大,所以要先将1~1000000以内的半素数打表,再进行查询操作.
整个步骤如下

• 利用筛法建立[2,500000]以内的素数表isPrime,时间复杂度O(nlog(log n))
• 利用素数表求得[2,500000]以内的素数,存于prime数组中,时间复杂度O(n)
• 利用prime数组暴力打表,得到半素数表ePrime,时间复杂度O(n*n)
• 查询操作,时间复杂度O(1)

CODE

#include
#include
#include
_Bool isPrime[500005];
void init()
{
  int i,j;
  memset(isPrime, true, sizeof(isPrime));
  for(i = 2; i <= 500000; ++i)
    if(isPrime[i])
      for(j = i + i;j <= 500000;j += i)
        isPrime[j] = false;
}
int main()
{
  init();
  int i, j, k, n;
  int prime[500000];
  for(i = 2, j = 0; i < 500000; ++i)
    if(isPrime[i]) prime[j++] = i;
  k = j;
  _Bool sPrime[1000005];
  memset(sPrime, false ,sizeof(sPrime));
  for(i = 0; i < k; ++i)
    {
      for(j = i; j < k; ++j)
        {
          n = prime[i] * prime[j];
          if(n > 1000000 || n < 0) break;
          sPrime[n] = true;
        }
    }
  while(scanf("%d",&n) != EOF)
    printf("%s\n", sPrime[n]?"Yes":"No");
  return 0;
}