以前寫的找質數函數

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

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

view source

print?

01	bool isPrime( const DWORD n ){

02	if( n < 2 )

03	return FALSE;

04	if( n == 2 || n == 3 )

05	return TRUE;

06	if( !(n%2) || !(n%3) )

07	return FALSE;

08	DWORD limit = (DWORD)sqrt( (double)n );

09	for( DWORD i=5, gap=2; i<=limit; i+=gap, gap=6-gap ){

10	if( !(n%i) ){

11	return FALSE;

12

}

13

}

14	return TRUE;

15

}

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

view source

print?

01	bool* eratosthenes( const DWORD n ){

02	bool* pPrime = new bool[n+1];

03	pPrime[0] = pPrime[1] = FALSE;

04	for( DWORD i=2; i<=n; ++i ){

05	pPrime[i] = TRUE;

06

}

07	DWORD limit = (DWORD)sqrt( (double)n );

08	for( DWORD i=2; i<limit; ++i ){

09	if( pPrime[i] ){

10	for( DWORD j=i*i; j<=n; j+=i ){

11	pPrime[j] = FALSE;

12

}

13

}

14

}

15	return pPrime;

16

}