0과 1의 쉼터

목차소수(Prime Number)란?소수 판별법(Prime Number Checking)에라토스테네스의 채 (Sieve of Eratosthenes)✏️ 연습 문제소수(Prime Number)란?1과 자기 자신 이외의 약수를 갖지 않는 2이상의 자연수 ex) 2. 3. 5. 7. 11. 13, ….⚠️1은 소수가 아닙니다.소수 판별법(Prime Number Checking)주어진 수가 소수인지 어떻게 알 수 있을까요?1. 전부 나누어 보기2부터 N - 1로 나누어 떨어지는지 확인하는 방법입니다.시간 복잡도는 O(N)입니다.def is_prime(n): # 1은 소수가 아니므로 제외 if n 2. 홀수로 나누어보기수의 절반은 짝수입니다.2를 제외한 모든 짝수는 소수가 아니므로 홀수로만 나누어 봅..

문제 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. 입력 첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. 출력 첫째 줄에 총 몇 개가 있는지 출력한다. 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 풀이 A와 B사이의 수 중 소수의 N제곱에 해당하는 "거의 소수"의 갯수를 구하는 문제다. 거의 소수는 최소 p^2이므로, A와 B에 대해 2 ~ sqr..