[数论] HOJ 2561 MaoLaoDa Number 筛素数 - jjaw2013 - 博客频道 - CSDN.NET

http://acm.hit.edu.cn/hoj/problem/view?id=2561

Background

MaoLaoDa likes studying numbers, especially the prime numbers, very much. One day, MaoLaoDa found that a number could be expressed as the product of two prime numbers. For instance, 10 = 2 x 5, and he called this kind of numbers MaoLaoDa Numbers. Now, give you a number N and you should tell me whether it is a MaoLaoDa number or not.

Input

Multiple test cases, each contains a positive integer, N (N <= 2³¹ - 1).

Output

For each case, print "Yes" when N is a MaoLaoDa number, or you should print "No".

Sample Input

10
11

Sample Output

Yes
No

解题报告：

此题就是问一个数是否能化为两个素数相乘。范围在int型内，开根号可知只需要找到前50000个数中的素数即可。代码如下：

1. int prime[6000],num;  
2. bool visited[50000];  
3. void isprime(){  
4.     num=0;  
5.     memset(visited,0,sizeof(visited));  
6.     memset(prime,0,sizeof(prime));  
7.     for(int i=2; i<=50000; i++){  
8.         if(visited[i] == 0)  
9.             prime[num++] = i;  
10.         for(int j=0; j<num && prime[j]*i<=50000; j++){  
11.             visited[prime[j]*i] = 1;  
12.             if(i%prime[j] == 0)  
13.                 break;  
14.         }  
15.     }  
16. }  
17. bool primes(int n){  
18.     for(int i=0;prime[i]*prime[i]<=n;i++)  
19.         if(n%prime[i]==0)  
20.             return false;  
21.     return true;  
22. }  
23. int main(){  
24.     isprime();  
25.     int n;  
26.     while(scanf("%d",&n)==1){  
27.         bool flag=false;  
28.         for(int i=0;(long long)prime[i]*prime[i]<=n;i++)  
29.             if(n%prime[i]==0)  
30.                 if(primes(n/prime[i])){  
31.                     flag=true;  
32.                     break;  
33.                 }  
34.         if(flag)  
35.             printf("Yes\n");  
36.         else  
37.             printf("No\n");  
38.     }  
39.     return 0;  
40. }  

Read full article from [数论] HOJ 2561 MaoLaoDa Number 筛素数 - jjaw2013 - 博客频道 - CSDN.NET