1845-安全的密码-质因数分解

 1

 #include
 2 using namespace std;
 3 vector<char> str(50000,0);
 4 vector <long long> pri;
 5 //**开始定义一个全局变量数组，每个下表对应的值默认为0** 
 6 int pm[20000] = { 0 };
 7 
 8 void prime()                        //这个函数可以将1~50000内的所有素数都找出来，所以在main()函数开头执行一遍就行了 
 9 {
10     str[1] = 1;
11 
12     for (int i = 2; i < 50000; i++)
13     {
14         for (int j = 2 * i; j < 50000; j += i)
15             str[j] = 1; //某个数的倍数肯定不是素数 
16     }
17 }
18 void judge(long long n) {
19     int flag1 = 0, flag2 = 0;
20        if (n == 4) { 
21         printf("YES\n"); 
22         return;
23        }
24        else if (n % 4 == 0 || n == 5 || n == 7 || n == 11 || n == 13) {
25             printf("NO\n");
26             return;
27         }
28         else {
29     
30             for (int j = 0; j < 4700; j++) {
31                 int mid, high = 4700, low = 0;
32                 int k = mid = low + (high - low) / 2;
33                 if (pri[j] >= n) { printf("NO\n"); 
34                 return;
35 
36                 }
37                 
38                 for (; k < 4700; ) {
39                     
40                     if (pri[j]*pri[k]==n) {
41                         printf("YES\n");
42                         return;
43                     }
44                     else if(pri[j] * pri[k] < n&& low < high){
45                         low = mid + 1;
46                         mid = low + (high - low) / 2;
47                         k = mid;
48                     
49                     }
50                     else if (pri[j] * pri[k] > n&&low<high){
51                         high = mid - 1;
52                         mid = low + (high - low) / 2;
53                         k = mid;
54                         
55                     }
56                     else if(low>=high){
57                         break;
58                     }
59                 }
60             }
61             printf("NO\n");
62             return;
63         }
64     
65 }
66 void judge2(long long n) {
67 
68 }
69 
70 
71 int main() {
72     int a; long long n[1000];
73     prime();
74     for (int i =2; i < 50000; i++) {
75         if (!str[i]) pri.push_back(i);
76     }//pre-processing
77     
78     int t;
79     scanf("%d", &t);
80     for (int i = 0; i < t; i++) {
81         scanf("%lld", &n[i]);
82     }    
83     for (int i = 0; i < t; i++) {
84             judge(n[i]);
85 
86     }
87 
88     /*
89     cout << pri.size() << endl;//size=5133个质数
90     cout << pri.at(4700) << endl;//第4700个刚好是2*10^9的平方根*/
91     return 0;
92 }