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

서로 다른 두 개의 소인수를 갖는 수들이 처음으로 두 번 연달아 나오는 경우는 다음과 같습니다.

14 = 2 × 7
15 = 3 × 5

서로 다른 세 개의 소인수를 갖는 수들이 처음으로 세 번 연속되는 경우는 다음과 같습니다.

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19

서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우를 찾으세요. 그 첫번째 숫자는 얼마입니까?

일단 소인수분해를 하고

서로 다른 인수를 구하기 위해 set으로.. 담고

4개 이상 나오면 중간에 break..넣어서 속도 상승을 노렸으나

점심때 풀어서 돌려놓으니 점심 지나서 끝.. ㅋㅋ

일하다가 보니 끝나있어서.. 정확한 시간 측정은 못 함..;

Python

	def primefactors_limit_count(num):
	num_of_factors = 0
	limit_cnt = 4
	startnum=2
	primeNumbers=set()
	quota=0
	rest=0
	while True:
	quota=num/startnum
	rest=num%startnum
	if rest==0:
	num_of_factors += 1
	primeNumbers.add(startnum)
	startnum=2
	num=quota
	else:
	startnum=startnum+1
	if quota==1 and rest==0:
	break
	if num_of_factors > limit_cnt:
	break
	return primeNumbers
	n = 2
	cnt_of_continue = 0
	while True:
	prime_factors = primefactors_limit_count(n)
	if len(prime_factors) == 4:
	cnt_of_continue += 1
	else:
	cnt_of_continue = 0
	if cnt_of_continue == 4:
	print(n - 3)
	break
	n += 1

view raw 47.py hosted with ❤ by GitHub

Ruby

	require 'set'
	def primefactors(num)
	startnum=2
	primeNumbers=Set.new
	quota=0
	rest=0
	while true
	quota=num/startnum
	rest=num%startnum
	#puts "quota=#{quota}, rest=#{rest}, startnum=#{startnum}"
	if rest==0
	primeNumbers.add(startnum)
	startnum=2
	num=quota
	else
	startnum=startnum+1
	end
	if quota==1 and rest==0
	break
	end
	end
	return primeNumbers
	end
	n = 2
	cnt_of_continue = 0
	while (true)
	prime_factors = primefactors(n)
	if prime_factors.length() == 4
	cnt_of_continue += 1
	else
	cnt_of_continue = 0
	end
	if cnt_of_continue == 4
	puts n-3
	break
	end
	n += 1
	end

view raw 47.rb hosted with ❤ by GitHub

Perl

	use strict;
	use warnings;
	sub primefactors {
	my $num = shift @_;
	my $start_num = 2;
	my @prime_numbers = ();
	my $quota = 0;
	my $rest = 0;
	while (1) {
	$quota = $num / $start_num;
	$rest = $num % $start_num;
	if ($rest == 0) {
	unless (grep(/^$start_num$/, @prime_numbers)) {
	push @prime_numbers, $start_num;
	}
	($start_num, $num) = (2, $quota);
	} else {
	$start_num+=1;
	}
	if ($quota == 1 and $rest == 0) {
	last;
	}
	}
	@prime_numbers;
	}
	my $n = 2;
	my $cnt_of_continue = 0;
	while(1) {
	my @prime_factors = primefactors($n);
	if (scalar @prime_factors == 4) {
	$cnt_of_continue += 1;
	} else {
	$cnt_of_continue = 0;
	}
	if ($cnt_of_continue == 4) {
	print $n-3;
	last;
	}
	$n += 1;
	}

view raw 47.pl hosted with ❤ by GitHub