파이썬_실전 프로젝트

프로젝트 오일러 12번문제 - 약수의 갯수

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

 

1부터 n까지 차례로 더해서 나오는 수의 약수의 갯수가 최초로 500개가 넘는 triangle number가 얼마인지를 찾으라는 문제이네요.

앞에서 몇번했던 방식으로, 루프만들고, 서브함수에서 약수의 갯수를 체크하면 될듯합니다.

 

먼저 루프문입니다.

i=1;t_number=0
while True:
    t_number=t_number+i
    count=factor_count(t_number)
    if count > 250:
    	break
	i+=1
    
print(t_number," has over 500 divisors")

t_number에 차례로 덧셈을 하면서, 더한수를 factor_count라는 서브함수에다가 넘겨줍니다.

서브함수 factor_count()는 앞에서 만들었던 소수체크와 유사합니다.

작은 루프를 만들고, 나눠서 나머지가 0으로 떨어지면, 약수이고, count에 1을 더합니다.

이 역시 숫자가 커질수록 시간이 많이 걸리기 때문에, 제곱근을 취해서,절반만 해주고, 대신, 메인함수에서 약수가 500개를 찾는게 아니라, 250만 찾도록 바꿔주면 됩니다.

def factor_count(number):
    i=2;count=1
	loop=number**0.5
	while i<loop:
		if number%i==0:
			count+=1
		i+=1
	return count

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
노마드
현재 버전
선택 버전
graphittie 자세히 보기