以前寫的找質數函數

以前寫的找質數函數
真懷念那為了這樣幾行小程式而絞盡腦汁的日子(遠目)

以 6n+1 6n-1 法檢驗 n 是否為質數

bool isPrime( const DWORD n ){
    if( n < 2 )
        return FALSE;
    if( n == 2 || n == 3 )
        return TRUE;
    if( !(n%2) || !(n%3) )
        return FALSE;
    DWORD limit = (DWORD)sqrt( (double)n );
    for( DWORD i=5, gap=2; i<=limit; i+=gap, gap=6-gap ){
        if( !(n%i) ){
            return FALSE;
        }
    }
    return TRUE;
}

以 Eratosthenes 篩法找出 n 以下的質數

bool* eratosthenes( const DWORD n ){
    bool* pPrime = new bool[n+1];
    pPrime[0] = pPrime[1] = FALSE;
    for( DWORD i=2; i<=n; ++i ){
        pPrime[i] = TRUE;
    }
    DWORD limit = (DWORD)sqrt( (double)n );
    for( DWORD i=2; i<limit; ++i ){
        if( pPrime[i] ){
            for( DWORD j=i*i; j<=n; j+=i ){
                pPrime[j] = FALSE;
            }
        }
    }
    return pPrime;
}