사용자 도구

사이트 도구


ps:problems:boj:1978

소수 찾기

ps
링크acmicpc.net/…
출처BOJ
문제 번호1978
문제명소수 찾기
레벨실버 4
분류

정수론

시간복잡도O(n*sqrt(m))
인풋사이즈n<=100, m<=1000
사용한 언어Python
제출기록32952KB / 68ms
최고기록52ms
해결날짜2022/06/02

풀이

  • 주어진 수 각각에 대해서 소수 여부를 확인하는 문제
  • 여러개의 수에 대해서 소수 판별을 할 경우에는 - 각각의 수에 trial division을 적용해서 각각 소수여부를 각각 확인하는 방법과, 소수 목록을 전처리해서 만들어두고 각각의 수가 그 안에 포함되는지를 확인하는 방법이 있다.
  • 이 문제에서는 전자가 좀더 빠르게 동작한다.

코드

"""Solution code for "BOJ 1978. 소수 찾기".

- Problem link: https://www.acmicpc.net/problem/1978
- Solution link: http://www.teferi.net/ps/problems/boj/1978

Tags: [Number theory]
"""

import math


def is_prime_small(n):
    return n > 1 and all(n % i for i in range(2, math.isqrt(n) + 1))


def main():
    N = int(input())  # pylint: disable=unused-variable
    nums = [int(x) for x in input().split()]
    answer = sum(1 for x in nums if is_prime_small(x))
    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
M L J O P
 
ps/problems/boj/1978.txt · 마지막으로 수정됨: 2022/06/02 08:46 저자 teferi