ZJU 2723 解题报告

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<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分享到:

Leave a Comment

NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>