本文共 967 字，大约阅读时间需要 3 分钟。

一、半素数定义

        数学中，两个的乘积所得的自然数我们称之为半（也叫双，二次殆素数）开始的几个半素数是4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... 它们包含1及自己在内合共有3或4个因子。另外，合数并不一定是半素数，但半素数一定是合数。

二、判断方法（不拆分数，而选择查找数，思路很厉害了。）

题目：输入一个整数N，2<=N<=1000,000,判断N是否为半素数。

思路：1.先求出500000以内的素数（因为最小的素数为2），建立素数表，共41538个

           【素数的判定首先排除2以外的所有偶数，然后从奇数中排除素数的倍数，剩下的就是素数】；

           2.对输入的每个整数N，从2开始找它的因子i，如果i和N/i都能在素数表中查找到，则N是半素数。

具体实现：STL——vector & set，分别用来存储素数和半素数

采用vector存储素数有利于线性查找，在for循环中，可直接根据下标遍历素数表。

采用set存储半素数，是因为set是平衡检索二叉树，可以将元素自动排序，检索速度最快。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;vector
       
         v;set
        
          s;void ChoosePrime(int a,int b)//建立[a,b]范围内的素数表{ for(int i=a;i<=b;i++) { //2是素数，这里清楚2的倍数 if(i!=2&&i%2==0) continue; for(int j=3;j*j<=i;j+=2) { if(i%j==0) goto RL; } v.push_back(i); RL:continue; }}int main(){ ChoosePrime(2,500000);//建立[2,500000]范围内的素数表 int i,j,p; for(i=0;i