[已解决]半素数问题

灯火阑珊201

若一个自然数可以表示成两个素数乘积的形式，这个自然数就叫做半素数(Quadratic Almost Prime)。

不知道咋写。。求大佬帮助！！！

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-10-25 20:27:35

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. unsigned isPrime(int num) {
   
5.         if (num < 2) return 0;
   
6.         else if (num == 2) return 1;
   
7.         for (int n = 2; n < sqrt(num) + .5; ++n) {
   
8.                 if (!(num % n)) return 0;
   
9.         }
   
10.         return 1;
    
11. }
    
12. 
    
13. unsigned isSemiprime(int num) {
    
14.         if (num < 2) return 0;
    
15.         for (int n = 2, a, b; n < sqrt(num) + .5; ++n) {
    
16.                 if (!(num % n)) {
    
17.                         a = n;
    
18.                         b = num / n;
    
19.                         if (isPrime(a) && isPrime(b)) return 1;
    
20.                 }
    
21.         }
    
22.         return 0;
    
23. }
    
24. 
    
25. int main(void) {
    
26.         for (int n = 0; n <= 20; ++n) {
    
27.                 isSemiprime(n) ? printf("%d is Semiprime\n", n) : printf("%d\n", n);
    
28.         }
    
29.         return 0;
    
30. }

复制代码

1. 0
   
2. 1
   
3. 2
   
4. 3
   
5. 4 is Semiprime
   
6. 5
   
7. 6 is Semiprime
   
8. 7
   
9. 8
   
10. 9 is Semiprime
    
11. 10 is Semiprime
    
12. 11
    
13. 12
    
14. 13
    
15. 14 is Semiprime
    
16. 15 is Semiprime
    
17. 16
    
18. 17
    
19. 18
    
20. 19
    
21. 20

复制代码

跳转到最佳答案楼层

柿子饼同学

emm 数据范围说一下

灯火阑珊201

柿子饼同学 发表于 2022-10-25 19:49
emm 数据范围说一下

都是int范围内的

柿子饼同学

灯火阑珊201 发表于 2022-10-25 19:53
都是int范围内的

那 , 写一个线性筛 , 然后在 根号 n 范围下枚举每个素数判断一下吧...
好像只能想到这个

傻眼貓咪

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. unsigned isPrime(int num) {
   
5.         if (num < 2) return 0;
   
6.         else if (num == 2) return 1;
   
7.         for (int n = 2; n < sqrt(num) + .5; ++n) {
   
8.                 if (!(num % n)) return 0;
   
9.         }
   
10.         return 1;
    
11. }
    
12. 
    
13. unsigned isSemiprime(int num) {
    
14.         if (num < 2) return 0;
    
15.         for (int n = 2, a, b; n < sqrt(num) + .5; ++n) {
    
16.                 if (!(num % n)) {
    
17.                         a = n;
    
18.                         b = num / n;
    
19.                         if (isPrime(a) && isPrime(b)) return 1;
    
20.                 }
    
21.         }
    
22.         return 0;
    
23. }
    
24. 
    
25. int main(void) {
    
26.         for (int n = 0; n <= 20; ++n) {
    
27.                 isSemiprime(n) ? printf("%d is Semiprime\n", n) : printf("%d\n", n);
    
28.         }
    
29.         return 0;
    
30. }

复制代码

1. 0
   
2. 1
   
3. 2
   
4. 3
   
5. 4 is Semiprime
   
6. 5
   
7. 6 is Semiprime
   
8. 7
   
9. 8
   
10. 9 is Semiprime
    
11. 10 is Semiprime
    
12. 11
    
13. 12
    
14. 13
    
15. 14 is Semiprime
    
16. 15 is Semiprime
    
17. 16
    
18. 17
    
19. 18
    
20. 19
    
21. 20

复制代码

jackz007

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

复制代码

        编译运行实况：

1. D:\[00.Exerciese.2022]\C>g++ -o x x.c
   
2. 
   
3. D:\[00.Exerciese.2022]\C>x
   
4.     4     6     9    10    14    15    21    22    25    26
   
5.    33    34    35    38    39    46    49    51    55    57
   
6.    58    62    65    69    74    77    82    85    86    87
   
7.    91    93    94    95   106   111   115   118   119   121
   
8.   122   123   129   133   134   141   142   143   145   146
   
9.   155   158   159   161   166   169   177   178   183   185
   
10.   187   194   201   202   203   205   206   209   213   214
    
11.   215   217   218   219   221   226   235   237   247   249
    
12.   253   254   259   262   265   267   274   278   287   289
    
13.   291   295   298   299   301   302   303   305   309   314
    
14.   319   321   323   326   327   329   334   335   339   341
    
15.   346   355   358   361   362   365   371   377   381   382
    
16.   386   391   393   394   395   398   403   407   411   413
    
17.   415   417   422   427   437   445   446   447   451   453
    
18.   454   458   466   469   471   473   478   481   482   485
    
19.   489   493   497
    
20. D:\[00.Exerciese.2022]\C>

复制代码

灯火阑珊201

柿子饼同学 发表于 2022-10-25 20:13
那 , 写一个线性筛 , 然后在 根号 n 范围下枚举每个素数判断一下吧...
好像只能想到这个

谢谢啦，但是我按这种写的话超时了。。还是谢谢你

灯火阑珊201

傻眼貓咪 发表于 2022-10-25 20:27

谢谢大佬！！！

灯火阑珊201

jackz007 发表于 2022-10-25 20:28
编译运行实况：

谢谢大佬！！！！！！

柿子饼同学

灯火阑珊201 发表于 2022-10-25 21:03
谢谢啦，但是我按这种写的话超时了。。还是谢谢你

...你这就判断一个数?