글 읽기 - [java] 왜틀렸는지 잘 모르겠네요 ...

asp4303 3년 전 0

최대한 에라토스테네스의 체에 맞춰서 만들었는데 이클립스에서는 잘 돌아가는 코드가

왜 틀리는지 잘 모르겠네요...

읽어보시라는 내용들도 다 읽어봤지만 제가 이해를 못하는건지 싶네요

도와주시면 감사하겠습니다!

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// 에라토스테네스의 체
		// m^2>=n일때까지 반복
		Scanner s = new Scanner(System.in);
		int m = s.nextInt();
		int n = s.nextInt();
		s.close();
		Boolean[] arr = new Boolean[n + 1];
		Arrays.fill(arr, true);
		arr[0] = false;
		arr[1] = false;
		for(int i=2;i<m;i++) {
			arr[i]=false;
		}
		for (int i = 2; i<=n/i; i++) {
			for (int j = 1; i * j <= n; j++) {
				if (arr[i * j] == true) {
					switch (i * j) {
					case 2:
					case 3:
					case 5:
					case 7:
						continue;
					}
					arr[i * j] = false;
				}

			}
		}

		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == true) {
				System.out.println(i);
			}
		}
	}

}

jsh4646 3년 전 1

1 173 입력해보시면

11이랑 13이 누락됩니다.

jsh4646 3년 전 1

15~19번 줄에서 m보다 작은 범위에 전부 false를 입력해두시는데

출력for문 초기화 부분에서 i를 m으로 초기화하는 방법을 쓰시면 필요없을 것 같아요.

에라토스테네스의 체에 대해 조금 오해가 있으신 것 같은데

아마 최대값이 120인 예시를 통해 보셨기 때문에 이해하는 데에 어려움이 있었을 거라 예상됩니다.

예시에서 2,3,5,7의 배수만 검사한 것은 120의 제곱근이 10.xxxx이며 이보다 작은 숫자 중 소수가 2,3,5,7 뿐이라서 그렇습니다.

최대값 n의 제곱근보다 작은 모든 소수에 대해 검사를 시행하셔야 합니다.

예를들어 1 ~ 150 범위에서 소수를 찾아내는 경우에는

150의 제곱근인 12.xxxx보다 작은 소수인 2,3,5,7,11의 배수를 제거하시면 되겠죠?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[java] 왜틀렸는지 잘 모르겠네요 ...

asp4303 3년 전 0

jsh4646 3년 전 1

jsh4646 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말