论坛 › C\C++交流 › 半素数问题

灯火阑珊201 发表于 2022-10-25 19:42:57

半素数问题

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

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

柿子饼同学 发表于 2022-10-25 19:49:57

emm 数据范围说一下

灯火阑珊201 发表于 2022-10-25 19:53:02

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

都是int范围内的

柿子饼同学 发表于 2022-10-25 20:13:03

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

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

傻眼貓咪 发表于 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

jackz007 发表于 2022-10-25 20:28:36

#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:\\C>g++ -o x x.c

D:\\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:\\C>

灯火阑珊201 发表于 2022-10-25 21:03:43

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

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

灯火阑珊201 发表于 2022-10-25 21:04:17

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


谢谢大佬！！！

灯火阑珊201 发表于 2022-10-25 21:04:48

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

谢谢大佬！！！！！！

柿子饼同学 发表于 2022-10-25 21:15:10

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

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

查看完整版本: 半素数问题