c语言如何判断素数
1. c语言怎么判断素数
所谓素数是指除了1和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被2~16的任一整数整除。因此判断一个整数m是否是素数，只需把m被2~m-1之间的每一个整数去除，如果都不能被整除，那么m就是一个素数
另外判断方法还可以简化。m不必呗2~m-1之间的每一个整数去除，只需被2~√m之间的每一个整数去除就可以了。如果m不能被2~√m间任一整数整除，m必定是素数。例如判别17是是否为素数，只需使17被2~4之间的每一个整数去除，由于都不能整除，可以判定17是素数。（原因：因为如果m能被2~m-1之间任一整数整除，其二个因子必定有一个小于或等于√m，另一个大于或等于√m。例如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;
printf("请输入一个整数：");
scanf("%d",&m);
k=(int)sqrt(m);
for(i=2;i<=k;i++)
if(m%i==0)
break;
if(i>k)
printf("%d 是素数。\n",m);
else
printf("%d 不是素数。\n",m);
}
2. 在C语言中，如何判断一个数是不是素数
main(){
int i=2,num=0,bj=1;
printf("请输入你要判断的数版");
scanf("%d",&num);
for(;i<num;i++){
if(num%i==0)
{
bj=0;
}
}
if(bj)
printf("%d是素数权",num);
else
printf("%d不是素数",num);
}
3. c语言怎么判断一个数是素数
判断是否是质数最直观和简单的方法就是从2开始直接除，能除尽（余数为0）就不是质数。则C语言实现为：
int isprime(int m)
{
int i;
for(i=2;i<m;i++)
if(m%i==0）
return 0;
else
return 1;
}
该算法的时间复杂度O(n)。
可以改进一下，根据如果一个数是合数，那么它的最小质因数肯定小于等于它的平方根。用反证法可以证明一下。假设x是n的最小质因数，则存在n/x=p。p>x,x*p=n。如果x不小于等于它的平方根，则x*x>n,而p>x，故x*p>n,假设不成立。合数是与质数相对应的自然数。一个大于1的自然数如果它不是合数，则它是质数。也就是说如果一个数能被它的最小质因数整除的话，那它肯定是合数，即不是质数。所以判断一个数是否是质数，只需判断它是否能被小于它开跟号后的所有数整除，因此，这样做的运算少了很多，降低了时间复杂度。
4. 如何用c语言编程判断一个数是不是素数
方法一：
＃include＜stdio．h＞
int main（）｛
int i，j；
printf（＂请输入一个正整数。＼n＂）；
scanf（＂％d＂，＆i）；
if（i＜2）
printf（＂小于2，请重新输入。＼n＂）；
elseif（i％2＝＝0）
printf（＂％d不是一个素数。＼n＂，i）；
else｛
for（j＝2；j＜＝i／2；j＋＋）｛
if（i％j＝＝0）｛
printf（＂％d不是一个素数。＼n＂，i）；
break；
｝
if（j＞i／2）｛
printf（＂％d是一个素数。＼n＂，i）；
break；
｝
｝
｝
｝
方法二：
＃include＜stdio．h＞
int main（）｛
int a＝0；
int num＝0；
scanf（＂％d＂，＆num）；
for（inti＝2；i＜num－1；i＋＋）｛
if（num％i＝＝0）｛
a＋＋；
｝
｝
if（a＝＝0）｛
printf（＂YES＼n＂）；
｝else｛
printf（＂NO＼n＂）；
｝
｝
方法三：
＃include＂stdio．h＂
int main（）｛
printf（＂＼t＼t＼t＼t＼thelloworld＼n＂）；
int a，i；
do｛
printf（＂inputnumberjudgeprimenumber：＼n＂）；
scanf（＂％d＂，＆a）；
for（i＝2；i＜a；i＋＋）
if（a％i＝＝0）break；
if（i＝＝a）
printf（＂％d是素数＼n＂，a）；
else
printf（＂％d不是素数＼n＂，a）；
｝while（a！＝0）；
｝
5. 用C语言如何判断素数
素数又称质数，所谓素数是指除了 1 和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被 2~16 的任一整数整除。
思路1、判断一个整数m是否是素数，只需把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。
思路2、判断方法还可以简化。
m 不必被2~m-1之间的每一个整数去除，只需被2~√m之间的每一个整数去除就可以了。如果 m 不能被2~√m间任一整数整除，m必定是素数。例如判别17是是否为素数，只需使17被2~4之间的每一个整数去除，由于都不能整除，可以判定17是素数。
原因：因为如果m能被2~m-1之间任一整数整除，其二个因子必定有一个小于或等于√m，另一个大于或等于√m。
例如16能被2、4、8整除，16=2*8，2小于 4，8大于4，16=4*4，4=√16，因此只需判定在2~4之间有无因子即可。
两种思路的代码请看解析。
拓展资料：
素数（prime number）又称质数，有无限个。素数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
C语言是一门面向过程、抽象化的通用程序设计语言，广泛应用于底层开发。C语言能以简易的方式编译、处理低级存储器。C语言是仅产生少量的机器语言以及不需要任何运行环境支持便能运行的高效率程序设计语言。
网络——C语言
6. C语言中怎么判断素数
从1开始遍历到该数的开方，如果找到一个数能整除该数，证明这不是个素数，看看以下代码
#include<math.h> //头文件为math.h
int isprime(int a)
{
int i;
for (i = 2; i <= sqrt((long double)a); ++i)
{
if (a % i == 0)
{
return 0; //能整除就返回不是
}
}
return 1; //都不能整除返回是
}
7. 求C语言中 判断素数的 代码!!!!!
基本思想：把m作为被除数，将2—INT（ ）作为除数，如果都除不尽，m就是素数，否则就不是。
可用以下程序段实现：
void main()
{ int m,i,k;
printf("please input a number: ");
scanf("%d",&m);
k=sqrt(m);
for(i=2;i<k;i++)
if(m%i==0) break;
if(i>=k)
printf("该数是素数");
else
printf("该数不是素数");
}
将其写成一函数,若为素数返回1，不是则返回0
int prime( m%)
{int i,k;
k=sqrt(m);
for(i=2;i<k;i++)
if(m%i==0) return 0;
return 1;
}
(7)c语言如何判断素数扩展阅读：
筛法求素数
一、基本思想
用筛法求素数的基本思想是：
把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。
如有：
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
1不是素数，去掉。剩下的数中2最小，是素数，去掉2的倍数，余下的数是：
3 5 7 9 11 13 15 17 19 21 23 25 27 29
剩下的数中3最小，是素数，去掉3的倍数，如此下去直到所有的数都被筛完，求出的素数为：
2 3 5 7 11 13 17 19 23 29
二、C++实现
1、算法一：令A为素数，则A*N（N>1;N为自然数）都不是素数。
#definerange2000
bool
IsPrime[range+1];
/*set函数确定i是否为素数，结果储存在IsPrime[i]中，此函数在DEV
C++中测试通过*/
voidset(boolIsPrime[])
{
inti,j;
for(i=0;i<=range;++i)
IsPrime[i]=true;
IsPrime[0]=IsPrime[1]=false;
for(i=2;i<=range;++i)
{
if(
IsPrime[i])
{
for(j=2*i;j<=range;j+=i)
IsPrime[j]=false;}}}2、
说明：解决这个问题的诀窍是如何安排删除的次序，使得每一个非质数都只被删除一次。 中学时学过一个因式分解定理，他说任何一个非质（合）数都可以分解成质数的连乘积。
例如，16=2^4，18=2 * 3^2，691488=2^5 * 3^2 * 7^4等。如果把因式分解中最小质数写在最左边，有16=2^4，18=2*9,691488=2^5 * 21609,；
换句话说，把合数N写成N=p^k * q，此时q当然是大于p的，因为p是因式分解中最小的质数。由于因式分解的唯一性，任何一个合数N，写成N=p^k * q;的方式也是唯一的。
由于q>=p的关系，因此在删除非质数时，如果已知p是质数，可以先删除p^2,p^3,p^4,... ，再删除pq,p^2*q,p^3*q,...,（q是比p大而没有被删除的数），一直到pq>N为止。
因为每个非质数都只被删除一次，可想而知，这个程序的速度一定相当快。依据Gries与Misra的文章，线性的时间，也就是与N成正比的时间就足够了（此时要找出2N的质数）。
代码如下：
#include<iostream>
#include<cmath>
usingnamespacestd;
intmain()
{
intN;cin>>N;
int*Location=newint[N+1];
for(inti=0;i!=N+1;++i)
Location[i]=i;
Location[1]=0;//筛除部分
intp,q,end;
end=sqrt((double)N)+1;
for(p=2;p!=end;++p)
{
if(Location[p])
{
for(q=p;p*q<=N;++q)
{
for(intk=p*q;k<=N;k*=p)
Location[k]=0;
}
}
}
intm=0;
for(inti=1;i!=N+1;++i)
{
if(Location[i]!=0)
{
cout<<Location[i]<<"";
++m;
}
if(m%10==0)cout<<endl;
}
cout<<endl<<m<<endl;
return0;
}
该代码在Visual Studio 2010 环境下测试通过。
以上两种算法在小数据下速度几乎相同。
8. 如何编写一个C语言程序判断一个数是否是素数
思路1：
判断一个整数m是否是素数，只需把m被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么就是一个素数。代码如下：
#include <stdio.h>
int main(){
int a=0; // 素数的个数
int num=0; // 输入的整数
printf("输入一个整数：");
scanf("%d",&num);
for(int i=2;i<num;i++){
if(num%i==0){
a++; // 素数个数加1
}
}
if(a==0){
printf("%d是素数。 ", num);
}else{
printf("%d不是素数。 ", num);
}
return 0;
}思路2：
另外判断方法还可以简化。m不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~ 之间的每一个整数去除就可以了。如果m不能被 2 ~ 间任一整数整除，m必定是素数。例如判别17是是否为素数，只需使17被2~4之间的每一个整数去除，由于都不能整除，可以判定17是素数。代码如下：
#include <stdio.h>
#include <math.h>
void main(){
int m; // 输入的整数
int i; // 循环次数
int k; // m 的平方根
printf("输入一个整数：");
scanf("%d",&m);
// 求平方根，注意sqrt()的参数为 double 类型，这里要强制转换m的类型
k=(int)sqrt( (double)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);
else
printf("%d不是素数。 ",m);
return 0;
}