[已解决]求助，很急！！

FC_YSN

求助，很急！！

最佳答案

月排行榜 / 总排行榜

jackz007

2020-11-23 14:55:36

FC_YSN 发表于 2020-11-22 18:23
还是

        顺便再测测这个：

1. #include <stdio.h>
   
2. 
   
3. int prime(int n)
   
4. {
   
5.         int c , d[4] = {2 , 4 , 2 , 2} , f = 0 , k      ;
   
6.         if(n > 1) {
   
7.                 if(n < 127) {
   
8.                         for(f = 1 , k = 2 ; k * k < n + 1  ; k += 1) {
   
9.                                 if(k < n && ! (n % k)) {
   
10.                                         f = 0           ;
    
11.                                         break           ;
    
12.                                 }
    
13.                         }
    
14.                 } else {
    
15.                         if(n % 2 && n % 3 && n % 5 && n % 7) {
    
16.                                 for(c = 0 , f = 1 , k = 11 ; k * k < n + 1 ; k += d[c % 4] , c ++) {
    
17.                                         if(k < n && ! (n % k)) {
    
18.                                                 f = 0   ;
    
19.                                                 break   ;
    
20.                                         }
    
21.                                 }
    
22.                         }        
    
23.                 }
    
24.         }
    
25.         return f                                        ;
    
26. }
    
27. 
    
28. int main(void)
    
29. {
    
30.         int n                        ;
    
31.         scanf("%d" , & n)            ;
    
32.         if(prime(n)) printf("Yes\n") ;
    
33.         else printf("No.\n")         ;
    
34. }

复制代码

跳转到最佳答案楼层

jackz007

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         int d , f = 0 , k             ;
   
6.         scanf("%d" , & d)             ;
   
7.         if(d > 1) {
   
8.                 for(f = 1 , k = 2 ; k * k < d + 1 ; k ++) {
   
9.                         if(k < d && ! (d % k)) {
   
10.                                 f = 0 ;
    
11.                                 break ;
    
12.                         }
    
13.                 }
    
14.         }
    
15.         if(f) printf("Yes\n")         ;
    
16.         else printf("No.\n")          ;
    
17. }

复制代码

FC_YSN

jackz007 发表于 2020-11-22 17:24

他说运行超时了，能再优化点么？

jackz007

    这个呢？

1. #include <stdio.h>
   
2. 
   
3. int prime(int n)
   
4. {
   
5.         int f = 0 , k                                                  ;
   
6.         if(n > 1) {
   
7.                 if(n < 11) {
   
8.                         if(n == 2 || n == 3 || n == 5 || n == 7) f = 1 ;
   
9.                 } else {
   
10.                         if(n % 10 == 1 || n % 10 == 3 || n % 10 == 7 || n % 10 == 9) {
    
11.                                 for(f = 1 , k = 2 ; k * k < n + 1  ; k ++) {
    
12.                                         if(k < n && ! (n % k)) {
    
13.                                                 f = 0                  ;
    
14.                                                 break                  ;
    
15.                                         }
    
16.                                 }
    
17.                         }
    
18.                 }
    
19.         }
    
20.         return f                                                       ;
    
21. }
    
22. 
    
23. int main(void)
    
24. {
    
25.         int n                        ;
    
26.         scanf("%d" , & n)            ;
    
27.         if(prime(n)) printf("Yes\n") ;
    
28.         else printf("No.\n")         ;
    
29. }

复制代码

FC_YSN

jackz007 发表于 2020-11-22 18:19
这个呢？

还是

永恒的蓝色梦想

1. #include<stdio.h>
   
2. #include<math.h>
   
3. 
   
4. 
   
5. 
   
6. int main() {
   
7.     unsigned int i, n;
   
8.     double root;
   
9.     char temp = getchar();
   
10. 
    
11. 
    
12.     if (temp - '-') {
    
13.         temp -= '0';
    
14.         i = temp;
    
15. 
    
16.         for (;;) {
    
17.             switch (temp = getchar()) {
    
18.             case '\0':
    
19.             case '\n':
    
20.             case '\r':
    
21.             case EOF:
    
22.                 switch (i % 6) {
    
23.                 case 1:
    
24.                 case 5:
    
25.                     root = sqrt(i);
    
26. 
    
27.                     for (n = 3; n <= root; n += 2) {
    
28.                         if (!(i % n)) {
    
29.                             goto END;
    
30.                         }
    
31.                     }
    
32. 
    
33.                     puts("Yes");
    
34.                     return 0;
    
35.                 }
    
36. 
    
37.                 goto END;
    
38.             }
    
39. 
    
40.             i *= 10;
    
41.             temp -= '0';
    
42.             i += temp;
    
43.         }
    
44.     }
    
45.     else {
    
46.     END:
    
47.         puts("No");
    
48.         return 0;
    
49.     }
    
50. }

复制代码

FC_YSN

永恒的蓝色梦想 发表于 2020-11-22 18:54

还是错了一部分

TOP_LK

1. from math import sqrt
   
2. num = int(input())
   
3. end = int(sqrt(num))
   
4. is_prime = True
   
5. for x in range(2, end + 1):
   
6.     if num % x == 0:
   
7.         is_prime = False
   
8.         break
   
9. if is_prime and num != 1:
   
10.     print('yes')
    
11. else:
    
12.     print('no')

复制代码

永恒的蓝色梦想

FC_YSN 发表于 2020-11-22 20:01
还是错了一部分

发个错误的例子呗

风过无痕1989

jackz007 发表于 2020-11-22 17:24

1. #include<stdio.h>
   
2. #include<math.h>
   
3. int main()
   
4. {
   
5.     int num,i;
   
6.     scanf("%d",&num);
   
7.     for (i = 2;i < sqrt(num);i++)
   
8.     {
   
9.         if(num % i == 0)
   
10.         {
    
11.             printf("No");
    
12.             break;
    
13.         }
    
14.         else if(i >= num / 2)
    
15.         {
    
16.             printf("Yes");
    
17.             break;
    
18.         }
    
19.     }
    
20.     return 0;
    
21. }

复制代码

风过无痕1989

FC_YSN 发表于 2020-11-22 17:33
他说运行超时了，能再优化点么？

上面的程序，回复时点错了对象

jackz007

FC_YSN 发表于 2020-11-22 18:23
还是

        顺便再测测这个：

1. #include <stdio.h>
   
2. 
   
3. int prime(int n)
   
4. {
   
5.         int c , d[4] = {2 , 4 , 2 , 2} , f = 0 , k      ;
   
6.         if(n > 1) {
   
7.                 if(n < 127) {
   
8.                         for(f = 1 , k = 2 ; k * k < n + 1  ; k += 1) {
   
9.                                 if(k < n && ! (n % k)) {
   
10.                                         f = 0           ;
    
11.                                         break           ;
    
12.                                 }
    
13.                         }
    
14.                 } else {
    
15.                         if(n % 2 && n % 3 && n % 5 && n % 7) {
    
16.                                 for(c = 0 , f = 1 , k = 11 ; k * k < n + 1 ; k += d[c % 4] , c ++) {
    
17.                                         if(k < n && ! (n % k)) {
    
18.                                                 f = 0   ;
    
19.                                                 break   ;
    
20.                                         }
    
21.                                 }
    
22.                         }        
    
23.                 }
    
24.         }
    
25.         return f                                        ;
    
26. }
    
27. 
    
28. int main(void)
    
29. {
    
30.         int n                        ;
    
31.         scanf("%d" , & n)            ;
    
32.         if(prime(n)) printf("Yes\n") ;
    
33.         else printf("No.\n")         ;
    
34. }

复制代码

麻瓜瓜呀

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. bool flag[2147483648];
   
6. vector<long long> ans;
   
7. 
   
8. bool prime(long long n)
   
9. {
   
10.     fill(flag, flag + n, false);
    
11.     flag[0] = flag[1] = true;
    
12.     for (long long i = 2; i <= n; i++)
    
13.     {
    
14.         if (!flag[i])
    
15.             ans.push_back(i);
    
16.         for (long long j = 0; j < ans.size() && i * ans[j] <= n; j++)
    
17.         {
    
18.             flag[i * ans[j]] = true;
    
19.             if (i % ans[j] == 0)
    
20.                 break;
    
21.         }
    
22.     }
    
23.    
    
24.     return !flag[n];
    
25. }
    
26. 
    
27. int main(int argc, const char *argv[])
    
28. {
    
29.     long long n;
    
30.     cin >> n;
    
31.    
    
32.     if (n < 0)
    
33.     {
    
34.         cout << "No" << endl;
    
35.         return 0;
    
36.     }
    
37.     if (prime(n))
    
38.         cout << "Yes" << endl;
    
39.     else
    
40.         cout << "No" << endl;
    
41.     return 0;
    
42. }
    

复制代码

线性筛法，时间复杂度O(n).

FC_YSN

jackz007 发表于 2020-11-23 14:55
顺便再测测这个：

感谢！！