求"求素数的C语言程序"

#include <stdio.h>

int main()

{

  int a=0

  int num=0

int i

  printf("输入一个整数：")

  scanf("%d",&num)

  for(i=2i<numi++){

      if(num%i==0){

       中慧   a++

      }

  }

  if(a==0){

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

  }else{

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

  }

  return 0

}

扩展资料：

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合卖肢答数。

基本算法：若 k%m==0 则说明 k 不是素数。

判断整数n是否为素饥纯数——采用枚举法求解。

采用枚举算法解题的基本思路：

（1）确定枚举对象、枚举范围和判定条件；

（2）枚举可能的解，验证是否是问题的解。

枚举算法的一般结构：while循环。

参考资料来源：百度百科-枚举法

#include<stdio.h>

#include<math.h>

int lsPrime(int n)

int main()

{

int n, i, k, sum = 0

printf("input n:\n")

scanf("%d", &n)

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

{

if (lsPrime(i) == 1)

{

sum += i

}

}

printf("sum=%d\n", sum)

return 0

}

int lsPrime(int n) /弯戚//是素数培肆21135261返回410216531,否配闹轿则返回0

{

int i, k

k = (int) sqrt(n)

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

{

if (n % i == 0)

break

}

if (i >k &&n >1)

return 1

else

return 0

}

这个问题可以枯搭分成两部分解决，一个是判断素数，另一部分是实现累加和输出。

一、判断素数。

有以下两种常见的判断素数的方法。

1 通过数学定义判断，即查找所有因子，如果存在除1及本身以外因子，则非素数。

代码如下：

#include <math.h>//用到开平方函数，引用对应的数学头文件

int is_prime(int n)

{

int i

for(i = 2 i <= (int)sqrt(n) i ++)//根据数学定义，除本身外，其它因子不可能比平方根更大，所以只需要判断不大于平方根的值即可。其中sqrt为求平方根函数。

if(n%i==0) return 0 //只要有一个符合条件的因子，则非素数，返回0。

return 1 //该数为素数。

}

这个算法可以应用于任何情况。

2 素数筛。

这种算法的原理是，所有素数的倍数都不是素数。

先假定所有数均为素数，然后去掉已知素数的倍数，最终得到一定范围内所有素数。

代码如下：

int map[100]//数据规模，这里使用题目中的100，实际上应该是标记0-100,也就是101个单位，但是100是已知的非素数，所以用100个元素就足够了。

void make_map(void)

{

int i,j

map[1] = 1 //1 不是素数。

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

{

if(map[i])continue //对于已知的非素数，不做处理

for(j = i*2 j < 100 j +=i)

map[j] = 1

}

}

int is_prime(int n)

{

if(map[1] == 0) make_map() //如果1没有被标记为非素数，那么表示map没有生成，需要生成map。

return map[n] == 0 //如map[n]为0，则n为素数

}

这种算法空间开销与数据规模成正比，当数据规模比较大时并不适用。

但对于数据规模小且素数判断频繁的情况，具有更高的时间开销优势。

二、累加。

这部分可以放置于主函数。调用上述任意一种素数判断函数皆可。

#include <stdio.h>

int main()

{

int 谨败物sum = 0//累加结果

int i

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

if(is_prime(i))sum+=i//累加素数。

printf("sum = %d\n", sum)//输出结果。

}

最终祥液输出sum=1060

---