[오일러프로젝트] 51번문제

13 이라는 두 자리 소수의 첫째 자리 숫자를 여러가지로 바꿨을 때 가능한 결과는 모두 9개이고, 그 중에서 13, 23, 43, 53, 73, 83의 여섯 개가 소수입니다.

56003 이라는 소수의 3번째와 4번째 자리는 둘 다 0으로 같은데, 이것을 다른 숫자로 바꿔보면 아래와 같이 모두 10개 중에서 7개가 소수입니다. 이것은 이런 식으로 하여 7개의 소수가 나타나는 첫번째 경우입니다.

56003, 56113, 56333, 56443, 56663, 56773, 56993

위의 예처럼 원래의 일부를 동일한 숫자로 치환했을 때, 10개 중에서 8개가 소수가 되는 가장 작은 소수를 구하세요.
치환하는 자리는 인접하지 않아도 되고, 가장 앞부분을 치환하는 경우 거기에 0 은 올 수 없습니다.

문제에러..
8개가 되는 가장 작은 소수가 아니라.. 8개의 소수중 가장 소수를 찾은거..
계속 120383이 답으로 나오는데.. 실제 답은 121313이라고 되어서 왜 그런지
한참 찾았음 -_-

Python

	def isPrime(n):
	n = abs(int(n))
	if n < 2:
	return False
	if n == 2:
	return True
	if not n & 1:
	return False
	for x in range(3, int(n**0.5)+1, 2):
	if n % x == 0:
	return False
	return True
	max = 1000000
	min = 100000
	prime_list = [int(n) for n in range(min, max) if isPrime(n)]
	patterns = ['110001','101001','100101','100011','011001','010101','010011','001101','001011','000111']
	#patterns = ['11001','10101','10011','10001','10111','11011','11101']
	#prime_list = [120383]
	for p in prime_list:
	for pat in patterns:
	replace_num_list = []
	for i in range(0,10):
	p_index = 0
	replace_num = ""
	for c in pat:
	if c == str(1):
	replace_num = replace_num + str(p)[p_index]
	else:
	replace_num = replace_num + str(i)
	p_index += 1
	if not replace_num in replace_num_list:
	replace_num_list.append(replace_num)
	print (replace_num_list)
	cnt = 0
	for n in replace_num_list:
	if int(n) > 99999 and isPrime(n):
	print (p, n)
	cnt += 1
	if cnt == 8:
	print ("result : ", p)
	import sys; sys.exit()

view raw 51.py hosted with ❤ by GitHub

Ruby

	require 'mathn'
	def isPrime(n)
	return n.to_i.prime?
	end
	max = 1000000
	min = 100000
	primes = Array.new
	(min..max).each do |n|
	if isPrime(n)
	primes.push(n.to_i)
	end
	end
	patterns = ['110001','101001','100101','100011','011001','010101','010011','001101','001011','000111']
	primes.each do |p|
	patterns.each do |pat|
	replace_num_list = []
	(0..9).each do |i|
	p_index = 0
	replace_num = ""
	pat.each_char do |c|
	if c == "1"
	replace_num = replace_num + p.to_s[p_index]
	else
	replace_num = replace_num + i.to_s
	end
	p_index += 1
	end
	if not replace_num_list.include?(replace_num)
	replace_num_list.push(replace_num)
	end
	end
	cnt = 0
	replace_num_list.each do |n|
	if n.to_i > 99999 and isPrime(n)
	cnt += 1
	#puts p, n
	end
	end
	if cnt == 8
	puts p
	Process.exit!(true)
	end
	end
	end

view raw 51.rb hosted with ❤ by GitHub

Perl

	use strict;
	use warnings;
	sub is_prime_number {
	my($num) = @_;
	my $t=2;
	while ($t <= $num) {
	my $rest = $num % $t;
	if ($rest==0 and $t==$num) {
	return 1;
	} elsif ($rest == 0 and $t != $num) {
	return 0;
	} else {
	$t+=1;
	}
	}
	0;
	}
	my $max = 1000000;
	my $min = 100000;
	my @primes;
	foreach my $n (($min..$max)) {
	if (is_prime_number($n)) {
	push @primes, $n;
	}
	}
	my @patterns = qw \110001 101001 100101 100011 011001 010101 010011 001101 001011 000111\;
	foreach my $p (@primes) {
	for my $pat (@patterns) {
	my @replace_num_list;
	foreach my $i (0..9) {
	my $p_index = 0;
	my $replace_num = "";
	foreach my $c (split //, $pat) {
	if ($c == "1") {
	my @temp_l = split //, $p;
	$replace_num = $replace_num.$temp_l[$p_index];
	} else {
	$replace_num = $replace_num.$i;
	}
	$p_index += 1;
	}
	if (!grep {$_ eq $replace_num} @replace_num_list) {
	push @replace_num_list, $replace_num;
	}
	}
	my $cnt = 0;
	foreach my $n (@replace_num_list) {
	if ($n > 99999 && is_prime_number($n)) {
	$cnt += 1;
	}
	}
	if ($cnt == 8) {
	print "$p";
	exit 0;
	}
	}
	}

view raw 51.pl hosted with ❤ by GitHub