[BOJ/Step9] 1978 : 소수 찾기 (Python)

www.acmicpc.net/problem/1978

1978번: 소수 찾기

---

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

4

1 3 5 7

 

예제 출력 1

3

---

풀이

(1) 입력 받은 숫자를 각각 소수 판별

  1. n과 n개의 숫자를 list a에 저장

  2. a를 하나씩 판별

    2-1. a가 1 이면 count--

    2-2. a를 2 ~ a-1 순서대로 나눠서 하나라도 나머지가 0이면 count-- 후에 종료 (소수는 1과 자기 자신으로만 나눠지므로)

  3. count 출력

# 1978-1.py

n = int(input())
a = list(map(int, input().split()))
count = n
for i in a:
    if i == 1:
        count -= 1
        continue
    for j in range(2, i):
        if i % j == 0:
            count -= 1
            break

print(count)

 

(2) 1~1000까지의 수를 미리 소수 판별 후 입력받아 확인

  1. prime 리스트안에 미리 2, 3을 넣어둔다

  2. 4~1000까지의 숫자 i를 소수 판별

    2-1. i를 prime안의 숫자로 나눠 모두 0이 아닐때만 prime 리스트에 값을 추가한다

  3. 입력받은 숫자들이 prime 안에 있는지 하나씩 확인하여 count++

  4. count 출력

# 1978-2.py

n = int(input())
count = 0
prime = [2, 3]

for i in range(4, 1001):
    pp = [i % k for k in prime]
    if all(pp):
        prime.append(i)

for i in list(map(int, input().split())):
    if i in prime:
        count += 1

print(count)