c语言求素数的算法

根据素数的性质，代码设计如下：

设计一：判断n是否能被1~n-1整除，不能整除为素数

#include<stdio.h>

int main()

{

int i, n

scanf("%d", &n)

for (i = 2i <n i++)

{

if (n%i == 0)

break

}

if (i <n) printf("This is not a prime.")

else printf("This is a prime.")

return 0

}

设计二：判断n是否能被2~√n间的整数整除，不能整除为素数

#include<stdio.h>

#include<math.h>

int main()

{

int n,i

double k

scanf("%d", &n)

k = sqrt(n)

for (i = 2i <= ki++)

{

if (n%i == 0) break

}

if (i <=k) printf("This is not a prime.")

else printf("This is a prime")

return 0

}

扩展资料：

1.素数的定义是只能被1和他本身整除,1不是素数.因此要判断一个数是否为素数.就要判断它能不能被比他小的所有素数整除,这是一个算法.(写到算法时,我只能写出用它除以比他小的所有数,造成运算速度低下)

2.如果一个质数大于根号n，而n可以除尽它，那么n必然也可以除尽一个更小的质数。由此可以得到一个法2较快的素数判断算法

参考资料：百度百科-scanf

参考资料：百度百科-质数

素数即只能被1和其本身整除的数，算法判断n是否为素数只需用2~n/2之间的数去除就可以了。因为一个数的一半的平方大于其本身是从5开始的，解方程：n/2的平方>n 。即一个数n的两个因数不能同时比n/2大。就可以说一个数若不是素数则一定在2~n/2之间有因数。而且2，3也是符合下面程序的。

素数（又称质数）：就是除了1和它本身，没有其他因子的整数。注：1不是素数。

C语言代码算法：

#include <stdio.h>

main(){

int i,j,k=0

for(i=2i<=1000i++)

{

for(j=2j<=i/2j++)

if(i%j==0)break

if(j>i/2)

{printf("%d ",i)}

}

}

//判断一个数num是否为素数

#include <stdio.h>

int main()

{

int num,i,n=0

while(1)

{

scanf("%d",&num)//输入一个数num

if(num==2) printf("%d是素数\n",num)

else if(num>=3)

{

for(i=1i<=numi++)

{

if((num%i)==0) n++

}

if(n==2) printf("%d是素数\n",num)

else printf("%d不是素数\n",num)

n=0

}

else printf("%d不是素数\n",num)

}

return 0

}

---