Prime Number(소수) 구하기 java

소수 구하기(Prime Number) JAVA

1. 소수란 무엇인가?

출처: http://www.mathsisfun.com/definitions/prime-number.html

한글 설명은 다음과 같다.

출처: http://terms.naver.com/entry.nhn?docId=1113970&cid=40942&categoryId=32206

그렇다. 소수는 말 그대로 1과 자기자신을 제외한 숫자로 나누어 떨어지지만 않으면 그 숫자는 소수인 것입니다. 그래서 코딩으로 어떻게 할까 생각한 끝에 2부터 자기 자신의 숫자까지 나누어서 나머지가 0인 경우를 count 하는 방법입니다. 만약에 소수인 5라면 2,3,4,5로 나눕니다. 그러면 2,3,4,5 중에 5만 나누어 떨어지기 때문에 count는 1인 것입니다. count가 1인 경우를 소수인 것입니다.(1과 자기자신의 수까지 2개인데 1부터 시작을 하지 않았으므로 갯수는 하나 밖에 없다.) 만약 소수가 아닌 6을 예를 들어보면 2,3,4,5,6으로 차례대로 나누어봅니다. 2,3,6으로 count가 3이 되었습니다. 그러므로 소수가 아닙니다. 좀 더 효율적으로 하기 위해서 count가 1을 넘어가면 그 반복문은 break문을 이용해서 멈추도록 했습니다. 밑에 보시면 자바 소스입니다. 

package Interface;
 
public class Main {
    public static void main(String[] args) {
        int[] primeNum = new int[100];
        int index = 0;
        for (int i = 2; i <= 100; i++) {
            int count = 0;
            for (int j = 2; j <= i; j++) {
                if (i % j == 0) {
                    count++;
                }
                if (count > 1) {
                    break;
                }
            }
            if (count == 1) {
                primeNum[index++] = i;
            }
        }
 
        for (int a = 0; a < primeNum.length; a++) {
            System.out.print(primeNum[a] + " ");
        }
 
    }
}
 
 

다음 포스터에서는 제 방법 말고 더 좋은 알고리즘으로 구현한 소수구하기를 포스팅하겠습니다.