정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오.
소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.
# 20이 입력된다면, 아래와 같이 반환해야 합니다!
[2, 3, 5, 7, 11, 13, 17, 19]
주어진 정수
는 소수가 아니라고 판단한다. 그래서 나누어 떨어지는 숫자를 제외한 나머지만 보기위해 소수는 자신의 제곱근보다 작거나 같은 어떤 소수로도 나눠지지 않는다
라는 소수의 특징을 사용하는 것이다29
가 소수인지 알아볼때 소수 리스트에 [2, 3, 5, 7, 11, 13, 17, 19] ]
가 있다고 가정했을때 제곱근 보다 작거나 같은 소수만 탐색하는 방법을 사용하면 [2,3,5]
만 탐색하면 된다function findPrimeList(number) {
let primeList = [];
for(let n=2; n<=number; n++) {
// i의 제곱근보다 작거나 같은 요소만 보면 됨
const isPrime = primeList.filter(prime => prime <= Math.sqrt(n))
.every(prime => n % prime !== 0);
if(isPrime) {
primeList.push(n);
}
}
console.log('primeList ? ', primeList);
return primeList;
}
const result = findPrimeList(20);
console.log(result);
input = 29
def find_prime_list_under_number(number):
prime_list = []
for n in range(2, number + 1):
i = 0
while len(prime_list) > i and prime_list[i] * prime_list[i] <= n:
if n % prime_list[i] == 0:
break
i += 1
else:
prime_list.append(n)
return prime_list
result = find_prime_list_under_number(input)
print(result)