[실기] 12. 소수 판별


소수 판별


설명


  • 소수(Prime Number)란 1과 자기 자신의 이외의 수로는 나누어떨어지지 않는 1보다 큰 자연수를 가리킨다.
  • 예) 2, 3, 5, 7, 11, 13 …은 소수이다.


문제


  • 1부터 100사이에서 가장 큰 소수를 구하는 알고리즘을 제시하라.
    • 자연수 N이 소수라면, 3부터 N의 제곱근(\sqrt{N})의 정수 중에서 0으로 나누어 떨어지는 수는 없다.(1과 자기 자신 수)
    • N의 제곱근(\sqrt{N})은 시스템 함수 SQRT(N)을 호출한다.

  • 4의 제곱은 4^2 = 16
  • 4의 제곱근은 \sqrt{4} = 2
  • 루트4는 \sqrt{4} = 2


문제공략


  • 일단 가장 큰 소수 P를 2로 잡은 후, 3에서 100까지의 자연수에 대하여 루틴처리
  • N이 제곱근인지 SQRT() 사용
  • SQRT(N)의 값을 MOD()로 나머지가 0인지 i인지 확인(0은 소수가 아님)


C언어

#include<stdio.h>
#include<math.h>

int main() {

        int P = 2; //가장 큰 소수 변수
        int N = 3; //가장 작은 소수는 2이기에, 3부터 시작
    	while(true) {
    	    double tmp = sqrt(N);
    	    int M = (int) tmp; //정수
    	    for (int i=2; i<=M; i++) {
    	        int R = N % i;
				//소수 x
    	        if(R == 0) break;
				//소수의 조건 1과 자신의 값으로 나누어짐
    	        else if(i == M) P = N;
    	    }
	        N++;
	        if(N>100) break;
    	}
	printf("%d\n", P);
};


JAVA

public class Main {
	public static void main (String[] args) {

		int P = 2; //가장 큰 소수 변수
		int N = 3; //가장 작은 소수는 2이기에, 3부터 시작
		while(true) {
			double tmp = Math.sqrt(N);
			int M = (int) tmp; //정수
			for (int i=2; i<=M; i++) {
				int R = N % i;
				//소수 x
				if(R == 0) break;
				//소수의 조건 1과 자신의 값으로 나누어짐
				else if(i == M) P = N;
			}
			N++;
			if(N>100) break;
		}
		System.out.println(P);
	}
}