소수 판별

설명

• 소수(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);
	}
}

• 웹컴파일러에서 프로그래밍 연습하기
• [이기적] 정보처리기사 무료영상 내용 참고
• [이기적] 정보처리기사 실기 책 내용 참고