小型素数判断

使用方法

  1. 打素数表时需要调用Init_Prime()
  2. bool isprime = isPrime(n);

模版

无素数表时

bool isPrime(int n)  
{  
    if(n==2)return 1;  
    if(n%2==0||n<2) return 0;  
    int l=sqrt(n+1);  
     for(int i=3;i<=l;i+=2)  
      if(n%i==0)return 0;  
    return 1;  
 }

有素数表时

说明: 素数表为prime[i] 下标由1~pcnt-1

ll prime[maxn]={1};
int pcnt=0;//素数下标1~pcnt-1
int factor[maxn]={1,1}; //factor[i]表示i的最小质因子
void Init_Prime(){
    pcnt=1;
    for(ll i = 2 ; i < maxn ; i ++){
        if(!factor[i]) {
            prime[pcnt++]=i;
            factor[i]=i;
        }
        for(ll j = 1 ; j < pcnt && i * prime[j] <  maxn ; j ++)
        {
            factor[i * prime[j]] = prime[j];
            if( !(i % prime[j] ) )
                break;
        }
    }
    return;
}
bool isPrime(int n)
{
    if(n==2)return 1;
    if(n%2==0||n<2) return 0;
    int l=sqrt(n+1);
    for(int i=2;prime[i]<=l;i++)
        if(n%prime[i]==0)return 0;
    return 1;
}

results matching ""

    No results matching ""