如何判断一个数是否是素数

开平方法:

代码

#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;
}