c语言求素数的办法？只需解题思路

Question

如题所述

Answer 1

/*求素数的三种方法
一：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;
}

Answer 2

看你需不需要追求时间效率

是不是需要求超大的素数,int64 的有20位

甚至高精度情况下的素数，百位上千位

可以建立素数表来求

你仔细想想，任意一个整数都能分成几个素数的乘积，只由素数只有自己

所以，对于每个我们需要判断的数，只需要用素数表里的数来除即可

若都不能整除，那此数一定也是素数，那就把它加入素数表内

一直求下去就行，一般来说10000个数的素数表就能判断 int32内的素有数

因为素数表能判断素数的范围是 表内最大那个素数的平方

Answer 3

素数即是质数，因此用for循环从2开始除就可以，假设你设定一个数字n，可以这么写。
for(i=2;i<=n/2;i++)
再用if语句依次循环除
if(n%i==0)
之后输出就行了

Answer 4

从2到平方根求模，就是求余数。有余数为0的就不是素数。