C语言中判断素数(求素数)的思路与方法实例

目录
  • 前言
  • 思路1实现：
  • 思路2实现：
  • 《C与指针》4.14-2:
  • 补充：判断素数的4种方法实例
  • 总结

前言

素数又称质数。所谓素数是指除了 1 和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被 2~16 的任一整数整除。

思路1)：因此判断一个整数m是否是素数，只需把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。

思路2)：判断方法还可以简化。m 不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~  之间的每一个整数去除就可以了。如果 m 不能被 2 ~  间任一整数整除，m 必定是素数。例如判别 17 是是否为素数，只需使 17 被 2~4 之间的每一个整数去除，由于都不能整除，可以判定 17 是素数。

原因：因为如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于 ，另一个大于或等于 。例如 16 能被 2、4、8 整除，16=2*8，2 小于 4，8 大于 4，16=4*4，4=√16，因此只需判定在 2~4 之间有无因子即可。

思路1实现：

#include <stdio.h>
int main() {
    int n;
    printf("请输入一个1-100之间的整数：\n");
    scanf("%d", &n);

    int m = 0;
    for (int i = 2; i < n; i++ ) {
        if(n % i  == 0) {
            m++;
        }
    }
    if (m == 0) {
        printf("%d是素数\n", n);
    } else {
        printf("%d不是素数\n", n);
    }
    return 0;
}

思路2实现：

#include <stdio.h>
#include <math.h>
int main() {
    int n;
    printf("请输入一个1-100之间的整数：\n");
    scanf("%d", &n);

    int i = 0;
    int q = sqrt(n);
    for (i = 2; i <= q; i++ ) {
        if(n % i  == 0) {
            break;
        }
    }
    if (i > q) {
        printf("%d是素数\n", n);
    } else {
        printf("%d不是素数\n", n);
    }

    return 0;
}

《C与指针》4.14 - 2:

打印1~100之间所有质数：

#include <stdio.h>
int main() {
    int num, divisor;
    printf("1, 2");
    for (num = 3; num <= 100; num += 2) {
        for(divisor = 3; divisor < num; divisor +=2 ) {
            if (num % divisor == 0) {
                break;
            }
        }

        if(divisor >= num) {
            printf(", %d", num);
        }
    }
    printf("\n");
    return 0;
}

结果：

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

补充：判断素数的4种方法实例

#include<stdio.h>
#include<math.h>
//方法一：从1-n挨个判断；
 bool isPrimel_1(int n)
{	for(int i=2;i<n;i++)
	if(n%i==0)
	return false;
	return true;
}

//方法二： 将被判断数n，进行开方作为判断结束的条件，
//因为开方后的数，是n的最大因子，最大因子之后的数对判断该数是否是素数没有意义。

bool isPrimel_2(int n)
{	for(int i=2;i<sqrt(n);i++)
	if(n%i==0)
	return false;
	return true;
}

//方法三: 只需要判断到该数的一半即可，如果超过它本身的一半,
//进行求余的结果将永远不会为0，除非是该数对该数的求余。

bool isPrimel_3(int n)
{   int i;
    if(n%2==0)
    return 0;
    for(i=3;i=n/2;i+=2){
	 if(n%i==0)
     return 0;
     return 1;
}
}

 //方法四:从3-n,只判断奇数，先对一个数进行奇偶判断，若是奇数，
 //只对从3到它本身的奇数进行求余计算，同理若是偶数，一定不是素数。

bool isPrimel_4(int n)
{   int i,j=1;
    if(n%2==0)
    return 0;
    else{
    for(i=3;i<=n;i=i+2){
	 if(n%i==0)
	 j=i;
	 break;
	}
}
   if(j==n)
   return 0;
   return 1;
}

int  main()
{
	int n;
	printf("请输入一个数：");
	scanf("%d",&n);
	printf("%d,%d,%d,%d\n",isPrimel_1(n),isPrimel_2(n),isPrimel_3(n),isPrimel_4(n));
	return 0;
}

总结

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

赞 (0)

相关推荐

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

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

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

  • 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语言判断一个数是否为素数方法解析

    一.概念介绍 素数又称为质数.一个大于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

  • 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.输入格式: 3输出格式: 1.题目内容: 孪生素数是指间隔为 2 的相邻素数,例如最小的孪生素数对是3和5,5和7也是(5虽重复但算作2组). 2.输入格式: 输入N,找出2至N之间的孪生素数的组数. 这里要注意输入的N不要超过int表示的最大范围了 3输出格式: 输出2至N之间的孪生素数,然后输出组数. 代码如下: #include<stdio.h> int Function(int n)//函数判断是否为素数 {     for (int i=2; i<n;

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

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

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

  • C语言练习之数组中素数交换

    C语言练习之数组中素数交换

    目录 题目要求 总结 题目要求 (1)在主函数中创建数组num,使用测试数据{108 4 19 7 23 66 49 13 33 35}对其初始化: (2)定义change函数,将num数组中的素数首尾交换,即第一个素数与最后一个素数交换,第二个素数与倒数第二个素数交换-,非素数保持位置不变: (3)定义prime函数,用于素数的判断. #include <stdio.h> #include <math.h> int prime(int num) { int i,k; if(num

  • 使用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语言中判断素数(求素数)的思路与方法实例

    目录 前言 思路1实现: 思路2实现: <C与指针>4.14-2: 补充:判断素数的4种方法实例 总结 前言 素数又称质数.所谓素数是指除了 1 和它本身以外,不能被任何整数整除的数,例如17就是素数,因为它不能被 2~16 的任一整数整除. 思路1):因此判断一个整数m是否是素数,只需把 m 被 2 ~ m-1 之间的每一个整数去除,如果都不能被整除,那么 m 就是一个素数. 思路2):判断方法还可以简化.m 不必被 2 ~ m-1 之间的每一个整数去除,只需被 2 ~  之间的每一个整数去

  • C语言如何使用函数求素数和举例

    本题要求实现一个判断素数的简单函数.以及利用该函数计算给定区间内素数和的函数.素数就是只能被1和自身整除的正整数. 注意:1不是素数,2是素数. 函数接口定义: int prime( int p ); int PrimeSum( int m, int n ); 其中函数prime当用户传入参数p为素数时返回1,否则返回0:函数PrimeSum返回区间[m, n]内所有素数的和.题目保证用户传入的参数m≤n. 裁判测试程序样例: #include <stdio.h> #include <m

  • C语言中判断两个IPv4地址是否属于同一个子网的代码

    问题描述: 现给定两个IPv4地址,和一个子网掩码,判断是否属于同一个子网,若属于,输出1,否则输出0. 例如输入: 172.16.1.3 172.16.1.35 255.255.255.224 输出: 0 解决方案: 首先将字符串格式的IP地址转化为4字节的IP地址,然后使用与(&)运算,分别将两个IP地址与掩码相与,若最后的值相同,则为同一个子网,否则不是. 以下函数的作用是将字符串格式的IP转化为4字节的IP(因为是4字节,所以使用int,但不同平台的int所占的字节好像不同哈~不太确定)

  • C语言中判断一个char*是不是utf8编码

    C语言中判断一个char*是不是utf8编码 里我修改了一下, 纯ASCII编码的字符串也返回true, 因为UTF8和ASCII兼容 实例代码: int utf8_check(const char* str, size_t length) { size_t i; int nBytes; unsigned char chr; i = 0; nBytes = 0; while (i < length) { chr = *(str + i); if (nBytes == 0) { //计算字节数 i

  • 浅谈C/C++ 语言中的表达式求值

    经常可以在一些讨论组里看到下面的提问:"谁知道下面C语句给n赋什么值?" m = 1; n = m+++m++; 最近有位不相识的朋友发email给我,问为什么在某个C++系统里,下面表达式打印出两个4,而不是4和5: a = 4; cout << a++ << a; C++ 不是规定 << 操作左结合吗?是C++ 书上写错了,还是这个系统的实现有问题? 注:运行a = 4; cout << a++ << a; 如在Visua

  • jsp页面中表达式语言中的$符号不起作用的解决方法

    今天myeclipse里部署了之前做的一个测试项目,发现jsp里的$符号tomcat启动后页面上显示出来了,百度搜了下别人也有类似的问题出现过.经提醒原来是web.xml配置的version设置的是2.5而我tomcat5启动的.是tomcat的版本低于web的版本,从而导致$符号不能正常使用. 后将tomcat5改用tomcat6.jdk采用1.6 启动spring2.5项目.$显示问题解决. 以下是网上摘录的详细说明: 在jsp页面中用表达式语言中的$符号,如${pageScope.titl

  • C语言中实现“17进制”转“10进制”实例代码

    C语言中实现“17进制”转“10进制”实例代码

    C语言中实现"17进制"转"10进制"实例代码 17进制转成10进制,输入是数字跟大写字母.例如输入G.11.FF,分别输出16.18.270 #include <iostream> #include <string> using namespace std; int main() { string s; int len,factor=17,num; bool sign;//用来标志输入字符串是否非法 while(cin>>s)

  • Pytorch中的自动求梯度机制和Variable类实例

    自动求导机制是每一个深度学习框架中重要的性质,免去了手动计算导数,下面用代码介绍并举例说明Pytorch的自动求导机制. 首先介绍Variable,Variable是对Tensor的一个封装,操作和Tensor是一样的,但是每个Variable都有三个属性:Varibale的Tensor本身的.data,对应Tensor的梯度.grad,以及这个Variable是通过什么方式得到的.grad_fn,根据最新消息,在pytorch0.4更新后,torch和torch.autograd.Variab

  • linux shell 中判断文件、目录是否存在的方法

    本文主要介绍了linux shell 中判断文件.目录是否存在的方法,分享给大家 -e filename 如果 filename存在,则为真 -d filename 如果 filename为目录,则为真 -f filename 如果 filename为常规文件,则为真 -L filename 如果 filename为符号链接,则为真 -r filename 如果 filename可读,则为真 -w filename 如果 filename可写,则为真 -x filename 如果 filenam

  • 小项目中管理npm包版本的思路与方法

    背景 笔者在最近碰到一个问题: 有一些项目没有类似jenkins的自动部署平台,前端部署都是本地执行npm run build命令生成压缩包,然后放到服务器上面,解压到nginx 目录, 但是有的时候遇到一个问题,比如项目中某个成员升级了其他组写的一个组件packageA,但是其他成员可能没有升级,导致上线后就会有一些问题,一个包还好,如果有好几个包都没有升级,那么可能导致一些意想不到的问题. 思路 首先就这个问题,我思考后有以下几个问题 package.json中的包名的版本有几个是用的^x.

随机推荐