[백준] 소수 판별

 

#1978번 (입력한 수들 중 소수의 개수 출력)

n=int(input())
lst=list(map(int,input().split()))

for x in lst[:]:
  if x>2:
    for i in range(2,x):
      if x%i==0:
        lst.remove(x)
        break
if 1 in lst:
  lst.remove(1)
print(len(lst))

** list for문 돌리는 중에 list에 요소 삭제, 추가 등의 변화가 생기면 for문에서도 변화가 생기므로

반복문에서는 원래의 list로 바로 반복문 돌리는 게 아니라

원래 list는 두고, 복사한 list로 반복문을 돌린다. 

ex. list[:] ==> list 복사

 

근데 소수 찾는 방법은 함수를 사용하는 것이 더 생각하기 쉬운 것 같다.

백준 알고리즘 1978번(python 파이썬) :: 깨지고 부서져라 (tistory.com)

백준 알고리즘 1978번(python 파이썬)

 

#2581 (m 이상 n 이하의 소수들 합과 최솟값)

m=int(input())
n=int(input())
sosu=[]
if n==2:
  sosu.append(2)
elif n>2:
  for i in range(m,n+1):
    sosu.append(i)
    if i==2:
      continue
    if i==1:
      sosu.remove(i)
    for j in range(2,i):
      if i%j==0:
        sosu.remove(i)
        break
if len(sosu)==0:
  print(-1)
else:
  print(sum(sosu))
  print(min(sosu))

m, n이 1이거나 2라서 range(2,~) 에서 범위 에러뜨는 경우 주의.

 

 

#11653 (입력한 수를 소인수분해하여 소인수들을 출력하기)

문제는,, 이렇게 함수를 만들어버리는 게 편하구나...! 깨닫자마자 푼 이 문제는,,

아주 쉽고 짧게 짤 수 있는 걸

함수 만들고... 반복문 몇개씩 돌리고... 난리가 나버림:

def prime(x):
  if x==1:
    return False
  elif x==2:
    return True
  else: # x는 항상 자연수만 입력된다는 전제 하에..
    for i in range(2,x):
      if x%i==0:
        return False
    return True
  
n=int(input())
soinsu=[]

while True:
  if prime(n):
    soinsu.append(n)
    break
  if n>2:
    for i in range(2,n):
      if prime(i):
        if n%i==0:
          soinsu.append(i)
          n=n//i
          break
for x in soinsu:
  print(x)

답은 나오는데

당연히 시간초과가 나고 ㅋㅋㅋㅋㅋ

다른 사람 답이 한 다섯 줄로 짜여있는 거 보고 충격받았다.

다시 짠 코드:

n=int(input())
i=2   # 제일 작은 소수 2부터 시작.
while n!=1:  #n이 1이 될 때까지.. 
  if n%i==0:
    n=n//i
    print(i)
  else:
    i+=1

어차피 순차적으로 제일 작은 소수부터 나누어주다보면 소수만 남게 됨.... 그니까 그냥 제일 작은 소수부터 +1 해주면서 따져나가면 된다구..

 

 

#1929 (m이상 n이하의 소수를 모두 출력하기)

1<=m<=n<=1,000,000   시간제한 2초

 

이것도 함수로 짰는데 시간초과 나옴:

m,n=map(int,input().split())

def prime(i):
  if i==1:
    return False
  elif i==2:
    return True
  else: # 자연수만 입력된다는 전제 하에.
    for j in range(2,i):
      if i%j==0:
        return False
        break
    return True

for i in range(m,n+1):
  if prime(i):
    print(i)

개짜증!!!

 

 

결국 책을 펼쳐봤는데

문제는 for문으로 주어진 숫자 직전까지 하나하나 나눠보는 건 알고리즘상 매우매우 비효율적이었던 것.

방법은??? 주어진 숫자 직전까지가 아닌, 주어진 숫자의 "제곱근"까지만 반복문을 돌려도 누락 없이 따져볼 수 있다.

 

m,n=map(int,input().split())
import math

def prime(i):
    for j in range(2,round(math.sqrt(i)+1)):
      if i%j==0:
        return False
        break
    return True

for i in range(m,n+1):
  if i==2:
    print(i)
  elif i==1:
    continue
  elif prime(i):
    print(i)

이렇게 하면 시간 제한 안에는 들어오지만, 

더 짧게 하는 방법도 소개되어있었다.. "에라토스테네스의 체" 알고리즘

이건... 내일... 추가하도록 하겠다....