素数是指只有两个正因数（1和自身）的数，如2、3、5、7等。在计算机科学中，判断一个数是否为素数的算法是一个基本问题。下面介绍几种C++判断素数的方法。

1. 直接判断法

根据素数的定义，一个数如果除了1和它本身，再没有其他约数，那么这个数就是素数。因此，我们可以从2开始到n-1，一个个试除，看是否能被整除。如果都不能整除，那么这个数就是素数。

bool isPrime(int n) {

  if (n <= 1) return false;

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

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

  }

  return true;

}

2. 埃拉托斯特尼筛法

埃拉托斯特尼筛法（Sievers of Eratosthenes）是一种较为高效的筛出素数的方法。它的原理是，从2开始，将每个素数的倍数都标记成合数，以便后面的筛选。在筛选过程中，只需保留未被标记的数，它们就是素数。

bool isPrime(int n) {

  if (n <= 1) return false;

  bool is_prime[n+1];

  memset(is_prime, true, sizeof(is_prime));

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

    if (is_prime[i]) {

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

        is_prime[j] = false;

      }

    }

  }

  return is_prime[n];

}

3. 米勒-拉宾素性检验

米勒-拉宾素性检验是一种基于费马小定理的概率算法，可以判断一个数是否为素数。该算法的核心是判断n-1是否满足2^s * d的形式，其中d为奇数，s为正整数。如果n-1不满足这个条件，那么n一定不是素数。否则，选取一个2到n-2之间的随机数a，进行递归计算。如果结果为1或n-1，则n可能是素数，否则n一定不是素数。可以通过多次测试来提高算法的正确性。

bool isPrime(int n) {

  if (n <= 1) return false;

  if (n <= 3) return true;

  int d = n - 1, s = 0;

  while (d % 2 == 0) {

    d /= 2;

    s++;

  }

  for (int i = 0; i < 10; i++) {

    int a = rand() % (n - 2) + 2;

    int x = powMod(a, d, n);

    if (x == 1 || x == n - 1) continue;

    for (int j = 1; j < s; j++) {

      x = powMod(x, 2, n);

      if (x == n - 1) break;

    }

    if (x != n - 1) return false;

  }

  return true;

}

相似文章
• C++ 求平均值
  C++是一种流行的编程语言，用于编写许多不同类型的应用程序。其中一个常见的任务是计算一个数列的平均值。下面介绍如何使用C++编写一个简单的程序来计算平均值。
  
  
• C++排序题目
  C++排序题目是编程领域内经典的问题之一，它要求程序员通过编写C++代码实现对一组数据进行排序的功能。排序算法的实现是程序员们接触的第一个最基本的算法之一，它可以运用于各种数据处理和优化中。本篇文章将介绍C++排序题目的背景和实现方法。
  
  
• C++计算机程序设计
  C++是一种高级计算机编程语言，被广泛应用于计算机程序设计。C++是C语言的扩展版本，它通过添加一些新的特性使得程序的编写更加方便，同时也使程序的执行效率得到了明显的提高。
  
  
• 《数据结构与算法分析C++第二版》课后习题答案
  《数据结构与算法分析C++第二版》是一本经典的计算机科学教材，在其中练习习题是成为一个优秀程序员的关键。这本教材的课后习题非常充实和繁多，对于学习者来说很有价值。下面是一些《数据结构与算法分析C++第二版》课后习题答案的介绍。
  
  
• C++算法竞赛
  C++算法竞赛是一项非常热门的竞技项目，在计算机专业中得到了广泛的关注和认可。通过这项竞技，既可以提高学生们的算法和程序设计水平，又可以培养他们的团队合作能力和创新意识。
  
  
• C++实现矩阵乘法
  矩阵乘法是一种计算矩阵之间的乘法的方法，是线性代数中的重要知识点之一。在计算机科学中，可以使用C++语言来实现矩阵乘法。
  
  
• C++ 去除空格
  C++是一门高级编程语言，在实际项目研发中，我们经常需要对字符串中的空格进行去除或替换操作，因为空格的存在可能会影响字符串的处理或展现效果。在本文中，我们将介绍C++中去除空格的几种方法。
  
  
• C++如何判断一个数列是否为等差数列
  等差数列是指数列中相邻的两项之间的公差相等的数列。在C++中，判断一个数列是否为等差数列可以通过以下方法实现。
  
  
• C++数据结构和算法
  C++是一门广泛应用于计算机科学和编程领域的高级编程语言。它是一种面向对象的语言，并提供了许多强大的编程语法，使得它成为开发优秀应用程序的理想工具。
  
  
• C++的最大公约数函数
  C++是一种广泛使用的编程语言，它可以用来解决各种问题。其中之一就是求最大公约数。C++提供了一个函数gcd()用于计算最大公约数。
  
  
• Java 数据分类算法简介
  Java数据分类算法是机器学习中的一个重要分支，旨在将数据按照特定的类别进行分类，让计算机能够根据已有数据的特征和规律来预测新的数据所属的类别。下面我们来简单介绍几种常用的Java数据分类算法。
  
  
• C++连连看代码
  C++连连看是一种经典的休闲游戏，其核心玩法就是通过连接两个相同的图案，从而使它们从游戏界面中消失。为了实现这个功能，我们需要对游戏的界面、图案以及玩家的操作进行代码实现。
  
  
• 数据结构与算法C++实现
  数据结构和算法的实现对于计算机科学和信息技术的学习者来说至关重要。在实践中，C++是最为广泛使用的程序设计语言之一，因此学会如何在C++中实现数据结构和算法是非常有意义的。
  
  
• 如何用C++编程判断一个数是否为素数
  素数是指除了1和自身外，不能被其他正整数整除的正整数。在计算机编程中，判断一个数是否为素数是一道经典的问题，本文将介绍如何使用C++编程实现这个功能。
  
  
• C++简单算法入门
  C++是目前业界应用最广泛的编程语言之一，它的应用范围非常广泛，其中最重要的一项就是在算法和数据结构的实现上。C++中包含了丰富的库函数和标准模板库，可以极大地简化算法的实现过程。
  
  
• C++ 实现一个数的次方
  C++语言是一种广泛应用于编程领域的高级语言，具有丰富的数据类型和面向对象编程思想，支持多种基本操作，例如算术运算、比较运算、逻辑运算等。在C++中，我们可以利用内置数据类型实现各种功能，包括计算数的次方。
  
  
• C++语言中素数的表达方式
  C++语言中是通过代码实现素数的生成和判断。素数是一种只能被1和自身整除的正整数，如2、3、5、7等。素数在密码学、计算机程序设计等方面具有重要作用，因此在C++语言中实现素数是很有必要的。
  
  
• C++分糖果1
  C++分糖果1是一道经典的算法题，常见于笔试和面试中，涉及到的核心内容为数组的运用。该问题的大意为：假设有n个孩子站成一列，每个孩子手中有一颗糖果，现在需要把糖果分给孩子们，要求糖果数量相同，且分到的糖果数最少，问最少需要分几颗糖果。
  
  
• C++算法的基本结构简介
  C++算法是指通过C++编程语言实现的一系列计算过程，这些计算过程旨在解决实际问题。C++算法涉及很多方面，如数组、字符串、排序、搜索、解析等，而每种算法都有其独特的结构和实现方法。
  
  
• C++特殊求和算法
  C++是一种高级编程语言，用于开发各种应用程序和软件，具有许多高级功能和算法，其中之一是特殊求和算法。C++特殊求和算法是一种高级算法，用于对一组数字进行求和。
  
  
• 《数据结构算法与应用C++语言描述》PDF
  《数据结构算法与应用C++语言描述》PDF是一本非常经典而且实用的书籍，它对于学习和掌握数据结构算法有着非常重要的作用。本书的作者是郝斌，他曾教授过很多计算机专业的学生，具有非常丰富的教学经验和实战经验。
  
  
• C++数据结构与算法
  C++是一门流行的编程语言，用于开发各种应用程序和系统。它有许多数据结构和算法的库可供使用，这些库可以帮助开发人员更容易地实现复杂的功能。C++数据结构和算法是计算机科学中的关键主题之一，因为它们与计算机程序的效率和性能密切相关。
  
  
• C++数据结构」的含义是什么？
  C++数据结构是指在C++编程语言中用于存储和组织数据的不同方式和方法。数据结构是软件开发中的一个重要概念，它强调了数据的组织方式以及如何访问和操作这些数据。
  
  
• C++编程：求一个数的所有因子
  在数学里，因子指的是能够整除另一个数的数，也就是除了1和这个数本身以外的数。对于一个数，求出它的所有因子是一个比较基础但相当重要的问题。而在C++编程中，我们可以通过一些简单的代码来实现求一个数的所有因子的功能。
  
  
• C++如何从容器中删除重复元素
  C++作为一种常用的编程语言，它提供了许多容器来存储和操作数据。然而，有时候我们需要从容器中删除重复的元素，这对于数组和基本数据类型非常简单，但是对于容器的操作则有些麻烦。本文将介绍如何使用C++从容器中删除重复元素。
  
  
• 数据结构算法与应用c++第二版答案：全面解读数据结构及算法实现
  《数据结构算法与应用c++第二版答案》是一本全面解读数据结构及算法实现的书籍。本书的作者是严蔚敏和吴伟民，两位作者都是著名的计算机教育家，拥有多年的教学和研究经验。本书作为一本解答数据结构算法问题的辅助书籍，旨在帮助读者更深入地理解和掌握数
  
  
• 如何在c++中去除重复的数字
  在c++中，为了去除重复的数字，我们可以采用以下两种方法：使用set容器或自建函数。
  
  
• 使用C++语言冒泡排序算法将10个数升序排列
  冒泡排序是最经典的排序算法之一，它的基本思想是从待排序的数列中，依次比较相邻的两个数大小，根据比较结果，按照升序或降序交换相邻的位置，这样进行多次比较后，最大/最小的数会逐步移动到数列的末端/起始端，从而达到排序的目的。
  
  
• C++或Python，哪一个更适合使用算法？
  C++和Python都是非常流行的编程语言，它们在不同的领域中都有广泛的应用。然而，在涉及到算法的情况下，哪一种编程语言更适合使用呢？
  
  
• C++如何求整数长度？
  C++是一种广泛使用的编程语言，它提供了一系列的数学运算和算法，方便程序员在编码的过程中进行数字的计算和处理。其中，一个常见的问题就是如何求某个整数的长度，下面将从几个不同的角度来探讨这个问题。
  
  
• C++如何求最大公约数
  C++语言是一种高效且广泛应用的编程语言，在实际编程中常常需要使用到最大公约数（Greatest
  
  
• C++开发面试常见问题
  C++是一种功能强大的编程语言，应用广泛，特别是在软件开发方面。如果你想进入C++开发领域，你需要经历一些面试，这些面试可能涉及一些常见问题。下面是C++开发面试中常见的一些问题。
  
  
• C++进度条百分比算法
  在实现数据处理等任务时，我们经常需要展示进度条来告诉用户任务的执行进度，而进度条通常会显示百分比。在C++中，要实现一个进度条百分比算法并不是很难，下面就让我们来学习一下具体实现方法。
  
  
• Node.js加密算法简介
  Node.js是一个基于Chrome
  
  
• C++数据结构与算法习题集
  如果你正在学习C++编程语言，并且想系统地学习数据结构和算法，那么选择一本好的习题集非常重要。
  
  
• C++算法题目分类求和
  C++是一种广泛使用的编程语言，它可以用来解决各种算法问题。针对不同的问题类型，C++算法题目也可以被分成多个类别。本文将介绍一些常见的C++算法题目分类，并进行求和计算。
  
  
• 如何用C++计算视频的PSNR
  对于视频处理的相关工作，计算图像质量指标是很重要的一环。PSNR（peak
  
  
• Java编程：求解某一范围内的质数
  在日常编程中，求解某一范围内的质数是一项比较常见的任务。而Java作为一种流行的编程语言，也有自己独特的方法来实现这个目标。
  
  
• C++中如何找到素数
  C++是一种强大的编程语言，它被广泛应用于许多领域，包括计算机科学、工业、医学、金融等。在C++中，找到素数是一项基本的编程任务。素数是指只能被1和自身整除的数。在C++中，我们可以使用以下方法找到素数。
  
  
• 如何使用C++ STL
  C++
  
  
• 用C++如何判断一个数是否为素数？
  素数是指只能被1和它本身整除的正整数，例如2、3、5、7等。在许多算法中，需要对给定的数字进行素数判断，C++是一种流行的编程语言，可以使用C++编写程序来判断一个数是否为素数。
  
  
• C++如何求复数的绝对值？
  C++是一种广泛用于开发各种应用的高级编程语言，也可以用来求解复数的各种运算，包括求复数的绝对值。复数是由实部和虚部组成的数学对象，其绝对值代表了其与原点的距离。
  
  
• C++实现回文数判断的算法
  回文数是指正读和反读都一样的数，例如121、111、2332等。在计算机编程中，回文数判断是一项常见的算法问题，同样也是很多面试问题的经典题目。下面介绍一下用C++实现判断回文数的算法。
  
  
• 《数据结构算法与应用C++语言描述答案PDF》
  《数据结构算法与应用C++语言描述答案PDF》是一本涉及计算机科学领域的著作，编写者主要是针对C++语言所编写的数据结构与算法的应用及练习题的解答。该书主要分为两部分，第一部分为一些理论知识的介绍和讲解，第二部分则是涉及应用的练习题答案。
  
  
• Java与C++在编写算法上的区别
  Java和C++都是广泛使用的编程语言，但在编写算法方面具有不同的特点。
  
  
• C++ 快速排序算法详解
  快速排序算法是一种常用的排序算法，它使用分治的思想来快速排序一个序列。C++语言提供了强大的工具来实现这个算法。本文将详细介绍C++快速排序算法的实现过程，帮助读者理解和掌握这个重要的算法。
  
  
• 学习数据结构与算法是否需要掌握C++？
  学习数据结构与算法是程序员必不可少的一门技能，然而对于初学者来说，是否需要掌握C++语言呢？这是一个有争议的话题。
  
  
• 《C++算法入门书》
  C++算法入门书是一本非常适合初学者的书籍，它主要讲解了C++语言中常见的算法和数据结构，包括数组、链表、栈、队列、树等等。
  
  
• 《C++数据结构与算法pdf》
  《C++数据结构与算法pdf》是一本帮助程序员更好的掌握C++编程语言和数据结构算法的电子书。这本书可以帮助学习者更好的了解C++编程语言中的数据结构和算法原理，帮助他们打下坚实的编程基础。
  
  
• C++程序设计报告
  本报告旨在总结C++程序设计的过程和经验，包括项目的需求分析、系统架构设计、编程实现、测试调试以及性能优化等方面的内容。
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政