质数的求解方法

#质数的求解方法

一、质数

1.质数定义：一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）

二、方法

1.自定义函数求质数

代码如下（示例）：

bool cmp(int x){
   
    for(int i=2;i*i<=x;i++){
   
        if(x%i==0){
   
            return 0;
        }
    }
    return 1;
 }

2.筛选法求质数

大致思想：首先从2开始，依次去删除每个数的倍数
例求1-120内的质数
首先从2 开始，删除2的倍数
接下来删除3的倍数
删除4的倍数，此时4已经不存在了，因为在删2的倍数时，第一个就把4删除了
后续删除倍数的时候，需要先判断当前的数存不存在，如果存在则删除当前数的倍数，否则，删除下一个数
代码如下（示例）：

int prime[125]={
   0};//借用数组来进行筛选，赋初值为0，
//代表现在没有元素被删除
prime[1]=1;//1代表删除
for(int i=1;i<=120;i++){
   
    if(prime[i]==0){
   
       for(int j=i*2;j<=120;j+=2){
   
           prime[j]=1;
       }
    }
}
for(int i=2;i<=120;i++){
   
    if(prime[i]==0){
   
        cout<<i<<" ";
    }
}

总结

第2种方法也可以把所有的质数都存到一个新的数组中，这样避免每次都要去求一遍，以时间换空间