목록에라토스테네스 (1)
이야기박스
Quiz) 에라토스테네스의 체 - 소수(Prime Number)를 찾아보자.
Problem Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number. 정수 N이 주어집니다. 이 정수 N보다 작은 모든 소수를 찾으면 됩니다. Example Input : n =10 Output : 2 3 5 7 Input : n = 20 Output: 2 3 5 7 11 13 17 19 Approach 우선 소수에 대하여 다시 짚고 넘어가 보려 합니다. 소수란 자기 자신과 1 이외에는 다른 약수가 없는 수를 의미합니다. 그러면 우리는 어떤 수가 소수인지 아닌지 어떻게 알 수 있을까요? 모든 수에 대해서 한 번씩 나눠보면 될까요? 너무 비효율적인 방법입니다. 우리는 에라토..
Computer & Data/Algorithm
2022. 3. 22. 21:56