본문 바로가기

소수2

[백준] 1929번: 소수 구하기 Hint 1. 1부터 n까지의 숫자가 소수인지 아닌지 확인을 하고, 소수이면 그 숫자의 배수들은 소수일까요? 2. 소수의 배수들은 소수가 아닌게 확실하기 때문에 미리 제거해주면 나중에 소수인지 확인할 필요가 없다! 3. 에라토스테네스의 체 이용하기 (그게 뭐지?) 백준 1929번: 소수 구하기 (풀어보기) import sys M, N = map(int, sys.stdin.readline().split()) # N까지의 숫자의 소수인지 아닌지에 대한 여부를 판단하는 배열 만들기 # 이것이 에레스토스테네스의 체! is_prime = [True] * (N+1) is_prime[0], is_prime[1] = False, False # 2부터 N까지의 숫자의 배수는 모두 소수가 아니라고 False로 바꿔주기 f.. 2023. 2. 18.
에라토스테네스의 체 Goal 1. 소수 정의하기 2. 소수 찾는 알고리즘 - "에라토스테네스의 체" 이해하기 소수란? 소수란 숫자 중 나 자신과 1로만 나눠지는 수다. 즉, 그 2개의 수 이외의 다른 수로 나눠진다면 소수가 아닌 "합성수" 라고 말할 수 있다! 예시) 소수 : 2, 3, 5, 7, 11, 13, 17, 19, ... 그 외 : 4 (2로 나눠지니까), 6 (2와 3으로 나눠지니까), 8 (2로 나눠지니까), 9 (3으로 나눠지니까), ... "에라토스테네스의 체"는 언제 필요한가? N이라는 숫자가 소수인지 아닌지 판단하기 위해서는 2부터 N/2 까지의 숫자로 나눠봐야 알 수 있다 하지만 2부터 100까지의 숫자 중에서 소수를 출력하라고 한다면 이중 for문을 돌려야하고 시간 복잡도는 O(n^2)으로 느리다 .. 2023. 2. 13.

티스토리툴바