开平方法:
代码
#include <stdio.h>
#include <math.h>
int main()
{
int num;
int data = sqrt(num);
for(int i=2;i<=data;i++)
if(num%i==0) return 1;
return 0;
}
素数筛法
求小于N的所有素数：
①用一个长度N+1的数组保存信息（true->素数，false->非素数）。
②先假设≤N的数都是素数（初始化为true），从第一个素数2开始，把2的倍数（不包括2）都标记为非素数（置为false），一直到＞N。
③从2的下一个数开始，重复步骤2，一直到最后。
④当数组中依然为true的数就是素数。
算法复杂度为O(nlog(logn));
埃氏筛法的代码
#include <stdio.h>
#include <stdbool.h>
#define N 10000
int main()
{
bool number[N+1];
int i,j;
memset(number,true,sizeof(number));
for(i=2;i<=sqrt(N);i++)
{
if(number[i]==true) //如果i是素数
{
for(j=2;j*i<=N;j++)
{
number[i*j]=false;//则i的倍数都不是素数
}
}
}
for(i=2;i<N+1;i++)
if(number[i]==true) printf("%d ",i);
return 0;
}
