21xrx.com
2024-12-23 02:50:51 Monday
登录
文章检索 我的文章 写文章
C++程序判断素数:快速简洁的算法
2023-06-30 14:32:52 深夜i     --     --
C++ 程序 素数 算法 快速简洁

C++程序可以用来判断素数,而且有一些快速简洁的算法,可以让程序的判断速度更快。当然,首先需要了解什么是素数。

素数是只能被1和它本身整除的自然数,比如2、3、5、7、11、13等等,而1和任何非1的自然数不是素数。

那么,如何用C++程序来判断一个数是否为素数呢?以下是一些常见的算法。

1.暴力枚举法

这是最基本的算法,就是从2到n-1依次枚举n的因子,如果有一个因子能够整除n,则说明n不是素数。

C++程序实现方法:

bool is_prime(int n) {

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

    if (n % i == 0)

      return false;

  }

  return true;

}

2.优化枚举法

这种算法是在暴力枚举的基础上进行的一些优化,比如只需要枚举到根号n就可以了,因为如果n有因子大于根号n,那么它一定有一个因子小于根号n,另外也可以只枚举奇数。

C++程序实现方法:

bool is_prime(int n) {

  if (n == 2 || n == 3)

    return true;

  if (n == 1 || n % 2 == 0)

    return false;

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

    if (n % i == 0)

      return false;

  }

  return true;

}

3.埃氏筛法

这种算法的原理是,从2开始,把每个素数的倍数都标记成合数,以达到筛选素数的目的。

C++程序实现方法:

vector sieve(int n) {

  vector primes;

  vector is_prime(n + 1, true);

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

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

    if (is_prime[i]) {

      primes.push_back(i);

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

        is_prime[j] = false;

      }

    }

  }

  return primes;

}

以上就是一些判断素数的C++程序算法,可以根据具体需求选择不同的算法。

  
  

评论区

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