[ create a new paste ] login | about

Link: http://codepad.org/tj215xuh    [ raw code | fork ]

C, pasted on Mar 25:
/*
	*3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる.

	56**3の第3桁と第4桁を同じ数で置き換ることを考えよう.
	この5桁の数は7つの素数をもつ最初の例である:
	56003, 56113, 56333, 56443, 56663, 56773, 56993.
	よって, この族の最初の数である56003は, このような性質を持つ最小の素数である.

	桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ.
	(注:連続した桁でなくても良い)
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int binSearch(int a, int num[], int size) {
	int s = 0, e = size - 1, m;

	if( a < num[s] ) return -1;
	if( a == num[s] ) return s;
	if( num[e] < a ) return size;

	while( e - s > 1 ) {
		m = (s + e) / 2;
		if( a <= num[m] ) e = m;
		else s = m;
	}

	return e;
}

int main(void) {
	int *prime, size;
	int num[6], digit, val;
	int flag, end = 0;
	int cnt;
	int min;
	int tmp;
	int i, j, k, replace;

	// 素数表より
	prime = (int *)malloc(sizeof(int) * 1000000);
	i = 0;
	while( scanf("%d", prime + i) != EOF ) i++;
	prime[i] = -1;
	size = i;

	for( i = 0; prime[i] != -1; i++ ) {
		tmp = prime[i];
		digit = 0;
		while( tmp > 0 ) {
			num[digit++] = tmp % 10;
			tmp /= 10;
		}
		for( j = 1; j < 2 << (digit - 1); j++ ) {
			tmp = prime[i];
			digit = 0;
			while( tmp > 0 ) {
				num[digit++] = tmp % 10;
				tmp /= 10;
			}
			cnt = 0;
			for( replace = 0; replace <= 9; replace++ ) {
				flag = 0;
				for( k = 0; k < digit; k++ ) {
					if( (j & 1 << k) != 0 ) {
						if( (k == 0 && replace % 2 == 0) || (k == digit - 1 && replace == 0) ) {
							flag = 1;
							break;
						}
						num[k] = replace;
					}
				}
				if( flag ) continue;
				val = 0;
				for( k = digit - 1; k >= 0; k-- ) {
					val = val * 10 + num[k];
				}
				k = binSearch(val, prime, size);
				if( val == prime[k] ) {
					if( cnt == 0 ) min = prime[k];
					cnt++;
				}
				if( cnt == 8 ) {
					printf("%d\n", min);
					end = 1;
					break;
				}
			}
			if( end ) break;
		}
		if( end ) break;
	}

	return 0;
}


Create a new paste based on this one


Comments: