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; }
0 条评论。