// 埃氏筛// a[i]==0 is prime
char a[MAXN];void sieve( ll n )
{memset( a,0,sizeof(a) );ll temp=(ll)sqrt(n),i,j;for( i=3;i<=temp;i+=2 ){// 直接 !a[i] 判断是否为素数if( !a[i] ) for( j=i*i;j<=n;j+=i ) a[j]=1;// 同样运用 开方求素数 减少循环次数if( i*i>n ) break;}
}// 六素数法int prime( ll n )
{if( n<=3 ) return n>1;else if( n%2==0 || n%3==0 ) return 0;ll temp=(ll)sqrt(n),i;for( i=5;i<=temp;i+=6 ){if( n%i==0 || n%(i+2)==0 ) return 0;}return 1;
}// 最大质因子ll max_prime_factor( ll n )
{ll i,maxf=0;for( i=2;i*i<=n;i++ ){if( n%i==0 ){if( maxf<i ) maxf=i;while( n%i==0 ) n/=i;}}return maxf>n?maxf:n;
}