- Today
- Yesterday
- Total
메이쁘
(JAVA) 백준 2960번 : 에라토스체네스의 체 본문
https://www.acmicpc.net/problem/2960
2960번: 에라토스테네스의 체
문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에
www.acmicpc.net
에라토스테네스의 체는 유명한 알고리즘으로
일정 숫자까지(N) 숫자들 중 소수를 찾아내는 알고리즘이다.
이 문제는 난이도가 상당히 쉬우며
이를 응용한 문제는
https://maivve.tistory.com/46?category=844319
(JAVA) 백준 1016번 : 제곱ㄴㄴ수
https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,..
maivve.tistory.com
'제곱ㄴㄴ수' 문제가 있다.
현재 이 게시글의 문제를 해결한 다음
저 문제를 풀어보는 것을 추천한다!
매커니즘 제목을 달 필요도 읍다..!
1) N의 크기만큼 boolean 배열 생성
2) 2부터 N까지(N 포함) 1차 for문 진행
3) 1차 for문으로 나온 값의 배수들을 하나씩 제거. 이미 제거(boolean false)된 상태면 continue.
4) count와 k의 값이 같으면 그 때의 숫자 출력
감사합니다.
소스코드
'Algorithm > Baekjoon' 카테고리의 다른 글
| (JAVA) 백준 2589번 : 보물섬 (0) | 2020.04.04 |
|---|---|
| (JAVA) 백준 11057번 : 오르막 수 (0) | 2020.04.03 |
| (JAVA) 백준 10872번 : 팩토리얼 (0) | 2020.04.02 |
| (JAVA) 백준 3967번 : 매직 스타 (0) | 2020.04.02 |
| (JAVA) 백준 2661번 : 좋은수열 (0) | 2020.04.01 |
