백준 JAVA11 1929번 : 소수 구하기

Mention : 에라토스테네스의 채🧺, Math.sqrt (제곱근)을 사용하는 방법이 있지만 다른 방법으로 구현해보았다.

소수 구하기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	214645	60735	42768	26.569%

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

출처

• 데이터를 추가한 사람: jinjean0123, yongjun042

슈도 코드

M(시작 자연수)
N(끝 자연수)
A(N까지의 자연수 배열)

for(N+1만큼) {
	A배열에 자연수 저장
}

소수 구하기 (A배열에서 소수가 아닌 것을 0으로 바꿔준다.)
에라토스테네스의 채 사용
delete 함수 구현
for(A배열의 길이만큼) {
		if (A의 값이 1,4,6,8,9라면 delete 함수 수행, 0으로 바꿔줌)
		else delete 함수 수행
	}
for(A배열의 길이만큼) {
	if(0이 아니라면 그리고 M보다 크거나 같다면)
	출력
}

delete 함수 구현
j = 1;
A = 변수 배열
while(A값이 A배열의 끝자리와 같을때 까지) {
	if(0이나 1이면) break;
	if(배수 인덱스가 A배열의 길이를 초과하면) break;
	A[배수인덱스] 0으로 바꿔준다.
	j++
}

Code

package numberTheory;

import java.util.Scanner;

public class P1929_getPrimeNumber {
	static int j;
	static int[] A;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt();
		int N = sc.nextInt();

		A = new int[N+1];

		for (int i = 1; i < N+1; i++) {
			A[i] += i;
		}

		for (int i = 1; i < A.length; i++) {
			if (A[i] == 1 || A[i] == 4 || A[i] == 6 || A[i] == 8 || A[i] == 9) {
				delete(A, i);
				A[i] = 0;
			} else {
				delete(A, i);
			}
		}

		for (int i = 0; i < A.length; i++) {
			if (A[i] != 0 && A[i] >= M) {
				System.out.println(A[i]);
			}
		}
	}

	private static void delete(int[] arr, int i) {
		j = 1;
		A = arr;
		while (A[i] != A[A.length - 1]) {
			if (A[i] == 0 || A[i] == 1) {
				break;
			}
			if (i + (A[i] * j) >= A.length) {
				break;
			}
			A[i + (A[i] * j)] = 0;
			j++;
		}
	}
}