Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- mongoose
- Nest.js
- Dinosaur
- class
- Bull
- Queue
- typeORM
- nestjs
- 자료구조
- MongoDB
- 공룡게임
- TypeScript
- Sequelize
- 정렬
- 게임
- react
- game
- Python
- Express
- JavaScript
- cookie
- flask
- GIT
- jest
- OCR
- dfs
- AWS
- MySQL
- nodejs
Archives
- Today
- Total
포시코딩
소수 찾기, 소수의 개수 구하기 본문
728x90
처음엔 나도 다른 사람들처럼 for문 두개로 2부터 n까지 모든 수로 나눠보며 소수를 찾는 방법으로 풀이했는데
정확도만 측정하는 테스트에서조차 시간초과나는 테스트케이스가 있었다.
솔직히 이런 소수를 다뤄본적이 많이 없었기 때문에 해당 문제의 질문답변 항목을 보던중에
엄상우 라는 분의
https://school.programmers.co.kr/questions/21359
글에서 정수론 관련하여 소수의 대한 성질을 이용해 연산 과정을 급격하게 줄이는 방법을 알게됨
해당 글의 3번은 앞의 1, 2번에서 다 해결되므로 알고만 있는거로 하고
(소수인지 여부를 묻는데 짝수면 1, 2번의 과정 없이도 바로 판별이 가능하므로)
n은 2이상 1000000이하의 자연수고
n이 소수인지의 여부를 묻는게 아닌 그 사이에 소수가 몇개인지 확인하는 것이기 때문에
for문을 일단 돌긴 해야함
대신 돌면서 체크하는 수들에 대해 1, 2번 방법을 통해 소수 판별을 하기로 하였다.
확인용 소수배열 prime_arr을 만들고
2이상 n이하인 하나씩 증가하는 x에 대해
prime_arr로 돌며 소수인지 판별. 원하는 판독 결과를 얻었을 때는 continue와 break를 이용해
x가 소수면 prime_arr에 넣고 바로 다음 +1된 x로 돌리기
x가 소수가 아닌 확증이 나와도 바로 넘어가게 했다.
해당 문제는 가끔씩이라도 한번씩 봐서 머릿속에 박아야 하는 케이스가 될 것 같다.
(javascript)
let n = 101;
function solution(n){
let prime_arr = [];
a:for(let x=2;x<=n;x++){
if(x == 2){
prime_arr.push(2);
continue a;
}
for(let y=0;y<prime_arr.length;y++){
// console.log('x: ' + x + ', prime_arr[y]: ' + prime_arr[y]);
if(prime_arr[y] > Math.sqrt(x)){
// console.log('break');
break;
}
if(x % prime_arr[y] == 0){
// console.log('continue');
continue a;
}
}
prime_arr.push(x);
}
// console.log('prime_arr: ' + prime_arr);
return prime_arr.length;
}
console.log(solution(n));
(python)
input = 101
def find_prime_list_under_number(number):
prime_arr = []
for a in range(2, number+1):
for i in prime_arr:
if a % i == 0:
break
if i > a**(1/2):
prime_arr.append(a)
break
else:
prime_arr.append(a)
return prime_arr
result = find_prime_list_under_number(input)
print(result)
728x90
'자료구조알고리즘 > 문제풀이' 카테고리의 다른 글
[신찬수] 괄호 맞추기 (0) | 2022.12.16 |
---|---|
[프로그래머스][Lv.0] 영어가 싫어요 (0) | 2022.12.15 |
[프로그래머스][Lv.0] 캐릭터의 좌표 (0) | 2022.12.14 |
곱하기 or 더하기 (0) | 2022.11.29 |
1부터 100까지 소수 구하기 (0) | 2018.07.27 |