C++求N以内所有的质数

时间:2022-10-14 11:02:49

有两种方法:筛选法和开根号法

 

筛选法:从小到大筛去一个已知素数的所有倍数。依次删除可被2整除,3整除。。。。的数字,剩下的则为素数 。

 

开根号法:如果一个数(>2),对这个数求平方根,如果这个数能被这个数的平方根到2之间的任何一个(只要有一人就行)整除说明就不是质数,如果不能就说明是质数!


原理:假如一个数N是合数,它有一个约数a,a×b=N,则a、b两个数中必有一个大于或等于根号N,一个小于或等于根号N。因此,只要小于或等于根号N的数(1除外)不能整除N,则N一定是素数。



#include <iostream>

#include <cmath>
using namespace std;
bool prime(int x)
{
     int y;
     for(y=2;y<=sqrt(x);y++)
         if (x%y==0)
            return false;
     return true;
}
int main ()
{
    int n,i;
    cin>>n;

    if(n>=2)
        cout<<"2 ";
    for(i=3;i<=n;i++)
        if (prime(i))
            cout<<i<<" ";

    return 0;
}

////////////                          //////////////////                                     /////////////


  1. /求n以内的素数  
  2. //素数又称质数,它是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。   
  3. //算法:筛选法,从小到大筛去一个已知素数的所有倍数。依次删除可被2整除,3整除。。。。的数字,剩下的则为素数   
  4. void getPrime0(int n){  
  5.      int i,j;  
  6.      bool m;  
  7.      for(i = 1; i <= n; i ++){  
  8.            m = true;  
  9.            for(j = 2; j < i; j ++){  
  10.                  if(i % j == 0){  
  11.                       m = false;  
  12.                       break;  
  13.                  }  
  14.            }  
  15.            if(m){  
  16.                  cout << i << " ";   
  17.            }  
  18.      }  
  19.      cout << endl;