[Java] 메소드 실습 - 100이하 소수 찾기

소수

- 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수.

이를테면, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,… 등은 모두 소수이다. 4=(22), 6=(2×3), 16=(24)… 등, 소수가 아닌 자연수를 합성수(合成數)라 하며, 1은 소수도 아니고 합성수도 아니다. 자연수 n이 소수인지 아닌지를 판정하려면, 2≤p≤ √n인 범위에 있는 모든 소수 p로 n을 나누어 보아, 나누어 떨어지지 않으면 소수이고, 나누어 떨어지면 합성수이다. 즉, 소수는 양의 약수로 1과 자신만을 가진 자연수이며 합성수는 양의 약수가 1과 자기자신을 포함하여 3개 이상인 자연수이다.

정수의 열 2, 3, 4, 5,…로부터 소수를 찾아내는 방법으로 그리스 시대부터 알려진 에라토스테네스의 체(sieve of Erathosthenes)라는 것이 있는데, 이 방법도 실은 위와 같은 원리에 따른 것이다. 또 메르센의 소수(Mersenne number)도 소수의 유력한 판정법을 제공해 준다. 무한히 많은 소수가 존재한다는 것은 그리스 시대부터 알려진 사실이며, 유클리드의 《기하학원본》 중에도 그 설명으로 정해진다. 이 정리를 초등정수론의 기본정리라고 한다.

[네이버 지식백과] 소수 [prime number, 素數] (두산백과)

.

.

소수 구하는 방법

 - 자신보다 작은(2보다 큰) 수들로 나눴을 때 나누어 떨어지는지 확인한다.

 - 나누어 떨어진다면 소수가 아니고, 아닐 경우 소수라고 판정한다.

.

.

예제 코드

class PrimeNumber 
{
	public static void main(String[] args) 
	{
		/*
		1~100 사이의 정수 중 소수를 구하여 출력
		소수인지 검사하여 소수여부를 리턴하는 메소드를 제작
		*/
		for (int i = 2 ; i <= 100 ; i++ )
		{
			if (isPrime(i))
			{
				System.out.println(i);
			}
		}
	}

	public static boolean isPrime(int n){
		// 매개변수로 받은 n이 소수인지 여부를 검사하여 리턴하는 메소드
		int q;
		boolean chk = true;
		for (int i = 2; i < n ; i++ )
		{
			q = n % i;

			if (q == 0)
			{
				chk = false; // 나누어 떨어질 경우 소수가 아님.
				break;
			} else {
				chk = true; // 모든 수로 나누었을 때 나누어 떨어지지 않는다면 소수.
			}
		}
		return chk;
	}
}