判断一个数是否为素数
算法思想
设一个正整数x,sqrt(x)为x开平方后的值,若x不为素数,则x=a*b,a,b为2~x-1之间的整数,且当2=< a <= sqrt(x)时,必有sqrt(x)=< b<= x-1,即a和b必有一个数在2~sqrt(x)范围内,反推之,若x不可被2~sqrt(x)范围内的任何整数整除,则x必为素数。
代码实现
#include
#include
int main()
{
int x;
scanf("%d", &x);
printf("%d是否为素数: %d", x, IsPrime(x));
return 0;
}
int IsPrime(int x)
{
int i, squareRoot;
//小于或等于1的整数均不为素数,预先排除
if(x <= 1) return 0;
//sqrt(x)为开平方函数,其返回结果为浮点数,通过类型强转获得小于该浮点数的最大整数
squareRoot = (int)sqrt(x);
for(int i = 2;i <= squareRoot;i++)
{
//通过取余函数,若除得余数为0,说明x可被i整除,x不为素数
if(x%i == 0) return 0;
}
return 1;
}
求100以内的所有素数
算法思想
若一个正整数x不为素数,则它必定可以由两个或两个以上的素数的乘积表示,并且这几个素数中必定有一个素数小于或等于sqrt(x),即x必定可以被2~sqrt(x)中的一个素数整除。设一个数组int a[101];,使a[2]=2,a[3]=3,.....,a[100]=100,排除此数组中所有可以被2~sqrt(100)中的素数整除的数(素数本身除外),则剩下的元素数则均为素数。那么如何求2~sqrt(100)中的素数呢,很简单,不用求,首先从最小的素数2开始,将3~100中可以被2整除的数组元素置为0,然后往下循环,下一个不为0的数组元素必定为素数,一直循环至下一个不为0的数组元素大于sqrt(100)时,数组中可以被2~sqrt(100)中的素数整除的数均被置为0了,则数组中剩下不为0的数均为素数
代码实现
#include
#include
#define N 100
int main()
{
int a[N+1];
SiftPrime(a, N);
PrintPrime(a, N);
return 0;
}
void SiftPrime(int a[], int n)
{
//初始化数组元素
for(int i = 2;i <= n;i++)
{
a[i]=i;
}
for(int i = 2;i <= sqrt(n);i++)
{
//当a[i]不为0时,必定为素数
if(a[i] != 0)
{
//将a[i]之后所有不为0的数除以a[i]求余,若可整除,则不为素数,置为0
for(int j = i+1;j <= n;j++)
{
if(a[j] != 0 && a[j]%a[i] == 0)
a[j] = 0;
}
}
}
}
void PrintPrime(int a[], int n)
{
for(int i = 2;i < n;i++)
{
if(a[i] != 0)
printf("%d\t", a[i]);
}
}
来源:oschina
链接:/u/4057396/blog/3135667