C｜暴力和筛法求100以内的素数

素数是指除1以外只能被1和自身整除的整数。

1 从定义出发的暴力法

#include 
bool isPrime(int n)
{
    int ret = 0;
    for(int i=1;i<=n;i++) // 边界为[1,n]
    {
        if(n%i == 0)
            ret++;
    }
    if(ret == 2)
        return true;
    return false;
}
int main()
{
    for(int i=1;i<100;i++)
        if(isPrime(i))
            printf("%d ",i);
    getchar();
}

2 暴力结合枚举和边界

#include 

double sqrt(double x,double y)
{
    if(y*y-x<-1e-5 || y*y-x > 1e-5)
        return sqrt(x,(y+x/y)/2.0);
    else
        return y;
}
bool isPrime(int n)
{
    if(n<2) return false;
    if(n==2) return true;
    if(n%2==0) return false;
    int limit = sqrt(n,n/2)+1;
    for(int i=3;i

3 埃拉托斯特尼素数筛法

素数筛法的思路是：从2开始，不包括2本身，其倍数全部筛掉，剩下的全是素数。

先是筛2的倍数，筛完后剩下的最小整数是3，然后筛3的倍数；

然后筛5的倍数……

demo code:

#include 
#include 
#include 
#include 
#define N 100
void prime(int n)
{
    int *arr = (int*)malloc(sizeof(int)*(n+1));
    memset(arr,0,sizeof(int)*(n+1));// arr[i]==0表示i是素数
    arr[1] = 1;
    int m = sqrt(n)+1;
    for(int i=2;i

埃拉托色尼（Eratosthenes，公元前275一前193）生于希腊在非洲北部的殖民地昔兰尼（cyrene，在今利比亚）。他在昔兰尼和雅典接受了良好的教育，成为了一位博学的哲学家、诗人、天文学家和地理学家。他的兴趣是多方面的，不过他的成就则主要表现在地理学和天文学方面。

－End－