[JUNGOL_2813 - JAVA] 소수의 개수

문제

소수(prime number)란 1보다 큰 자연수 중 1과 자기 자신 두 개만을 약수로 갖는 수를 말한다.
자연수 M과 N을 입력받아 M부터 N까지 소수의 개수를 구하여 출력하는 프로그램을 작성하시오.

 

입력형식

자연수 M과 N이 공백으로 구분되어 주어진다. (1 ≤ M ≤ N ≤ 2,000,000)

 

출력형식

M이상 N이하의 자연수 중 소수가 몇 개인지 구하여 출력한다.

 

에라토네스의 체를 이해한다면 만들기 어렵지 않을 것이라 판단된다.
간단한 설명을 하자면,
1을 먼제 제외한 후, 2의 모든 배수 제거, 3의 모든 배수 제거, 5의 모든 배수 제거이다.
4는 2의 배수 제거에서 사려졌기 때문에 3다음5의 배수 제거이다.
위의 방법을 범위 끝의 제곱근 까지 이하까지 하면 남은 값은 소수이다.
(ex 범위가 30일때, 7의 제곱은 49로 30을 초과함으로 7까지 반복 후 남은 수들은 소수이다.)
(제곱이 기준인 이유는 n*m 인경우 둘 중 한 수는 제곱근보다 작기때문에 작은수에서 m이 걸러진다.)

이렇게 소수가 아닌 수에 1을 넣은 후 배열 값이 0인 값들을 찾으면 개수가 나온다.
주의할 점은 배열의 초기값은 0 이므로, 사용한 배열의 범위만큼 출력을 해야한다.

import java.util.Scanner;

public class Main {

	static int prime[] = new int[2000005];	// 소수를 담는 배열
	static Scanner sc = new Scanner(System.in);

	// 에라토스테네스의 체
	// 소수 = '0' 소수가 아닌수 = '1' 으로 정리
	static void eratos(int n) {
		prime[1] = 1; // 반복문 범위 밖의 '1'을 제외하기 위함.
		for (int i = 2; i * i <= n; i++) {	// 입력받는 n의 제곱근 이하까지 반복
			if (prime[i] == 0) {	// int형 배열의 초기값은 '0'
				for (int j = i * i; j <= n; j += i) // i의 제곱부터 n까지 i씩 증가 ex) 2의배수 2,4,6,8,...
				{									
					prime[j] = 1; // i의 배수일 때, '1' 대입
				}
			}
		}
	}

	public static void main(String[] args) {

		int cnt = 0;
		int s = sc.nextInt();
		int e = sc.nextInt();

		eratos(e);

		for (int i = s; i <= e; i++) { //입력받은 범위만큼 반복
			if (prime[i] == 0)		// 배열값이 '0'일때 소수이므로, 카운트
				cnt++;
			
		}
		System.out.println(cnt);
	}

}

 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2079&sca=2040

JUNGOL | 소수의 개수 > 문제은행