数论_素数判定.cpp

来自「一些ACM基本算法的测试源码」· C++ 代码 · 共 51 行

#include<iostream>
using namespace std;

const int MAXN = 100001;

int pcount = 0;
bool num[MAXN];
int plist[MAXN];
/*
int prime(int n)
{
    if((n != 2 && !(n % 2)) || (n != 3 && !(n % 3)) || (n != 5 && !(n % 5)) || (n != 7 && !(n % 7)))
        return 0;
    for(int i = 0; plist[i] * plist[i] <= n; i ++)
        if(!(n % plist[i]))  
            return 0;
    return n > 1;   
}

void initprime(int num)
{
    int i;
    for(plist[pcount ++] = 2, i = 3; i < num; i ++) 
        if(prime(i))
            plist[pcount ++] = i;    
}
*/
void initprime(int n)
{
    memset(num, true, sizeof(num));
    for(int i = 2; i < n; i ++)
    {
        if(num[i])  plist[pcount ++] = i;
        for(int j = 0; j < pcount; j ++)
        {
            int temp = i * plist[j];
            if(temp >= n)  break;
            num[temp] = false;        
        }        
    }     
}

int main()
{
    initprime(101);
    for(int i = 0; i < pcount; i ++)
        printf("%d\n", plist[i]);
    system("pause");
    return 0;    
}