埃拉托斯特尼筛法&素数定理

算法

先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个素数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；不断重复下去......

代码

int m = floor(sqrt(n) + 0.5);
memset( vis, 0, sizeof( vis ) )
for( int i = 2; i <= m; i ++ )
{
    if( !vis[ i ] )
    {
        for( int j = i * i; j <= n; j += i ) vis[ j ] = 1;
    }
}

素数定理

定义π(x)为不大于x的素数个数,则π(x) ~ ( x / lnx )

唯一分解定理

任何大于１的自然数，都可以唯一分解成有限个质数的乘积

byene.jpg