指定された数値Xが素数であるかどうかを判定する

素数判定法

簡単な公式は無いので地道に頑張る
というか公式を見つけたら大発見

ある数の素数性を得るためのフェルマー法とかミラー法とかミラー・ラビン法とかを使えば相当の高速化が期待できるから十分に知っているなら使ってもいいとは思うけど、あくまでも「ホワイトボード」プログラミングなのでそういったアルゴリズムを使うか使わないかはあまり意味がないと思うよ

ループ

何にもわからなかったらベタにでもいいからまずは何か書いてみること
小さい方の素因数は元の数の平方根より大きくならないことを利用して

// n は素数かな
bool	is_prime_number( int	n ){
	bool	result = true;
	if( n == 2 ){
		result = true;
	}
	else if(( n < 2 )|| !( n & 1 )){
		result = false;
	}
	else{
		// prime_factor は素因数。2 より大きい最小の素数は 3 なので 3 から始めるよ
		int	prime_factor = 3;
		// 小さい方の素因数の二乗は必ず n 以下だから √n 以下の素数で割り切れなければ n は素数だよ
		while(( prime_factor * prime_factor <= n )&&( n % prime_factor )){
			prime_factor += 2;
		}
		result = ( prime_factor * prime_factor > n );
	}
	return	result;
}

// n より大きい最小の素数を得る
int    prime_number_next( int    n ){
    if( n < 2 ){
        n = 2;
    }
    else if( n < 3 ){
        n = 3;
    }
    else{
        if( !( n & 1 )){
            --n;
        }
        do{
            n += 2;
        }while( !is_prime_number( n ));
    }
    return    n;
}

int    main(){
    int    cprime_numbers = 0;
    for( int    n = 0; n < 100; ++n ){
        if( is_prime_number( n )){
            debug_printf( "%d,", n );
            ++cprime_numbers;
        }
    }
    debug_printf( "\n" );
    {
        int    n = 0;
        for( int    m = 0; m < cprime_numbers; ++m ){
            n = prime_number_next( n );
            debug_printf( "%d,", n );
        }
    }
    debug_printf( "\n" );
    return    0;
}

少し高速化

5以上の素数は決して 2 でも 3 でも割り切れないので必ず 3*2*m-1 か 3*2*m+1 になることを利用して

// n は素数かな？
bool	is_prime_number( int	n ){
	bool	result = true;
	if(( n == 2 )||( n == 3 )){
		result = true;
	}
	else if(( n < 2 )|| !( n & 1 )){
		result = false;
	}
	else{
		// 5以上の素数は決して 2 でも 3 でも割り切れないので必ず 3*2*m-1 か 3*2*m+1 になる
		int	n1 = n+1;
		int	n2 = n-1;
		if(( n1 % (2*3))&&( n2 % (2*3))){
			// ということは素数の前後の数は 3*2*m-1+1 か 3*2*m+1-1 になり、つまり少なくともどちらかは必ず 6 の倍数なので、そうじゃなかったらダメ
			result = false;
		}
		else{
			// 残りは地道に調べる
			// 小さい方の素因数は元の数の平方根より大きくはならないのでそこまでチェックすれば十分
			int	m = 1;
			for(;;){
				int	prime_factor1 = 3 * 2 * m - 1;
				int	prime_factor2 = 3 * 2 * m + 1;
				if( prime_factor1 * prime_factor1 > n ){
					break;
				}
				else if( !( n % prime_factor1 )){
					result = false;
					break;
				}
				else if( prime_factor2 * prime_factor2 > n ){
					break;
				}
				else if( !( n % prime_factor2 )){
					result = false;
					break;
				}
				++m;
			}
		}
	}
	return	result;
}

// n より大きい最小の素数を得る
int	prime_number_next( int	n ){
	if( n < 2 ){
		n = 2;
	}
	else if( n < 3 ){
		n = 3;
	}
	else{
		if( !( n & 1 )){
			--n;
		}
		do{
			n += 2;
		}while( !is_prime_number( n ));
	}
	return	n;
}

int	main(){
	int	cprime_numbers = 0;
	for( int	n = 0; n < 100; ++n ){
		if( is_prime_number( n )){
			debug_printf( "%d,", n );
			++cprime_numbers;
		}
	}
	debug_printf( "\n" );
	{
		int	n = 0;
		for( int	m = 0; m < cprime_numbers; ++m ){
			n = prime_number_next( n );
			debug_printf( "%d,", n );
		}
	}
	debug_printf( "\n" );
	return	0;
}

テンプレート：その１

素数かどうかをチェックする対象が定数なのであれば、テンプレートを使ってコンパイル時に調べることもできます
（コンパイル時間が長くなります）

template<int n> struct is_even_t {
	static const int	value = !( n & 1 );
};
template<int n,int prime_factor> struct is_prime_loop_helper_t {
	static const int	value = ( prime_factor * prime_factor > n );
};
template<int n, int prime_factor = 3,bool = is_even_t<n>::value,bool = is_prime_loop_helper_t<n,prime_factor>::value> struct is_prime_t {
	static const bool	value = ( n % prime_factor )&& is_prime_t<n,prime_factor+2,is_even_t<n>::value,is_prime_loop_helper_t<n,prime_factor+2>::value>::value;
};
template<int n,int prime_factor> struct is_prime_t<n,prime_factor,false,true> {
	static const bool	value = true;
};
template<int n,int prime_factor> struct is_prime_t<n,prime_factor,true,true> {
	static const bool	value = false;
};
template<int prime_factor> struct is_prime_t<1,prime_factor,false,true> {
	static const bool	value = false;
};
template<int prime_factor> struct is_prime_t<2,prime_factor,true,true> {
	static const bool	value = true;
};
template<int prime_factor> struct is_prime_t<3,prime_factor,false,true> {
	static const bool	value = true;
};
#define	is_prime_number( n )	is_prime_t<(n)>::value

template<int N,int n = 1> struct prime_print_t {
	static void	print(){
		if( is_prime_number( n )){
			debug_printf( "%d,\n", n );
		}
		prime_print_t<N,n+1>::print();
	}
};
template<int N> struct prime_print_t<N,1> {
	static void	print(){
		if( is_prime_number( 1 )){
			debug_printf( "1,\n" );
		}
		prime_print_t<N,1+1>::print();
	}
};
template<int n> struct prime_print_t<n,n> {
	static void	print(){
	}
};
template<int N> static void	prime_print(){
	prime_print_t<N>::print();
}
int	main(){
	prime_print<100>();
	return	0;
}

テンプレート：その２

素数かどうかをチェックするのではなくコンパイル時に n 番目の素数がほしいという場合もテンプレートを使って書くことができます
（コンパイル時間が長くなります）

template<int lhs,int rhs> struct less_than_or_equal_to_t {
	static const bool	value = ( lhs <= rhs );
};
template<int nth,int n = 0,int prime_number = 2,bool = is_prime_t<prime_number>::value,bool = less_than_or_equal_to_t<nth,n>::value> struct nth_prime_number_t {
	static const int	value = nth_prime_number_t<nth,n,prime_number+2,is_prime_t<prime_number+2>::value,less_than_or_equal_to_t<nth,n>::value>::value;
};
template<int nth,int n,int prime_number> struct nth_prime_number_t<nth,n,prime_number,true,false> {
	static const int	value = nth_prime_number_t<nth,n+1,prime_number+2,is_prime_t<prime_number+2>::value,less_than_or_equal_to_t<nth,n+1>::value>::value;
};
template<int nth> struct nth_prime_number_t<nth,0,2,true,false> {
	static const int	value = nth_prime_number_t<nth,1,3,is_prime_t<3>::value,less_than_or_equal_to_t<nth,1>::value>::value;
};
template<int nth,int n,int prime_number> struct nth_prime_number_t<nth,n,prime_number,true,true> {
	static const int	value = prime_number;
};
template<> struct nth_prime_number_t<0,0,2,true,true> {
	static const int	value = 2;
};
template<> struct nth_prime_number_t<1,1,3,true,true> {
	static const int	value = 3;
};

template<int N,int n = 0> struct prime_print_t {
	static void	print(){
		debug_printf( "%d,\n", nth_prime_number_t<n>::value );
		prime_print_t<N,n+1>::print();
	}
};
template<int n> struct prime_print_t<n,n> {
	static void	print(){
	}
};
template<int N> static void	prime_print(){
	prime_print_t<N>::print();
}
int	main(){
	prime_print<100>();
	return	0;
}