반응형
- 해당하는 모든 소수를 출력하라.
소수란 1과 자기 자신만을 약수로 가지는 수이다. 100이하의 자연수 중 모든 소수를 출력하시오.
소수를 오름차순으로 출력한다. 각 출력값 사이는 공백으로 구분하고 출력값 5개 마다 줄바꿈을 한다.
아래와 같은 결과 값이 출력되어야 한다.
2 3 5 7 11
13 17 19 23 29
31 37 41 43 47
53 59 61 67 71
73 79 83 89 97
위 내용까지 트라이캐치의 소수 찾기 문제이며, 아래코드는 오름차순과 출력값 사이를 공백으로 구분하고, 5개마다 줄바꿈을 적용하지 않은 소스이다.
해당 코드는 범용성을 위해 자바스크립트를 이용하여 만들었으며, 에라토스테네스의 체를 이용한 방법이다.
function getPrimesUpTo(n) {
if (n < 2) return [];
// true는 소수로 간주되는 초기 상태
const isPrime = new Array(n + 1).fill(true);
isPrime[0] = false;
isPrime[1] = false;
for (let i = 2; i * i <= n; i++) {
if (isPrime[i]) {
// i의 배수들을 모두 false 처리
for (let j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
// 인덱스가 true인 숫자만 필터링하여 소수 목록 생성
const primes = [];
for (let i = 2; i <= n; i++) {
if (isPrime[i]) primes.push(i);
}
return primes;
}
// 예시 사용
console.log(getPrimesUpTo(100)); // 100 이하의 모든 소수 출력
아래는 재귀 함수를 이용하여 좀더 간략하게 구성
function sieve(arr, primes) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] % primes[0] === 0 && arr[i] !== primes[0]) {
arr.splice(i, 1);
i--; // 중요: 삭제 후 인덱스 조정
}
}
primes.shift();
if (primes.length === 0) arr.shift(); // 1 제거
return primes.length === 0 ? arr : sieve(arr, primes);
}
const numbers = Array.from({ length: 100 }, (_, i) => i + 1);
const primesToUse = [2, 3, 5, 7]; // 100 이하라면 sqrt(100) 이하 소수만 필요
console.log(sieve(numbers, [...primesToUse]));
에라토스테네스의 체에 대한 부연설명
고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.
아래 움직이는 이미지를 통해 쉽게 알고리즘을 눈으로 확인하자.
반응형
'Programing > Algorithm' 카테고리의 다른 글
jvascript array 경우의 수 구하기 (permute) (0) | 2022.02.15 |
---|---|
LRU Cache (Least Recently Used) / 프로그래머스 캐시 (0) | 2022.01.19 |
콜라츠 추측 (0) | 2021.08.27 |
하샤드의 수 (Harshad Number) (0) | 2021.08.25 |
덧셈 뺄셈 동적 계산 (dynamic plus minus, Dynamic addition and subtraction) (0) | 2019.07.19 |
주민등록번호 체계 및 유효성 검사 (javascript) (2) | 2016.10.07 |
퀵 정렬(Quick Sort) (javascript) (0) | 2016.05.31 |
재귀 함수를 이용한 거듭제곱 (a의 n승) (javascript) (0) | 2016.05.18 |