본문 바로가기

정수론

[백준 1456] 거의 소수 (JAVA)

CodingTEST 2023. 8. 13. [백준 1456] 거의 소수 (JAVA) 백준 1456번 문제 - 거의 소수 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 문제 분석 거의 소수 : 소수의 N제곱 A부터 B까지 수 중에 거의 소수의 개수를 출력해라 해결 키 포인트 정수론: 소수구하기 - 에라토스테네스의 체의 원리 1 ≤ A ≤ B ≤ 10^14 int, long 타입보다 큰 수가 시작, 끝 값으로 입력될 수 있다. 어차피 배열 탐색에 필요한 index 는 2 ~ B의 제곱근 → 그러니 long타입으로 설정할 수 있는 값으로 배열의 사이즈는 10^14의 제곱근인 10^7(10000001)로 설..

[백준 1929] 소수 구하기 (JAVA)

CodingTEST 2023. 8. 13. [백준 1929] 소수 구하기 (JAVA) 백준 1929번 문제 - 소수 구하기 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 분석 입력받은 범위의 숫자 중에 소수만 출력 해결 키 포인트 정수론: 소수구하기 - 에라토스테네스의 체의 원리 에라토스테네스의 체의 원리 소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다. ( 1도 소수가 아니다 ) 에라토스테네스의 체 원리 알고리즘 1. 구하고자 하는 소수의 범위만큼 1차원 배열 생성 2. 2부터 시작해 N의 제곱근까지 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다 3. ..

이전 1 다음

티스토리툴바