본문 바로가기

에라토스테네스의 체5

[백준] 2960번 : 에라토스테네스의 체 – JAVA [자바] https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 문제 문제 풀이 백준 2960번 에라토스테네스의 체는 실버 4 난이도의 수학, 구현 및 에라토스테네스의 체 문제이다. 이 문제에서는 정수 N과 K가 주어진다. 2부터 N까지 에라토스테네스의 체 알고리즘을 적용시킨다고 할 때 K번째로 지우는 수를 출력하면 된다. 참고로 원래 에라토스테네스의 체 알고리즘에서는 숫자의 배수만 지운다. 즉, 예를 들어서 2의 배수를 지울 때 2는 원래는 안 지우는데 이 문제에서는 2도 같이 지워야 한다. 만약에 에라토스테네스의 체에 대해서 잘 모른다면 밑에 .. 2022. 7. 16.
[백준] 15965번 : K번째 소수 – JAVA [자바] https://www.acmicpc.net/problem/15965 15965번: K번째 소수 자연수 K가 주어진다.(1 ≤ K ≤ 500,000) www.acmicpc.net 문제 문제 풀이 백준 15965번 K번째 소수는 실버 2 난이도의 수학 및 에라토스테네스의 체 문제이다. 이 문제는 추가로 부산일과학고 BSIS배 Code Festival에서 D번 문제로 출제된 문제이기도 하다. 이 문제 자체는 간단하다. 문제에서 입력으로 자연수 K가 주어지는데 K번째 소수를 출력하기만 하면 된다. 이 문제는 에라토스테네스의 체를 이용해서 풀 수 있다. 아직 에라토스테네스의 체에 대해서 잘 모르면 밑에 있는 링크를 참고하면 되겠다. https://propercoding.tistory.com/182 [알고리즘] 에.. 2022. 7. 15.
[백준] 1978번 : 소수 찾기 – JAVA [자바] https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 문제 풀이 백준 1978번 소수 찾기는 실버 5 난이도의 수학 및 에라토스테네스의 체 문제이다. 이 문제에서는 입력으로 N개의 자연수가 주어지고 이 N개 자연수들 중에서 소수가 몇 개인지를 출력하면 된다. 이 문제는 에라토스테네스의 체를 이용하면 쉽게 풀 수 있다. 에라토스테네스의 체를 잘 모르면 밑에 있는 링크를 참고하면 되겠다. https://propercoding.tistory.com/182 [알고리즘] 에라토스테네스의 체 (Sieve of Eratost.. 2022. 7. 15.
[백준] 1929번 : 소수 구하기 – JAVA [자바] https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 문제 풀이 백준 1929번 소수 구하기는 실버 3 난이도의 수학 및 에라토스테네스의 체 문제이다. 이 문제에서는 입력으로 자연수 M과 N이 주어진다. 그리고 M 이상 N 이하의 소수들을 모두 출력해주면 되는 문제이다. 이 문제에서는 에라토스테네스의 체 알고리즘을 이용해서 풀 것이다. 에라토스테네스의 체를 잘 모르면 밑에 있는 글을 참고하면 되겠다. https://propercoding.tistory.com/182 [알고리즘.. 2022. 7. 15.
반응형

티스토리툴바