백준 1978 문제 풀이 python

🐒 문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

• 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

• 주어진 수들 중 소수의 개수를 출력한다.

입력 예시

4
1 3 5 7

출력 예시

3

✍ 나의 풀이

import sys

n = int(input())
result = n

a = list(map(int,sys.stdin.readline().split()))
for i in a:
    count = 3

    if i == 2:
        continue
    elif i == 1 or i%2 == 0:
        result -= 1
    else:
        while count < i :
            if i%count == 0:
                result -= 1
                break
            count += 2
            
print(result)

일단 아이디어는

• 소수는 1과 자신만을 약수로 가지는 수
  • 1과 자신이외에 나눠서 떨어지는 수를 찾아서 제외하기
  • 짝수는 소수일 수 없음
  • 그렇다고 모든 홀수가 소수인 것은 아님

그래서 입력받은 수를 1부터 n까지 홀수로 나누어서 떨어지는 숫자를 찾았다.
굳이 홀수로 나눈 이유는 짝수를 포함하면 계산시간이 2배로 걸리기 때문이다.

이를 토대로 코드를 작성하였다.

몇번 빠꾸먹으면서 알게됐는데 1은 소수가 아니다.
2는 약수를 1과 자기자신만을 가지므로 소수였다.

다시 코드를 수정했다.

import sys

n = int(input())
count = 3		# 변수 초기화 필요
result = n

a = list(map(int,sys.stdin.readline().split()))
for i in a:
    if i == 1 or i%2 ==0:
        result -= 1
    elif i == 2: 	#위 if문이 2를 거름
        continue
    else:
        while count < i :
            if i%count == 0:
                result -= 1
                break
            count += 2

print(result)

여기서 문제는 count를 검사할 숫자가 바뀔때마다 3으로 초기화가 되어야하는데 위코드 처럼하면 계속 3을 더해서 의도하지 않은 결과를 출력한다.

또한 for문의 첫번째 if문에서 i가 2일때 i%2 == 0이 True이므로 소수가 아니게 처리된다.

따라서 위 사항들을 수정했다.

import sys

n = int(input())
result = n		# 전체 갯수에서 검사한 숫자가 소수가 아니면 1씩 빼기위함

a = list(map(int,sys.stdin.readline().split()))
for i in a:
    count = 3

    if i == 2:
        continue # 검사할 숫자가 2면 소수이므로 넘어감
    elif i == 1 or i%2 == 0:
        result -= 1		#1 또는 짝수는 소수가 아니므로 전체 갯수에서 1을 뺌
    else:
        while count < i :
            if i%count == 0:	#검사할 숫자를 count로 나누어 떨어지면 소수가 아니므로 결과에서 1을 뺀다
                result -= 1
                break	#while문 탈출
            count += 2	# 3부터 2씩 증가시킴
            
print(result)

사실 입력이 반복문 안에서 일어나는게 아니라서 readline()을 쓸 필요는 없을 것 같다.

다른 답안

n = int(input())

num = list(map(int,input().split()))

result = n
for i in num:
    if i == 1:	#1은 소수가 아님
        result -= 1
        continue
    for j in range(2,int(i**0.5)+1):	#약수 대칭 형태 이므로 절반만 알아도됌
        if i%j == 0:	# 나누어 떨어지는 약수가 있다면
            result -= 1
            break

print(result)

https://freedeveloper.tistory.com/391?category=888096