Seongkyun Han's blog
190205 백준 알고리즘 문제풀기
05 Feb 2019 | baekjoon[1978] 소수찾기
문제
-
N개의 정수가 입력되고, 입력된 수 중 소수가 몇개인지 출력하는 프로그램 작성
- 소수는 1보다 큰 자연수이므로 그 이하의 수는 소수가 아니다
- 약수가 없는 수가 소수이므로 2부터 자기자신/2 까지만 소수인지 확인하면 된다
- 2부터 자기자신/2까지 판단할 수를 나누며 나머지가 0이된다면 소수가 아님(약수가 존재)
- 아닐경우는 소수로 판단한다.
정답(틀렸습니다!)
def isprimenum(num):
lnum = int(num / 2)
if num <= 1:
return 0
for j in range(2, lnum):
if num%j == 0:
return 0
return 1
a = int(input())
nums = list(map(int, input().split()))
result = 0
for num in nums:
result += isprimenum(num)
print(result)
- 위 코드에서 도저히 뭐가 틀렸는지 알 수 없어서 질문글을 올렸다..
- 해결했다.
isprimenum함수에서 입력이 4가 될 경우, 2로 나뉘어진 끝 숫자lnum이 2가 되므로 함수 내 for문이 돌지 못해(for j in range (2,2)) 1을 return하는것이 문제였다. 따라서 if문에 num이 4일 경우에 대한 처리를 추가하여 해결하였다.
def isprimenum(num):
lnum = int(num / 2)
if num <= 1 or num == 4:
return 0
for j in range(2, lnum):
if num%j == 0:
return 0
return 1
a = int(input())
nums = list(map(int, input().split()))
result = 0
for num in nums:
result += isprimenum(num)
print(result)
- 문제를 급하게 풀려다보니 쉬운 반례였지만 찾지 못하여 질문글까지 올렸다..
다른 정답(맞았습니다!)
import sys
N = int(input())
num = sys.stdin.readline().split()
result = 0
for i in num:
c = 0
for j in range(1, int(i)+1):
if int(i)%j == 0:
c += 1
if c == 2:
result += 1
print(result)
