[已解决]半素数问题

灯火阑珊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

复制代码

跳转到最佳答案楼层

灯火阑珊201

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

都是int范围内的

灯火阑珊201

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

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

灯火阑珊201

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

谢谢大佬！！！

灯火阑珊201

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

谢谢大佬！！！！！！