21xrx.com
2024-11-08 22:10:16 Friday
登录
文章检索 我的文章 写文章
C++中如何表示素数
2023-06-26 18:17:32 深夜i     --     --
C++ prime number array loop algorithm

素数是指只能被1和自身整除的数,他们在数学中具有重要的应用。在C++中表示素数有不同的方法,下面我们将介绍一些常用的方法。

1.暴力枚举法

这是最简单的思路,从2到n-1枚举每个数,如果该数不能被1或者本身整除,则它就是一个素数。虽然这种方法很简单,但是他的时间复杂度很高,在大的n时速度将极慢。

2.试除法

试除法可以用一个数去除以小于它的数,如果都不能被整除,则它就是一个素数。这种方法相对于暴力枚举法减少了比较次数,但是时间复杂度依然很高。

3.埃氏筛法

埃氏筛法是一种更高效的方法,其基本思路是用一个数组记录从2开始到n的每个数,然后逐个筛选,将其倍数标记为非素数,最终留下的即为素数。具体实现可以用一个bool型数组,其中true表示该下标对应的数为素数,false表示不是素数。

4.欧拉筛法

欧拉筛法是一种更加高效的筛法算法,其基本思想是在埃氏筛法的基础上去重。具体实现可参考以下代码:

void euler()

{

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

    if (!vis[i]) {

      prime[++num] = i;

    }

    for (int j = 1; j <= num && i * prime[j] <= n; j++) {

      vis[i * prime[j]] = true; // 将i * prime[j]标记为不是素数

      if (i % prime[j] == 0)

        break;

    }

  }

}

其中,vis数组同样用于标记是否为素数,prime数组用于存储素数列表,num表示素数的数量。

总体而言,C++有许多方式可以表示素数,每个方法都有其优点和局限性,可以根据不同的需求选择不同的方法。

  
  

评论区

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