[백준] 수학 2

백준 1978 소수찾기

문제

풀이

내 풀이

n = int(input())
arr = list(map(int, input().split()))
count = 0

for i in range(n):
    if arr[i] == 1:
        continue
    elif arr[i] == 2:
        count += 1
    elif arr[i] % 2 == 0:
        pass
    else:
        for j in range(2, arr[i] + 1):
            if arr[i] % j == 0:
                if arr[i] == j:
                    count += 1
print(count)

이렇게 풀이를 했는데, 사이트에서 오답으로 나와서 다른 풀이를 참고했다.

다른 풀이

N = int(input())
A = list(map(int, input().split()))
num_count = 0

for i in A:
	count = 0
	if i == 1:
		continue
	for j in range(2, i+1):
		if i%j == 0:
			count +=1
	if count == 1:
		num_count +=1
print(num_count)

어떤 방식으로 푸는지는 이해했는데,
내 답이 틀린 이유를 모르겟다.

맞다고 생각했는데, 틀렸다고 나오면
그래... 내 코드에 문제가 있겟지 생각한다
거의 99%는 내가 생각못한 실수에서 오류가 나기때문에 ㅋㅋㅋㅋ
컴퓨터는 나보다 똑똑하니까.....

에라토스테네스의 체

소수를 구하는 방식은

def prime_list(n):
  sieve=[True] * (n+1) # 소수는 True, 나머지는 False
  for i in range(2, int(n ** 0.5)+1):
    if sieve[i] == True:
      for j in range(i+i, n+1 , i): #간격을 i로 해주어, 소수의 배수를 지워준다.
        sieve[j]=False
  return [i for i in range(2,n+1) if sieve[i]==True]

# n의 숫자 범위에서 합성수를 지워나가면서, 소수를 구해주는 방법이다. 

[출처] [파이썬] : 에라토스테네스의 체 -소수 찾기|작성자 456

에라토스테네스의 체 : 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법.

소수를 찾는 방법 중에 가장 효율이 좋은 방법이다.

---

백준 2581 소수

문제

풀이

M = int(input())
N = int(input())
prime = []

for i in range(M, N + 1):
    count = 0
    for j in range(2, i + 1):
        if i % j == 0:
            count += 1
            if count > 2:
                break
    if count == 1:
        prime.append(i)
if len(prime) != 0:
    print(sum(prime))
    print(prime[0])
else:
    print("-1")

사실 위에 문제를 풀었으면, 이 문제는 크게 어렵지 않다.
그 뒤에 나오는것도 비슷하지 않을까 생각했다...

---

백준 1929 소수 구하기

문제

풀이

메모리를 어떻게 더 줄여야 할까
런타임 에러가 자꾸 나서 음... 짝수를 제외하고 해보기도 하고,
계산을 줄여보려고 여러가지 해봤는데,
런타임에러에서 벗어나질 못했다..
그러다 다들 얼마나 시간이 걸렸나 확인해보려고 들어가봤는데
역시 C 나 C++과의 차이를 확실하게 느낄 수 있엇다.
풀어보고 싶다.

---