소수 판별 2

Python 파이썬 - 소수 판별 알고리즘 (에라토스테네스의 체)

가끔 알고리즘 문제에 나오는 소수계산을 위해 정리하는 글이다.소수란, 1과 자기 자신 이외에 약수를 가지지 않는 1보다 큰 자연수 이다. 1은 소수가 아니다 소수 판별 알고리즘은 대표적으로 두가지 방법으로 구현 할 수 있다. 일반적인 방법 우선, 반복문을 사용하는 것이다. 이 방법은 1개의 숫자가 소수인지 아닌지 판별하는데 사용하면 좋다. 여러 숫자를 소수 판별해야하는 경우는 아래 있는 에라토스테네스의 체가 더 유용하다. n이라는 숫자가 소수인지 확인하기 위해서는 2부터 n-1까지 나눠보면서 나머지가 0이 나오는 숫자가 한개도 없으면 n은 소수이다. 하지만 n-1까지 나눠보지 않더고 √n 까지만 확인해봐도 된다. 소스코드 import sys, math # 소수 판별 알고리즘 : 제곱근까지 구하기 def ..

[BOJ 백준] 1747번 : 소수&팰린드롬(Python, 파이썬)

www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 소수 판별과 팰린드롬을 사용하는 문제이다. 파이썬의 경우 팰린드롬은 굉장히 쉽게 판별할 수 있으므로 패스한다. 소수 판별은 에라토스테네스의 체 2부터 제곱근까지 나머지 확인 2가지 방식으로 테스트를 해봤는데, 시간복잡도는 크게 차이나지 않는 것 같다. 다만, 소수의 갯수보다 팰린드롬의 갯수가 더 많으므로 팰린드롬인지 확인해주는 것을 먼저 해주는게 시간복잡도 측면에서 효율적이..