본문 바로가기
728x90

소수판별2

[BOJ/Python] 4948. 베르트랑 공준 📌 문제 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 📌 문제 접근 방법 is_prime이라는 배열을 만들고, 2부터 n의 제곱근까지를 탐색하며 소수의 배수를 모두 False로 바꿔준다. n부터 2n까지 반복하여 해당 숫자가 소수라면 cnt를 1 더해준다. n에 0이 입력되면 반복문을 종료한다. 📌 코드 # 백준 4948 베르트랑 공준 import sys input = sys.stdin.readline def is_prime_numb.. 2021. 10. 21.
[BOJ/Python] 2960. 에라토스테네스의 체 📌 문제 https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 📌 문제 접근 방법 2부터 N까지의 숫자 리스트를 생성한다. 가장 작은 수가 소수라면 그 수의 배수를 모두 리스트에서 제거한다. (나중에 생각하고 알게 된 점이지만, 어차피 가장 작은 수는 항상 소수이므로 소수판별을 생략해도 된다.) 📌 코드 def is_prime(number): for i in range(2, number): if not number%i: return False else: return True N, K = map(int, input().split()) nu.. 2021. 10. 4.
728x90

티스토리툴바