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

소수 중에서 각 자리의 숫자들을 순환시켜도 여전히 소수인 것을 circular prime이라고 합니다. 예를 들어 197은 971, 719가 모두 소수이므로 여기에 해당합니다.

이런 소수는 100 밑으로 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97 처럼 13개가 있습니다.

그러면 1,000,000 밑으로는 모두 몇 개나 있을까요?



처음에는 순열을 생각하고 순열을 생성했는데 답이 틀려서 문제를 좀 더 자세히 읽어보니
shift인것... 파이썬과 루비는 pop 메서드가 지원되어서 그걸 사용하였고
펄은 pop과 함께 unshift를 사용하여 순환수를 생성하였음...

펄에서 join 메서드 파라메터 잘못써서 디버깅에 몇 시간 투자한건..뭐..--; 내가 이거 때문에 어제 이 문제를 다 못 풀고 잤더랬지...
우선 2와 0이 들은 것은 순환수가 모두 소수가 되는 것은 불가능해서 제외.. 답 스레드를 보니 5나 기타 몇개도 추가로 제외가 가능한듯..
 

Python

	def isPrime(n):
	# http://www.daniweb.com/software-development/python/code/216880
	'''check if integer n is a prime'''
	# make sure n is a positive integer
	n = abs(int(n))
	# 0 and 1 are not primes
	if n < 2:
	return False
	# 2 is the only even prime number
	if n == 2:
	return True
	# all other even numbers are not primes
	if not n & 1:
	return False
	# range starts with 3 and only needs to go up the squareroot of n
	# for all odd numbers
	for x in range(3, int(n**0.5)+1, 2):
	if n % x == 0:
	return False
	return True
	def getCircularList(n):
	n_list = [c for c in (str(n))]
	result_list = list()
	loop_cnt = len(str(n)) - 1
	result_list.append(n)
	while (loop_cnt > 0):
	t = n_list.pop(-1)
	n_list.insert(0, t)
	result_list.append(int("".join(str(c) for c in n_list)))
	loop_cnt = loop_cnt - 1
	return result_list
	r_list = list()
	for n in range(0,1000000):
	n_str = str(n)
	if n_str != 2 and "2" in n_str:
	next
	if "0" in n_str:
	next
	c_list = getCircularList(n)
	all_prime=True
	for p in c_list:
	if not isPrime(p):
	all_prime = False
	break
	if all_prime:
	r_list.append(n)
	print (len(r_list))
	print (r_list)

view raw 35.py hosted with ❤ by GitHub

Ruby

	require 'mathn'
	def isPrime(n)
	return n.prime?
	end
	def getCircularList(n)
	n_list = Array.new
	n.to_s.each_char{|c| n_list.push(c)}
	result_list = Array.new
	loop_cnt = n.to_s.length - 1
	result_list.push(n)
	while (loop_cnt > 0)
	n_list.rotate!
	result_list.push(n_list.join.to_i)
	loop_cnt -= 1
	end
	return result_list
	end
	r_list = Array.new
	(0..999999).each do |n|
	n_str = n.to_s
	if n_str != 2 and n_str.include? "2"
	next
	end
	if n_str.include? "0"
	next
	end
	c_list = getCircularList(n)
	all_prime = true
	c_list.each do |c|
	if not isPrime(c)
	all_prime = false
	break
	end
	end
	if all_prime
	r_list.push(n)
	end
	end
	puts r_list.size

view raw 35.rb hosted with ❤ by GitHub

Perl

	use strict;
	use warnings;
	sub isPrime
	{
	my ($number) = @_;
	$number = abs $number;
	my $sqrt = sqrt $number;
	my $d = 2;
	while (1)
	{
	return 0 if ( $number % $d == 0 );
	return 1 if ( $d > $sqrt );
	$d++;
	}
	}
	sub get_circular_list {
	my ($n) = @_;
	my @n_list = split //, $n;
	my @result_list=();
	my $loop_cnt = length $n - 1;
	push @result_list, $n;
	while ($loop_cnt > 0) {
	my $t = pop @n_list;
	unshift @n_list, $t;
	my $st = join("", @n_list);
	push @result_list, $st;
	$loop_cnt -= 1;
	}
	return @result_list;
	}
	my @r_list = ();
	foreach my $n ((0..999999)) {
	if ($n != 2 and $n =~ m/2/) {
	next;
	}
	if ($n =~ m/0/) {
	next;
	}
	my @c_list = get_circular_list($n);
	my $all_prime = 1;
	foreach my $c (@c_list) {
	unless (isPrime($c)) {
	$all_prime = 0;
	last;
	}
	}
	if ($all_prime) {
	push @r_list, $n;
	}
	}
	my $r = @r_list;
	print "$r";

view raw 35.pl hosted with ❤ by GitHub