21xrx.com
2024-11-25 03:18:44 Monday
登录
文章检索 我的文章 写文章
C++如何求质数
2023-07-05 07:42:34 深夜i     --     --
算法 循环 除法 最小质因数 筛法

C++是一种高级编程语言,广泛用于编写计算机程序,其中求质数是经常用到的一个算法。质数是指只能被1和本身整除的正整数,在数学和计算机科学领域都有着重要的应用。下面介绍C++如何求质数的方法。

1.暴力枚举法

暴力枚举法是最简单的一种求质数的方法,也是最慢的一种方法。其基本思想是对于每个大于1的正整数,分别用2到它自身的数去除,如果都不能整除,则这个数是质数。具体实现代码如下:

int is_prime(int n)

{

  if(n < 2) return 0;

  for(int i = 2; i < n; i++)

  {

    if(n % i == 0) return 0;

  }

  return 1;

}

2.优化算法

对于大于2的偶数,一定不是质数;对于大于3的奇数,可以只用检查是否被3到其平方根之间的奇数整除。具体实现代码如下:

int is_prime(int n)

{

  if(n < 2) return 0;

  if(n == 2 || n == 3) return 1;

  if(n % 2 == 0) return 0;

  for(int i = 3; i <= sqrt(n); i += 2)

  {

    if(n % i == 0) return 0;

  }

  return 1;

}

3.筛选法

筛选法是一种较快的求质数的方法,其基本思想是把从2开始的素数的倍数进行标记,从而剔除所有合数。具体实现代码如下:

void get_prime(int n)

{

  vector is_prime(n+1, true);

  is_prime[0] = is_prime[1] = false;

  for(int i = 2; i <= sqrt(n); i++)

  {

    if(is_prime[i])

    {

      for(int j = i*i; j <= n; j += i)

      {

        is_prime[j] = false;

      }

    }

  }

  for(int i = 2; i <= n; i++)

  {

    if(is_prime[i]) cout << i << ' ';

  }

}

以上三种方法都可以用于求质数,但各有优缺点,需要根据具体情况选择使用。值得一提的是,在面对更大的输入数据时,以上方法可能会出现性能瓶颈,需要采用更高效的算法,比如线性筛法等。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复