学步园

一:

最常用,但是也是效率最低的

直接判断法

code:

#include <cstdio>

bool is_prime(int n)
{
    if (n == 1 || !n)
        return 0;
    for (int i = 2; i*i <= n; i++)
        if (!(n%i))
            return 0;
    return 1;
}

int main()
{
    int N;
    while (~scanf("%d",&N))
    {
        if (is_prime(N))
            printf("%d is a prime!\n",N);
        else
            printf("%d is not a prime!\n",N);
    }
}

二:

构造素数表法:

运用时,首先打表,效率会提升很多

code:

#include <cstdio>

const int MAXN = 101;
bool prime[MAXN];

bool is_prime(int n)
{
    if (n == 1 || n == 0)//不要忘记特判特殊情况,不过有的时候,OJ也判不出来,水过....
        return 0;
    else
        for (int i = 2; i*i <= n; i++)
            if (!(n % i))
                return 0;
    return 1;
}

void init()
{
    for (int i = 0; i < MAXN; i++)
        prime[i] = is_prime(i);
}

int main()
{
    init();//一定不要忘记调用
    int N;
    while (~scanf("%d",&N))
    {
        if (prime[N])
            printf("%d is a prime!\n",N);
        else
            printf("%d is not a prime!\n",N);
    }
}

三:

位向量法构造素数表

首先判定N一个数是否是素数,然后从N~MAXN把所有N的倍数都去掉,效率很高

#include <cstdio>
#include <cstring>

const int MAXN = 101;
bool prime[MAXN];

bool is_prime(int n)
{
    if (n == 1 || n == 0)
        return 0;
    else
        for (int i = 2; i*i <= n; i++)
            if (!(n % i))
                return 0;
    return 1;
}

void init()
{
    memset(prime,1,sizeof(prime));
    prime[0] = prime[1] = 0;// 首先将0,1置为0;
    for (int i = 2; i < MAXN; i++)
        if (prime[i] && is_prime(i))
        {
            //将其所有的倍数都去掉;
            for (int j = i*2; j < MAXN; j+=i)
                prime[j] = 0;
        }
}

int main()
{
 //   freopen("input.txt","r",stdin);
    init();
    int N;
    while (~scanf("%d",&N))
    {
        if (prime[N])
            printf("%d is a prime!\n",N);
        else
            printf("%d is not a prime!\n",N);
    }
}