C语言判断一个数是否为素数方法解析

一、概念介绍

　　素数又称为质数。一个大于1的自然数（从2开始），除了1和它本身外，不能被其他自然数整除的叫做素数，否则称为合数。

　 0和1既不是素数也不是合数，最小的素数是2。

二、代码

方法一：

bool is_Prime(int num){
 int i;

 for(i = 2;i <= sqrt(num);i++){
  if(num % i == 0)//一旦发现有因子，则返回false
   return false;
 }
 return true;
}

注意：在for循环判断时不能忘记 i <= sqrt(num) 的等号，因为假设 p*p = n , n的因子是可以取到 sqrt(n) 的，如判断 9 是不是素数，如果没有等号会出现 9是素数，而实际上 9不是素数。

方法二：

关于质数分布的规律：大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等；

证明：令x≥1，将大于等于5的自然数表示如下：

··· 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ···

可以看到，不和6的倍数相邻的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。因此在5到sqrt(n)中每6个数只判断2个，时间复杂度O(sqrt(n)/3)。

在高配版和尊享版中，都是一个剪枝的思想，高配版中裁剪了不必要的偶数，尊享版中裁剪了不和6的倍数相邻的数，虽然都没有降低时间复杂度的阶数，但都一定程度上加快了判断的速度。

/*一种高效的方法*/
bool isPrime_3(int num){
 //两个较小数另外处理
 if(num == 2 || num == 3)
  return true;
 //不在6的倍数两侧的一定不是质数
 if(num % 6 != 1 && num % 6 != 5)
  return false;

 int i;
 //在6的倍数两侧的也可能不是质数
 for(i = 2;i <= sqrt(num);i += 6){
  if(num % i == 0 || num % (i + 2) == 0)
   return false;
 } 

 //排除所有，剩余的是质数
 return true;
}

三、测试

　　对负数与0，1进行异常处理

int main(){
 int num;
 bool result1,result2;

 printf("请输入一个正整数,以-1结束： ");
 scanf("%d",&num);
 while(num < 2 && num != -1){
  printf("输入不合法，请重新输入！（说明：素数必须大于1）\n");
  printf("请输入一个正整数，以-1结束： ");
  scanf("%d",&num);
 } 

 while(num >= 2 && num != -1){
  result1 = isPrime(num);
  result2 = isPrime_3(num);

  if(result1 == true)
   printf("%d 是素数\n",num);
  else if(result1 == false)
   printf("%d 不是素数\n",num);

  if(result2 == true)
   printf("%d 是素数\n\n",num);
  else if(result2 == false)
   printf("%d 不是素数\n\n",num);

  printf("请输入一个正整数，以-1结束： ");
  scanf("%d",&num);
  while(num < 2 && num != -1){
    printf("输入不合法，请重新输入！（说明：素数必须大于1）\n");
    printf("请输入一个正整数，以-1结束： ");
    scanf("%d",&num);
  }
 }
}

四、截图

到此这篇关于C语言判断一个数是否为素数方法的文章就介绍到这了,更多相关C语言判断一个数是否为素数内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 使用c语言判断100以内素数的示例(c语言求素数)

    从console输入一个数,判断这个数是否为素数(质数). 复制代码 代码如下: #include <stdio.h> /**判断100以内的素数*/ //定义函数判断是否是素数int isPrime(int num ){    int i;    //从2开始循环,一直到i的平方小于等于给定的数.    for (i = 2; i*i <= num; i++) {        if ( ( num % i ) == 0 ) {            return 0;       

  • C语言实现求梅森素数的代码与解析

    C语言实现求梅森素数的代码与解析

    问题描述 梅森数(Mersenne Prime)指的是形如2n-1的正整数,其中指数n是素数,即为Mn.如果一个梅森数是素数,则称其为梅森素数.例如22-1=3.23-1=7都是梅森素数. 当n=2,3,5,7时,Mn 都是素数,但n=11时,Mn=M11=211-1=2047=23X89,显然不是梅森素数. 1722年,瑞士数学大师欧拉证明了231-1=2147483647是一个素数,它共有10位数,成为当时世界上已知的最大素数. 迄今为止,人类仅发现了47个梅森素数.梅森素数历来都是数论研究

  • C语言实现的统计素数并求和代码分享

    题目来源于PAT平台,此题又是费了一番脑子.题目要求输出给定区间内的素数个数并对他们求和.具体思路是利用循环判断素数,将结果传递给控制变量,由控制变量再来判断是否执行自增以及求和.当然这里必须要注意1既不是素数也不是合数. 下面是代码: 复制代码 代码如下: #include <stdio.h> int main () {  int a=0,b=0;  int n=0,sum=0;  int x=0,i=0;  scanf("%d %d",&a,&b);  

  • c语言判断是否素数程序代码

    复制代码 代码如下: #include <stdio.h> bool isPrimeNum(int x){    if (x == 1)        return false;    else if (x <= 0)        return false;    else if (x == 2)        return true;    else    {        for (int i = 2; i < x; i++)        {            if (

  • C语言判断一个数是否为素数方法解析

    一.概念介绍 素数又称为质数.一个大于1的自然数(从2开始),除了1和它本身外,不能被其他自然数整除的叫做素数,否则称为合数. 0和1既不是素数也不是合数,最小的素数是2. 二.代码 方法一: bool is_Prime(int num){ int i; for(i = 2;i <= sqrt(num);i++){ if(num % i == 0)//一旦发现有因子,则返回false return false; } return true; } 注意:在for循环判断时不能忘记 i <= sq

  • java如何判断一个数是否是素数(质数)

    目录 java判断一个数是否是素数(质数) 质数(prime number)又称素数,有无限个 思路 java 求1-100之间的质数 质数定义: 1.质数实例一 2.质数实例二 3.质数实例三 4.质数实例四 5.质数实例五 6.质数实例六 java判断一个数是否是素数(质数) 质数(prime number)又称素数,有无限个 质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数,这样的数称为质数. import java.util.Scanner; public class Te

  • Go语言判断指定文件是否存在的方法

    本文实例讲述了Go语言判断指定文件是否存在的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: package main    import (     "fmt"     "os" )    func main() {     f, err := os.Open("dotcoo.com.txt")     if err != nil && os.IsNotExist(err) {         fmt.Pri

  • C语言判断一个数是否是2的幂次方或4的幂次方

    快速判断一个数是否是2的幂次方,若是,并判断出来是多少次方! 将2的幂次方写成二进制形式后,很容易就会发现有一个特点:二进制中只有一个1,并且1后面跟了n个0: 因此问题可以转化为判断1后面是否跟了n个0就可以了. 如果将这个数减去1后会发现,仅有的那个1会变为0,而原来的那n个0会变为1:因此将原来的数与去减去1后的数字进行与运算后会发现为零. 最快速的方法: (number & number - 1) == 0 原因:因为2的N次方换算是二进制为10--0这样的形式(0除外).与上自己-1的

  • C语言判断数是否为素数与素数输出

    C语言判断数是否为素数与素数输出

    目录 1.判断单个数是否为素数(多组输入) 2.输入范围输出范围内的素数 3.总结 素数的概念:素数也叫质数,是一种只能被自己本身和1整除的数并且大于1,当然0与1不是素数. 1.判断单个数是否为素数(多组输入) 我的思路是,首先输入一个数,利用素数的概念来判断是非为素数,是的话输出素数:否则不输出. 关于素数的判断首先我们吧输入的数当初被除数,我选择用一个for循环来实现,从2开始当除数,每轮加1,一直循环去除被除数,一直除到被除数减一那个数,要是期间能被一个数整除则跳出循环不为素数,要是一直

  • C语言实现统计100以内所有素数的个数

    C语言实现统计100以内所有素数的个数

    目录 题目描述 分析 代码实现 运行结果 后期完善 网上参考 本人C语言萌新,最近工作中频频出现C语言小错误,遂决定使用笨方法提高我的C语言水平,坚持每天一个C语言小练习,养成C语言手感,从此让编程成为习惯. 题目描述 统计100以内所有素数的个数 分析 素数(prime number)又称质数,在大于1的自然数中,除了1和它本身以外不再有其他因数的数称为质数,2是最小的素数. 代码实现 #include <stdio.h> #define INTEGER_RANGE 100 //数字范围 i

  • 判断一个数是不是素数的方法

    给出一个数,判断这个数是不是素数: 复制代码 代码如下: #include <cmath> bool isPrime(int n) {  int i;  for (i = 2; i <= sqrt(n); i++) {    if (n % i == 0)      return false;  }  return true;}

  • ruby判断一个数是否为质数(素数)示例

    ruby判断一个数是否为质数 质数又称素数.一个大于1的自然数,如果除了1和它自身外,不能被其他自然数整除的数:(除0以外)否则称为合数 .根据算术基本定理,每一个比1大的整数,要么本身是一个质数,要么可以写成一系列质数的乘积:而且如果不考虑这些质数在乘积中的顺序,那么写出来的形式是唯一的. 复制代码 代码如下: def prime?(num)  res = [1]  res << num if num == 0 || num == 1    return false  end 2.upto(

  • C++如何判断一个数是不是素数

    目录 如何判断一个数是不是素数 思路 实现代码 快速判断一个数是不是素数(质数) 朴素的方法 下面介绍一个更快的方法 如何判断一个数是不是素数 题目:判断一个数是不是素数,1 < N <= 50000 思路 判断n是否整除(求余是否等于0)大于1而小于sqrt(n)中的任何一个数,如果有则不是素数,否则是素数 实现代码 // 判断一个数是不是素数,1 < N <= 50000 #include <iostream> #include <cmath> usin

随机推荐