[已解决]半素数问题

灯火阑珊201

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

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

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-10-25 20:27:35

#include <stdio.h>
#include <math.h>

unsigned isPrime(int num) {
        if (num < 2) return 0;
        else if (num == 2) return 1;
        for (int n = 2; n < sqrt(num) + .5; ++n) {
                if (!(num % n)) return 0;
        }
        return 1;
}

unsigned isSemiprime(int num) {
        if (num < 2) return 0;
        for (int n = 2, a, b; n < sqrt(num) + .5; ++n) {
                if (!(num % n)) {
                        a = n;
                        b = num / n;
                        if (isPrime(a) && isPrime(b)) return 1;
                }
        }
        return 0;
}

int main(void) {
        for (int n = 0; n <= 20; ++n) {
                isSemiprime(n) ? printf("%d is Semiprime\n", n) : printf("%d\n", n);
        }
        return 0;
}

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

跳转到最佳答案楼层

柿子饼同学

emm 数据范围说一下

灯火阑珊201

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

都是int范围内的

柿子饼同学

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

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

傻眼貓咪

#include <stdio.h>
#include <math.h>

unsigned isPrime(int num) {
        if (num < 2) return 0;
        else if (num == 2) return 1;
        for (int n = 2; n < sqrt(num) + .5; ++n) {
                if (!(num % n)) return 0;
        }
        return 1;
}

unsigned isSemiprime(int num) {
        if (num < 2) return 0;
        for (int n = 2, a, b; n < sqrt(num) + .5; ++n) {
                if (!(num % n)) {
                        a = n;
                        b = num / n;
                        if (isPrime(a) && isPrime(b)) return 1;
                }
        }
        return 0;
}

int main(void) {
        for (int n = 0; n <= 20; ++n) {
                isSemiprime(n) ? printf("%d is Semiprime\n", n) : printf("%d\n", n);
        }
        return 0;
}

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

jackz007

#include <stdio.h>

int check(int n)
{
        int c , d , k , r                                   ;
        for(c = r = 0 , k = n , d = 2 ; d * d < k + 1 ;) {
                if(! (k % d)) {
                        k /= d                              ;
                        c ++                                ;
                } else {
                        d ++                                ;
                }
        }
        if(c == 1) r = 1                                    ;
        return r                                            ;
}

int main(void)
{
        int c , d , k                                       ;
        for(c = d = 0 ; d < 500 ; d ++) {
                if(check(d)) {
                        if(c) {
                                if(! (c % 10)) printf("\n") ;
                                else printf(" ")            ;
                        }
                        printf("%5d" , d)                   ;
                        c ++                                ;
                }
        }
}

        编译运行实况：

D:\[00.Exerciese.2022]\C>g++ -o x x.c

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

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