精华内容
下载资源
问答
  • c语言求素数

    千次阅读 2017-03-15 19:03:33
    c语言求素数
    思路:另外判断方法还可以简化。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之间有无因子即可。


    #include <stdio.h>
    #include <math.h>
    void main(){
        int m,i,k,n=0;   
        printf("输入一个整数:");
        scanf("%d",&m);
        // 求平方根,注意sqrt()的参数为 double 类型,这里要强制转换m的类型 
        k=(int)sqrt(m);
        for(i=2;i<=k;i++)
            if(m%i==0)
                break;
        // 如果完成所有循环,那么m为素数
        // 注意最后一次循环,会执行i++,此时 i=k+1,所以有i>k 
        if(i>k)
            printf("%d",m);
            n++;
            if(n%5==0){
               printf("\n");
            }
        return 0;
    }


    展开全文
  • C语言求素数

    万次阅读 多人点赞 2018-08-17 10:30:00
    /*求素数的三种方法 一: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: ");...

    质数是指在大于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

    展开全文
  • 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...

    1,判断n是否能被2~n-1整除

    输入的数n不能被2-(n-1)整除,说明是素数

    输入的数n能被2-(n-1)整除,说明不是素数

    注意:1不是素数,素数是指大于1的自然数,除了1和该数自身外,无法被其他自然数整除的数。

    法一:

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

    法二:

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

     

     

     

     

    2,判断n是否能被2~√n间的整数整除

    输入的数n不能被2-√n整除,说明是素数

    输入的数n能被2-√n整除,说明不是素数

     

    #include<stdio.h>
    #include<math.h>
    int main()
    {
        int n,i;
        double k;
        printf("please input a number:"); 
        scanf("%d", &n);
        k = sqrt(n);
        for (i = 2; i <= k;i++)
        {
            if (n%i == 0) break;
        }
        if (n <=1 ) printf("This is not a prime\n");
        else if (i <= k) printf("This is not a prime.\n");
        else printf("This is a prime\n");
        return 0;
     
    }

    法二:

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

    以上两个程序的法二:Modified on April 22, 2019

    对于评论出现的问题,在此整理一下

    运行软件: VC++ 6.0

     

    weixin_43912791: 这段代码识别不了1啊。。

    回答:素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数。所以没考虑1的情况。

     

    weixin_43412408: 能问下i>k的逻辑是什么?想不太明白

    第二个方法:对一个数n,如果他能分解成n=pq,那么pq里必然有一个大于等于根号n一个小于等于根号n,也就是说一个合数n必然有一个因子是小于等于根号n的. 所以对一个数n,只要检验他有没有小于等于根号n的因子就可以了(检验小于等于n的因子使循环次数变少,这也是简化的原因)

     

    写这篇文章的初衷是给自己提供一个思路,没有考虑太多的情况,没想到这么多人看,所以重新整理了一下代码。

    感谢@ 锦言肾行的分享

     

     

    素数的定义是只能被1和他本身整除,1不是素数.因此要判断一个数是否为素数.就要判断它能不能被比他小的所有素数整除,这是一个算法.(写到算法时,我只能写出用它除以比他小的所有数,造成运算速度低下)
    这里给出的是一个更快速的方法.要判断一个数是否为素数,只要判断比它开根号后的数小的数,能否把它整除.
    为什么可以这样做呢.从百度得到的答案如下:
    如果一个质数大于根号n,而n可以除尽它,那么n必然也可以除尽一个更小的质数。
    例如21,它可以除尽7,而它同样可以除尽3。所以判断21是否质数,只需要判断21是否可以除尽2和3就可以了。5和7和11就不需要判断了。
    想来就是这样,例如21.根号21乘根号21等于21.则当一个比根号21的数大的数乘另一个数得到21.另一个数必然小于根号21.
    由此可以得到一个法2较快的素数判断算法 

     

     

     

     

     

     

    展开全文
  • 主要介绍了使用c语言判断100以内素数的示例(c语言求素数),需要的朋友可以参考下
  • C语言求素数方法

    2019-10-14 23:20:12
    C语言求素数方法 确定性算法 缺点:慢 试除法 //1.试除法 int is_prime(int n) { int i; if(n<=1) return 1; //1表示素数 for(i = 2; i < n; i++) // for(i = 2; i*i <n;i++) //改进版 { if...

    C语言求素数方法

    确定性算法
    缺点:慢

    1. 试除法
    //1.试除法
    
    int is_prime(int n)
    {
    	int i;
    	
    	if(n<=1)
    	return 1;    //1表示素数
    	
    	for(i = 2; i < n; i++)
    //	for(i = 2; i*i <n;i++)   //改进版 
    	{
    		if(n%i == 0)
    		return 0;
    	}
    	return 1;
    }
    
    1. Eratosthenes求素数方法
    //2.Erathosthens求素数方法
    #denfine MAXNUM 1000
    int main()
    {
    	int i ,j;
    	int prime[MAXNUM+1];     	//定义保存素数的数组
    	//初始化数组
    	for(i = 2;i <= MAXNUM;i++)
    	{
    		prime[i] = 1;
    	 } 
    	 
    	for(i = 2;i*i <= MAXNUM;i++)
    	{
    		if(prime[i] )
    		{
    			for(j = i*2; j*j <=MAXNUM;j++)
    			{
    				if(!prime[j] )  continue;   //判断是否是合数
    				if(j%i == 0)   prime[j]=0;  //判断质因数是否为i,即是否是素数
    			}
    		}
    	} 
    	 
    	 int c=0;
    	 for(i = 2; i < MAXNUM;i++)
    	 {
    	 	if(prime[i])
    	 	printf("%d",i);
    	 	c++;
    	 }
    	 printf("共有%d个素数",c);
    	
     } 
    

    随机算法
    优点:快
    涉及较多数学定理,数学性较强
    详见blog素数测试与随机算法

    参考资料:《程序员的数学思维修炼》

    展开全文
  • C语言求素数的不同解法

    千次阅读 2013-10-19 23:26:26
    C语言求素数的不同解法,不同编码。不同的编码对应不同的效率。 1、求a到b之间的素数: (1)一般的: #include "stdio.h" void main() { int a,b; int i,n; int flag=1; printf("请输入下限:"); scanf("%d...
  • c语言求素数

    2019-11-09 15:20:03
    c语言输出正数n以内的素数。如果输入一个负数,则会提示:”输入数据错误,请输入一个正数。“ 示例: 输入:100` 输出: 代码如下: 我所写的这个代码中首先用了一个选择结构if语句的判定,如果输入的数m符合...
  • 101-200之间的素数; 初学C语言的时候写的程序,写的可能不是很好,但我觉得小白比较能接受,算法很简单。希望可以帮到正在看的你
  • “要成为绝世高手,并非一朝一夕,除非是天生武学奇才,但是这种人…万中无一”——包租婆这道理放在C语言学习上也一并受用。在编程方面有着天赋异禀的...例17:C语言编程实现输出100~200之间的素数。解题思路:这个...
  • c语言求素数的小程序

    2011-05-14 01:21:07
    c语言循环求素数,c语言经典面试题,面试必备宝典
  • 常见算法:C语言求素数的问题 素数,又称为质数,指在一个大于1的自然数中,除了1和此整数自身外,无法被其他自然数整除的数(只有1和本身两个因数的数),维基百科:素数的定义点击打开链接 算法过程:...
  • C语言求素数,以及优化

    千次阅读 2017-08-05 15:43:43
    素数C语言求法。
  • 当我们用c语言去实现素数算法的代码时,重点是去考虑其变量以及循环条件,掌握这两点就可以做素数的例题啦~ 例 1 从键盘输入一个数,判断其是否为素数 ????分析:想到概念,任何素数只能被1和它本身所除,那么从1到...
  • c语言求素数个数

    2020-02-07 20:25:41
    请问有大佬帮我解读一下if(i==j)这个判断是怎么出来的吗?j的值是哪来的 [img=https://img-bbs.csdn.net/upload/202002/07/1581078340_536113.jpg][/img]
  • 输入的数n不能被2-(n-1)整除,说明是素数 输入的数n能被2-(n-1)整除,说明不是素数 注意:1不是素数素数是指大于1的自然数,除了1和该数自身外,无法被其他自然数整除的数。 法一: #include<stdio.h> ...
  • 1.除了2以外所有2的倍数都不是素数 2.如果num能被2~m-1之间任意一个整数整除,它的两个因子一定有一个小于等于根号num,另一个大于等于根号num,所以当根号num之前没有找到因数,在它之后也不会有因数 #include <...
  • 代码需要使用c99编译 #include <stdio.h> #include <...//是否为素数 //从2到x-1测试是否可以整除 //时间复杂度O(n-2),n趋向正无穷 int isPrime(int x) { int ret = 1; for(in...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,115
精华内容 446
关键字:

c语言求素数

c语言 订阅