23-04-07 TIL 일지 : 효율적으로 소수 찾기

Today I Learned

---

어떤 문제가 있었는지

# 소수 찾기

# 문제 설명
# 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, 
# solution을 만들어 보세요.

# 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
# (1은 소수가 아닙니다.)

# 제한 조건
# n은 2이상 1000000이하의 자연수입니다.

소수찾기 문제들은 많이 풀어봐서 별 생각 없이 금방 풀었는데

답 제출할 때 시간 오버로 오답이 떴다 

---

내가 시도해 본 것들

n = 1000000

answer = 0
# 소수를 찾으면 answer +1
for i in range(2,n+1):
    count=0
    for j in range(1, i+1):
        if i%j == 0: count+=1
    if count ==1: answer+=1

print(answer)

그냥 평범한 소수찾기 답 코드였는데 시간초과가 떠서 

더 효율적으로 해야한다

 

n = 1000000

answer = 0
# 소수를 찾으면 answer +1
for i in range(2,n+1):
    count=0
    for j in range(1, int(i**(1/2))+1):
        if i%j == 0: count+=1
    if count ==1: answer+=1

print(answer)

range를 i의 제곱근으로 바꿨는데도 시간초과가 뜸

 

---

어떻게 해결 했는지

n = 1000000

for i in range(2,n+1):
    count=0
    for j in range(2, int(i**(1/2))+1):
        if i%j == 0: 
            count+=1
            break
    if count ==0: answer+=1

print(answer)

어차피 소수아닌 애들은 더미니깐 for문 다 돌때까지 기다릴 필요도 없음

그냥 바로 break 하니깐 통과했다. 

 

---

무엇을 새롭게 배웠는지

역시 제한된 리소스에서 절약할 수 있는 부분에서 효율적으로 코딩을 해야한다