[수학] [BJ1978] 소수 찾기

코드 플러스

🚩 문제 설명

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

BJ1978

 

⏱️ 시간 복잡도
▪

◾ 소수를 찾아서 개수를 구해 출력하는 문제 이다.

◾ 소수 (Prime Number)

• 약수가 1과 자기 자신밖에 없는 수
• N이 소수가 되려면, 2 <= x <= N - 1인 x로 나누어 떨어지면 안된다.
• 1부터 100까지의 소수

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

◾ 소수 관련 알고리즘

1. 소수 확인: 어떤 N이 소수인지 아닌지 판별하기
2. 소수 찾기: N보다 작거나 같은 모든 자연수 중에서 소수 찾기

◾ 소수 확인 알고리즘

• N이 소수가 되려면 2 <= x <= N 인 x로 나누어 떨어지면 안된다.

def isPrime(n):
    if n < 2:
        return False

    for i in range(2, n):
        if n % i == 0:
            return False

    return True

• N이 소수가 되려면 2 <= x <= N/2 인 x로 나누어 떨어지면 안된다.
• N의 약수 중에서 가장 큰것은 N/2 보다 작거나 같기 때문이다.

def isPrime(n):
    if n < 2:
        return False

    for i in range(2, n//2):
        if n % i == 0:
            return False

    return True

• N이 소수가 되려면 2 <= x <= 루트 N 인 x로 나누어 떨어지면 안된다.
• N이 소수가 아니라면, N = a x b 로 나타낼 수 있다. ( a <= b )
• 두 수 a와 b의 차이가 가장 작은 경우는 루트 N이다.

def isPrime(n):
    if n < 2:
        return False

    for i in range(2, abs(n)):
        if n % i == 0:
            return False

    return True

 

 

 

---

 

 

 

✅ 입출력

1) 주어지는 수의 갯수 N
2) N개의 자연수가 주어진다.
return ➡️ 주어지는 자연수들 중에서 소수의 개수를 구한다.

✔️ 예제 1

4
1 3 5 7

3

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys

N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))


def isPrime(n):
    if n < 2:
        return False

    for i in range(2, abs(n)):
        if n % i == 0:
            return False

    return True


ans = 0
for n in nums:
    if isPrime(n):
        ans += 1

print(ans)

💬 Point

➡️  for i=2 to abs(N)
➡️  만약 소수라면 카운트를 한다.

◾ 우선 수열의 개수를 나타내는 N을 입력받는다.

◾ list(map(int, sys.stdin.readline().split())) 를 통해서 공백을 기준으로 나열된 숫자들을 배열로 입력받는다.

◾ 해당 배열을 돌면서 소수인지 아닌지 확인한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 코드플러스 소수 찾기 python 파이썬

# 백준 1978 소수찾기 python 파이썬

---