## 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

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

CODE

```#include<stdio.h> #include<string.h> #include<stdbool.h>   _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; }```
» 本博客采用署名 2.5 中国大陆许可协议进行许可，本文版权归作者所有，欢迎转载，但必须在明显位置给出原文连接。
anyShare分享到：