[Project Euler] Problem 1 ~ 7번 알고리즘 풀이

1. 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면?

s = 0
for i in range(1000):
    if i%3==0 or i%5==0:
        s = s + i
    else:
        pass
    
print(s)

---

2. 4백만 이하의 짝수 값을 갖는 모든 피보나치 항을 더하면 ?

n1 = 0
n2 = 1
n3 = n1+n2
result = 0

while n3<=4000000:
  n3 = n1+n2
  # print(n3)
  n1 = n2
  n2 = n3

  if n3 % 2==0:
    result += n3

print('result_sum : ', result)

---

3. 600851475143의 소인수 중에서 가장 큰 수

a = 600851475143 
i = 2 
num = []
while (i<=a):
    if a%i==0:  
        num.append(i)  # 소인수 모음 
        a = a//i   # 이게 열쇠이다!
    i = i+1
print(max(num))

 

5.  1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수 (최소공배수)

for i in range(20,1000000000,20):    # 20씩 뛰면서 진행
  for a in range(1,20):
    if i%a != 0 :   # 나머지가 0이 아니면 멈추고 다음수로, 0이면 a 바꿔가면서 계속 진행
      break
    if a >= 19:
      print (i) 

---

6.  1부터 100까지 "제곱의 합"과 "합의 제곱"의 차는?

num = 1
a = 0  # 합의 제곱
b = 0  # 제곱의 합
while (num<=100):
  a += num
  b+= num**2
  num += 1    # 합의제곱
print('제곱의 합과 합의 제곱의 차 : ', a**2 - b)

 

---

7. 10001번째의 소수 구하기

num = 1   
i = 1
# 우선 True로 설정
while (num<=10002):
    i +=1 
    result = True  # True, False 이용
    for j in range(2, i):
      if i % j ==0:
        result = False
        break
        
    if result == True:
      num+=1
      if num == 10002:
        print('10001번째 소수 : ', i)   # 51초정도 걸림

cf) 에리토스테네스의 체 : 소수를 구하는 알고리즘

- 찾고자 하는 자연수를 배열로 나열하여 그 중에 소수의 배수들을 전부 지워나가면 남는 수가 소수가 됨 
- 시간복잡도를 매우 줄일 수 있음

코드 적용!

n = 104743
a = [False, False] + [True] * (n-1)   # False 두번, True가 n-1번 등장
소수 = []

for i in range(2, n+1):
  if a[i] == True:
    소수.append(i)  # 우선 소수로 추가
    
    for j in range(2*i, n+1, i):   # 소수의 배수를 지워간다 
      a[j] = False

print(소수)
print(len(소수))