[알고리즘] 소수 나열하기

마데슾 : My Dev Space·2021년 6월 17일
0

알고리즘

목록 보기
7/9

문제

정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오.
소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.

# 20이 입력된다면, 아래와 같이 반환해야 합니다!
[2, 3, 5, 7, 11, 13, 17, 19]

이해

소수의 특징

  • 소수는 자기 자신과 1 외에는 아무것도 나눌 수 없다
  • 주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문입니다.
  • 따라서 주어진 정수의 제곱근보다 작거나 같은 소수까지만 확인해보면 된다
    - 우리는 1과 자기 자신을 제외한 나머지를 순회하는 반복문에서 나누어 떨어지는 숫자가 나온다면 주어진 정수는 소수가 아니라고 판단한다. 그래서 나누어 떨어지는 숫자를 제외한 나머지만 보기위해 소수는 자신의 제곱근보다 작거나 같은 어떤 소수로도 나눠지지 않는다 라는 소수의 특징을 사용하는 것이다
    - 정수 29가 소수인지 알아볼때 소수 리스트에 [2, 3, 5, 7, 11, 13, 17, 19] ]가 있다고 가정했을때 제곱근 보다 작거나 같은 소수만 탐색하는 방법을 사용하면 [2,3,5]만 탐색하면 된다

계획

  1. 소수를 담을 공간(배열)을 만든다
  2. 숫자 2부터 주어진 정수까지 순회한다
  3. 그 안에서 소수 배열을 필터링한다
    • 조건 : 탐색중인 소수의 제곱근보다 작거나 같은 소수
  4. 정수를 필터링된 소수 배열의 각 요소로 나누었을때 단 하나라도 나누어 떨어진다면 소수가 아니다
  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)
profile
👩🏻‍💻 🚀

0개의 댓글