精华内容
下载资源
问答
  • c语言求素数
    万次阅读 多人点赞
    2018-08-17 10:30:00

    质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。

    /*求素数的三种方法
    一:for(i=2;i<=(n-1);i++)
    if(n%i==0)i在2到n-1之间任取一个数,如果n能被整除则不是素数,否则就是素数

    #include <stdio.h>
    void main(){
    	int i,n;
    	printf("Please input: ");
    	scanf("%d",&n);
    	for(i=2;i<=n-1;i++){
    		if(n%i==0){
    			break;
    		}
    	}
    	if(i>=n){
    		printf("This is a prime!\n");
    	}
    	else{
    		printf("This is not a prime!\n");
    	}
    }

    二:for(i=2;i<=n/2;i++)
    if(n%i==0) /*i在2到n/2之间任取一个数,如果n能被整除则不是素数,否则就是素数

    #include "stdio.h"
    void main(){
    	int n,i;
    	printf("Please input numbers: ");
    	scanf("%d",&n);
    	for(i=2;i<=n/2;i++){
    		if(n%i==0){
    			printf("This is not a prime!\n");
    			break;
    		}
    	}
    	if(i==n/2+1){
    		printf("This is a prime!\n");
    	}
    }

    三:for(i=2;i<=j;i++)
    if(n%i==0) /*i在2到sqrt(n)之间任取一个数,如果n能被整除则不是素数,否则就是素数

    #include "stdio.h"
    #include <math.h>
    void main(){
        int i,j,n;
        printf("Please input numbers: ");
        scanf("%d",&n);
        j=(int)sqrt(n);
        for(i=2;i<=j;i++){
            if(n%i==0){
                break;
            }
        }
        if(j<i){
            printf("%d is prime!\n",n);
        }
        else{
            printf("%d is not prime!\n",n);
        }
    }

    这是本博主通过学习素数,也通过一些资料查找,总结的三种输出素数的代码,如果大家在学习的过程中有不懂得请关注我的博客,后续会为大家继续推出一些学习方法。

    接下来小编在为大家推出1-100之间的素数,代码如下:

    #include <stdio.h> 
    #include <math.h>
    int prime(int n);
    void main(){
    	int i=0,k=0;
    	int count=0;
    	printf("1-100之间的素数从小到大为: \n");
    	for(i=2;i<100;i++){
    		if(prime(i)){
    			count++;
    	        k++;
    			printf("%d\t", i);
    			if(k%5==0){
    					printf("\n");				
    			}
    		}
    	}
    	printf("\n一共有:%d个\n", count);
    }
    int prime(int n){
    	int i=0;
    	for(i=2;i<=sqrt(n);i++){
    		if(n%i==0){
    			return 0;
    		}		
    	}
    	return 1;
    }

     

    版权声明:本文为博主原创文章,未经博主允许不得转载。https://blog.csdn.net/qq_42680327

    更多相关内容
  • 101-200之间的素数; 初学C语言的时候写的程序,写的可能不是很好,但我觉得小白比较能接受,算法很简单。希望可以帮到正在看的你
  • 主要介绍了使用c语言判断100以内素数的示例(c语言求素数),需要的朋友可以参考下
  • c语言求素数

    千次阅读 2021-09-25 15:26:13
    /*求素数的三种方法 一:for(i=2;i<=(n-1);i++) if(n%i==0)i在2到n-1之间任取一个数,如果n能被整除则不是素数,否则就是素数 二:for(i=2;i<n/2;i++) if(n%i==0) /*i在2到n/2之间任取一个数,如果n能被整除...
    /*求素数的三种方法
    一:for(i=2;i<=(n-1);i++)
    if(n%i==0)i在2到n-1之间任取一个数,如果n能被整除则不是素数,否则就是素数
    二:for(i=2;i<n/2;i++)
    if(n%i==0) /*i在2到n/2之间任取一个数,如果n能被整除则不是素数,否则就是素数
     
    三:for(i=2;i<(n=sqrt(n));i++)
    if(n%i==0) /*i在2到sqrt(n)之间任取一个数,如果n能被整除则不是素数,否则就是素数,在下省了下面的输出步骤*/ 
     
    /*在本程序中使用第三种方法来求解*/
    #include <stdio.h>
    #include <math.h>
    int main(void)
    {
    int i; /*外循环*/
    int j; /*内循环*/
    int flag; /*素数标志,flag为1则此数为素数*/
    flag = 0;
    //int n;
    i = 2;
    while( i <= 100)
    {
    j = 2;
    flag = 1; /*假设此数为素数*/
    while(j <= (int) sqrt(float(i)))
    {
    if(0 == (i %j))
    flag = 0; /*根据第三种算法可知次数不为素数*/
    j ++;
    }
    if(flag)
    printf("%d\t",i);
    i++;
    }
    printf("\n");
    return 0;
    } 
     
     
     
     
    n到m:
     
    #include<stdio.h>
    int isprime(int n)
    { for(int i=2; i*i<=n; i++)
        if(n%i==0)return 0;
      return n>1;
    }
    int main()
    { int n,m,i;
      scanf("%d%d",&n,&m);
      for(i=n; i<=m; i++)
        if(isprime(i))
          printf("%d ",i);
      return 0;
    }
    
    
    
    展开全文
  • C语言求素数的解析

    2022-04-20 13:30:00
    素数:即质数,除了1和自己之外,再没有其他的约数,则该数据为素数,具体方式如下 */ //方法一:试除法 int main() { int i = 0; int count = 0; // 外层循环用来获取100~200之间的所有数据,100肯定不是...

    /*
    思路:
    素数:即质数,除了1和自己之外,再没有其他的约数,则该数据为素数,具体方式如下
    */


    //方法一:试除法
    int main()
    {
        int i = 0;
        int count = 0;


        // 外层循环用来获取100~200之间的所有数据,100肯定不是素数,因此i从101开始
        for (i = 101; i <= 200; i++)
        {
            //判断i是否为素数:用[2, i)之间的每个数据去被i除,只要有一个可以被整除,则不是素数
            int j = 0;
            for (j = 2; j < i; j++)
            {
                if (i % j == 0)
                {
                    break;
                }
            }

            // 上述循环结束之后,如果j和i相等,说明[2, i)之间的所有数据都不能被i整除,则i为素数
            if (j == i)
            {
                count++;
                printf("%d ", i);
            }
        }


        printf("\ncount = %d\n", count);
        return 0;
    }


    //上述方法的缺陷:超过i一半的数据,肯定不是i的倍数,上述进行了许多没有意义的运算,因此可以采用如下
    // 方式进行优化
    // 方法二:每拿到一个数据,只需要检测其:[2, i/2]区间内是否有元素可以被2i整除即可,可以说明i不是素数
    int main()
    {
        int i = 0;//
        int count = 0;


        for (i = 101; i <= 200; i++)
        {
            //判断i是否为素数
            //2->i-1
            int j = 0;
            for (j = 2; j <= i / 2; j++)
            {
                if (i % j == 0)
                {
                    break;
                }
            }
            //...
            if (j > i / 2)
            {
                count++;
                printf("%d ", i);
            }
        }


        printf("\ncount = %d\n", count);
        return 0;
    }


    /*
    方法二还是包含了一些重复的数据,再优化:
    如果i能够被[2, sqrt(i)]之间的任意数据整除,则i不是素数
    原因:如果 m 能被 2 ~ m-1 之间任一整数整除,其二个因子必定有一个小于或等于sqrt(m),另一个大于或等于 sqrt(m)。
    */
    int main()
    {
        int i = 0;
        int count = 0;


        for (i = 101; i <= 200; i++)
        {
            //判断i是否为素数
            //2->i-1
            int j = 0;
            for (j = 2; j <= sqrt(i); j++)
            {
                if (i % j == 0)
                {
                    break;
                }
            }
            //...
            if (j > sqrt(i))
            {
                count++;
                printf("%d ", i);
            }
        }


        printf("\ncount = %d\n", count);
        return 0;
    }


    //方法4
    /*
    继续对方法三优化,只要i不被[2, sqrt(i)]之间的任何数据整除,则i是素数,但是实际在操作时i不用从101逐渐递增到200,因为出了2和3之外,不会有两个连续相邻的数据同时为素数
    */


    int main()
    {
        int i = 0;
        int count = 0;


        for (i = 101; i <= 200; i += 2)
        {
            //判断i是否为素数
            //2->i-1
            int j = 0;
            for (j = 2; j <= sqrt(i); j++)
            {
                if (i % j == 0)
                {
                    break;
                }
            }
            //...
            if (j > sqrt(i))
            {
                count++;
                printf("%d ", i);
            }
        }

        printf("\ncount = %d\n", count);
        return 0;
    }

    展开全文
  • //1--1000内的质数素数) #include <stdio.h> int main() { int x = 0; int i = 0; unsigned int count = 0; for (x = 2; x < 1000; x++) //在2到1000之间找质数 { for (i = 2; i < x; i++)...

    在这里插入图片描述

    什么是质数(素数)?

    质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数(规定1既不是质数也不是合数)。———来自百度百科

    第一种方法,暴力解决

    我们设定一个数为x,根据质数的定义判断x是否为质数,我们看它能否被2、3、4······、x-1整除,如果它不能被其中任何一个整数整除,则这个数就是质数。
    比如要判断11是不是质数,我们就看能否被下面这10个数整除。
    2、3、4、5、6、7、8、9、10
    因为11无法被其中任何一个数整除,则判断它为质数。

    如果我们要找1—1000内的质数,我们可以控制x从2自己增到1000,并且x每次自增1过后,都要从2开始找能否被x所整除的数,直到找不到结束。所以我们可以用两层for循环来控制,第一层来控制x产生2–1000数字,第二层for循环产生2到x-1的数,并且判断能否被整除。(因为1不是质数,把1排除在外)

    并且我还设置了一个计数器count来统计大概运算的次数,方便和下面方法做对比。代码如下:

    
    //求1--1000内的质数(素数)
    #include <stdio.h>
    int main()
    {
    	int x = 0;   
    	int i = 0;
    	unsigned int count = 0;  //统计运算的次数
    	for (x = 2; x < 1000; x++)    //在2到1000之间找质数
    	{
    		for (i = 2; i < x; i++)   //试除法,能不能被x整除,从2开始找,直到等于x
    		{
    			count++;
    			if (x % i == 0)   //找到能被x整除的数了
    			{
    				break;
    			}
    		}
    		if (x == i)   //找到和x相等也没有被整除的,证明是质数
    		{
    			printf("%d ",x);
    		}
    	}
    	printf("\n\n\n");
    	printf("运算的次数:%d ",count);
    	return 0;
    }
    

    第一种方法运行结果:
    在这里插入图片描述

    第二种方法,用奇数

    第一种方法是否有点复杂呢,这是当然的。
    其实我们从质数:
    2、3、5、7、9、11、13、17、19······中发现什么规律了没有呢?

    嘿嘿嘿,那就是除了2以外那些2的倍数(4、6、8、10、12、14、18·······)都不是质数。

    所以我们的第一层for循环是不是可以不用一步步自增1,而是从3开始自增2呢,从而产生3、5、7、9、11······这样就把偶数给巧妙避免了。代码如下:

    #define _CRT_SECURE_NO_WARNINGS 1
    #include <stdio.h>
    int main()
    {
    	int x = 0;
    	int i = 0;
    	unsigned int count = 0;
    	x = 2;
    	printf("%d ",x);   //已经知道2为质数,所以先第一个打印
    	for (x = 3; x < 1000; x += 2)  //从3开始自增2
    	{
    		for (i = 2; i < x; i++)
    		{
    			count++;
    			if (x % i == 0)
    			{
    				break;
    			}
    		}
    		if (x == i)
    		{
    			printf("%d ",x);
    		}
    	}
    	printf("\n\n\n");
    	printf("运算的次数:%d ", count);
    	return 0;
    }
    

    第二种方法运行结果:
    在这里插入图片描述
    第一种和第二种对比图片:
    在这里插入图片描述
    大家发现了没有好像第二种并没有比第一种运算要少很多,这个是因为当判断33、66、666这些在开始阶段i=3的时候,马上就可以判定不是质数了,所以运算次数并没有怎么减少。

    第三种方法,奇数双管齐下

    结合第二种方法,除了2以外那些2的倍数(4、6、8、10、12、14、18·······)都不是质数。
    所以除了2以外质数一定是奇数。
    从而判断11是否为质数的时候,我们不再需要判断能否被2、3、4、5、6、7、8、9、10这9个数整除,我们只需要判断 能否被3、5、7、9这几个数整除即可。
    所以我们可以控制第二层for循环不再自增1,而是从3开始自增2。
    代码如下:

    #define _CRT_SECURE_NO_WARNINGS 1
    #include <stdio.h>
    int main()
    {
    	int x = 0;
    	int i = 0;
    	unsigned int count = 0;
    	x = 2;
    	printf("%d ",x);
    	for (x = 3; x < 1000; x += 2)  //只产生奇数
    	{
    		for (i = 3; i < x; i += 2)  //只产生奇数
    		{
    			count++;
    			if (x % i == 0)
    			{
    				break;
    			}
    		}
    		if (x == i)
    		{
    			printf("%d ",x);
    		}
    	}
    	printf("\n\n\n");
    	printf("运算的次数:%d ", count);
    	return 0;
    }
    

    第三种方法运行结果:
    在这里插入图片描述

    第四种方法,巧用数组

    在第三种的基础上再看,我们还发现如下规律:
    不能被3整除的整数也无法被大于3的那些3的倍数(6、9、12······)整除。
    不能被5整除的整数也无法被大于5的那些倍数(10、15、20······)整除。
    所以,如果整数x无法被小于x的质数整除,那么x就是质数。
    根据这个条件,我们求质数就有了另外一条思路:我们用数组来保存质数,控制x自增后,用x除去数组的每一个元素,如果不能整除则是质数,并且保存到数组中。

    因此,我们先把2、3这两个质数保存到数组中,第一层for循环依旧是控制x自增,第二层for循环来遍历数组。遍历后如果都不能整除,则存到数组中。如果有一个能被整除,则不是质数,不保存。

    代码如下:

    #define _CRT_SECURE_NO_WARNINGS 1
    #include <stdio.h>
    int main()
    {
    	int arr[500] = { 0 };
    	int x = 0;
    	int i = 0;
    	unsigned int count = 0;
    	int sum = 0;  //定义数组的下标
    	arr[sum] = 2;  //把2存到数组中
    	sum++;
    	arr[sum] = 3;   //把3存到数组中
    	sum++;
    	for (x = 5; x < 1000; x += 2)
    	{
    	  //从下标0开始遍历,直到数组的最后一个质数
    		for (i = 0; i < sum; i++ ) 
    		{
    			count++;
    			if (x % arr[i] == 0)
    			{
    				break;
    			}
    		}
    		if (sum == i)  //遍历后都不能整除
    		{
    			arr[sum] = x;  //把质数保存到数组中
    			sum++;   //下标加1,为下次放做准备
    		}
    	}
    	for (i = 0; i < sum; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n\n\n");
    	printf("运算的次数:%d ", count);
    	return 0;
    }
    

    运算结果:
    在这里插入图片描述

    第五种方法,巧用平方根

    写法1:

    我们设两个整数a和b,如果不是质数的话,整数x就可以写成 x=a * b 比如:
    36=2 * 18
    36=3 * 12
    36=4 * 9
    36=6 * 6
    如果整数x为质数,那么就不可能写成 x = a * b的形式。所以如果整数x无法被小于等于x的平方根的质数整除,则x为质数。
    因此,我们可以在第四种方法上改造一下,就是在第二层for循环,从数组的第一个元素出发,每一个都写成平方,直到平方大于整数x退出循环。
    代码如下:

    //第五种方法,巧用平方根,写法1:
    #include <stdio.h>
    int main()
    {
    	int arr[500] = { 0 };
    	int x = 0;      //定义要找质数的变量
    	int i = 0;
    	unsigned int count = 0;
    	int sum = 0;    //定义数组下标
    	arr[sum] = 2;  //2是质数,储放到数组中
    	sum++;
    	arr[sum] = 3;   //3也是质数,放到数组中
    	sum++;
    	for (x = 5; x < 1000; x += 2)   //只查找奇数
    	{
    		for (i = 0;arr[i] * arr[i] <= x; i++)   //利用数组中的元素平方去排查
    		{
    			count++;
    			if (x % arr[i] == 0)   //不是质数
    			{
    				break;
    			}
    		}
    		if (arr[i]*arr[i]>x)     //为质数
    		{
    			arr[sum] = x;   //把找到的奇数放到数组中
    			sum++;          //下标加1
    		}
    	}
    	for (i = 0; i < sum; i++)
    	{
    		printf("%d ",arr[i]);
    	}
    	printf("\n\n\n");
    	printf("运算的次数:%d ", count);
    	return 0;
    }
    

    运算结果:
    在这里插入图片描述

    写法2:

    我们不要数组也可以,直接在第三种方法上改造。
    代码如下:

    //第五种方法,巧用平方根,写法二:
    #include <stdio.h>
    int main()
    {
    	int x = 0;
    	int i = 0;
    	unsigned int count = 0;
    	x = 2;
    	printf("%d ",x);
    	for (x = 3; x <= 1000; x += 2)
    	{
    		for (i = 2; i*i<=x; i++)  //控制第二层循环
    		{
    			count++;
    			if (x % i == 0)
    			{
    				break;
    			}
    		}
    		if (i*i>x)
    		{
    			printf("%d ",x);
    		}
    	}
    	printf("\n\n\n");
    	printf("运算的次数为:%d ",count);
    	return 0;
    }
    

    运算结果:
    在这里插入图片描述

    总结

    我们从第一种的简单粗暴到最后的优良改造,运算次数一步步地减少,大家是否领悟到了编程的优美了呢?我特别推荐最后一种的写法二,既不用数组,也可以节省很多的运算时间。

    如果有错误的地方,还有改进的方法,欢迎在评论区指出。

    在这里插入图片描述

    既然都看到这里了,点个赞呗,嘿嘿嘿。

    展开全文
  • C语言求素数的几种方法

    万次阅读 多人点赞 2020-02-17 20:01:45
    输入的数n不能被2-(n-1)整除,说明是素数 输入的数n能被2-(n-1)整除,说明不是素数 注意:1不是素数素数是指大于1的自然数,除了1和该数自身外,无法被其他自然数整除的数。 法一: #include<stdio.h> ...
  • C语言求质数的方法

    千次阅读 2021-05-22 00:38:33
    质数就是只能被1和本身整除的数。Eratosthenes筛选法是一种计算质数的有效方法。这个算法的第一步就是写下所有从2至某个上限之间的所有整数。在算法的剩余部分,遍历整个列表并剔除所有不是质数的整数。后面的步骤是...
  • C语言求素数的两种方法

    万次阅读 多人点赞 2018-02-07 09:33:07
    1,判断n是否能被2~n-1整除 ...注意:1不是素数素数是指大于1的自然数,除了1和该数自身外,无法被其他自然数整除的数。 法一: #include<stdio.h> int main() { int i, n; printf("please input a nu...
  • C语言求质数的算法

    2021-05-22 13:17:15
    上次被出了一题质数C语言求解题目(面试),当时用了最粗暴的算法,回来仔细参考资料,其实答案有很多种:1,小学生版本:判断 x 是否为质数,就从 2 一直算到 x-1。static rt_uint32_t array1[ARRAY_LEN];void func...
  • C语言求素数/质数最高效的方法

    万次阅读 多人点赞 2016-11-15 19:13:59
    所有求素数方法中循环次数最少. 2 ) . 关于只要求到平方根的说明 : 因为任何一个数都不可能分解成两个大于其平方根的数的乘积 . 肯定只能分解为一个大于或等于其平方根,另一个小于或等于其平方根 . ...
  • C语言求质数.pdf

    2021-09-27 12:52:51
    C语言求质数.pdf
  • C语言求质数算法
  • 关注公众号:你不知道的东东 与博主直接交谈 #include<stdio.h> void is_primer(int x,int y){ int i=2; int sum=0; if(x==2){ printf("%d\t", x); sum += x; } for(;......
  • C语言六种方法求素数质数) 最全 输出2-100以内的所有素数 1000以内的所有素数
  • 问题描述 梅森数(Mersenne Prime)指的是形如2n-1的正整数,其中指数n是素数,即为Mn。如果一个梅森数是素数,则称其为梅森素数。例如22-1=3、23-1=7都是梅森素数。...试出指数n<20的所有梅森素数。 问题分
  • C语言求素数

    2021-05-21 07:21:06
    满意答案雪中asd送炭推荐于 2017.11.24采纳率:55%等级:7已帮助:860人/*求素数的三种方法一:for(i=2;i<=(n-1);i++)if(n%i==0)i在2到n-1之间任取一个数,如果n能被整除则不是素数,否则就是素数二:for(i=2;...
  • C语言丨筛法求素数质数

    千次阅读 2021-12-17 11:22:53
    素数质数)是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。素数被广泛用于密码学、汽车变速箱齿轮设计、害虫的生物生长周期与杀虫剂使用之间的关系、导弹和鱼雷等领域上,具有重要意义。本文...
  • 素数(又称质数)的概念: 只有1和它本身两个因数的自然数 当我们用c语言去实现素数算法的代码时,重点是去考虑其变量以及循环条件,掌握这两点就可以做素数的例题啦~ 例 1 从键盘输入一个数,判断其是否为素数 ????...
  • C语言编程题求素数

    2022-07-05 20:07:20
    素数又叫质数,素数是指在大于1的自然数中,除了1和它本身以外,不能被其他自然数整除的数。 思路:比如100-200之间的素数,遍历每一个数,看它是否能够被2到(n-1)之间的数字整除,如果能够被整除,那么就不是素数,...
  • 本文主要介绍了c语言求出给定范围内的所有质数的小程序。具有很好的参考价值。下面跟着小编一起来看下吧

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,761
精华内容 13,104
关键字:

c语言求素数

友情链接: QRCode.java.zip