[백준 1016] 파이썬(Python) 제곱ㄴㄴ수 - 에라토스테네스의 체
제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다. 입력 첫째 줄에 두 정수 min과 max가 주어진다. 출력 첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다. 제한 1 ≤ min ≤ 1,000,000,000,000 min ≤ max ≤ min + 1,000,000 예제 입력 1 1 10 예제 출력 1 7 에라토스테네스의 체 알고리즘 에라토스테네스의 체는 소수를 찾는 방법 중 하나입니다. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다. 2 자신을 제외한 2의 배..
2022. 10. 10.
[파이썬 Python] 에라토스테네스의 체(소수 구하기) 개념과 예제 - (백준 1747)
에라토스테네스의 체 알고리즘 에라토스테네스의 체는 소수를 찾는 방법 중 하나입니다. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다. 2 자신을 제외한 2의 배수를 모두 지웁니다. 남아있는 수 가운데 3은 소수이므로 놔두고, 자신을 제외한 3의 배수를 모두 지웁니다. 남아있는 수 가운데 5는 소수이므로 자기 자신을 제외한 5의 배수를 모두 지웁니다. 남아있는 수 가운데 7은 소수이므로 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남게됩니다. Python 3으로 구현 일단 A 리스트를 인덱스와 수가 같도록 [0,0,2,3,4,5,6,7,8,9 ...] 로 초기화 해줍니다. (0,1은 제외) 2부터 2의 배수들을 차례로 0으로 만들어 줍니다. 이 방식을 ..
2022. 10. 10.
