[JAVA] 알고리즘 소수 판별

어제 포스트한 소인수분해에서 나온 소수란 무엇일까.

 

소수란 저번 글에서도 설명했지만 약수로 1과 자기자신만을 가지는 수를 의미한다.

 

많이 알려진 소수로는 2, 3, 5, 7, 11, 13, 17 등이 있다.

위와같이 몇몇가지 경우는 외워서 판별할 수는 있지만 큰 수가 소수인지 판별하기는 어렵다.

 

이러한 상황에서 쓸 수 있게 소수를 판별하는 알고리즘을 짜보자.

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int num = sc.nextInt();

		if (isPrime(num)) {
			System.out.println("Input number " + num + " is prime number");
		} else {
			System.out.println("Input number" + num + " isn't prime number");
		}

	}

	static boolean isPrime(int num) {

		boolean bool = false;

		for (int i = 2; i < num; i++) {

			if (num % i == 0) {
				bool = false;
				break;
			} else {
				bool = true;
				break;
			}

		}

		return bool;
		
	}

}

코드를 보면 판별하고 싶은 수를 Scanner로 입력받아 num에 저장한다.

if문을 통해 입력받은 수가 소수인지 아닌지를 판별하게 된다.

 

조건문에서 호출된 isPrime()함수를 보게되면 수를 매개변수로 전달 받아 수를 판별한다.

for문으로 2부터 1씩 증가시키며 num을 나누게되는데 이는 소수의 성질인 약수가 1과 자기자신밖에 없다는 것을 이용하는 부분이다.

 

반복문 내의 if문을 통해 num이 i로 나눠떨어지면 소수가 아니기 때문에 false를 return하고 나누어 떨어지지 않으면 소수이기 때문에 true를 return한다.