1. 10. 1. Defining Prime Number 순서도 수정.ㅡ

학습장/Algorithm

Shin Jaehyun 2018. 4. 23. 20:19

어제까지 수열을 마치고, 이제 '수학' 입니다.

문득 중학교 2학년때 친구따라 강남간다고, 수학의 정석 문제를 풀던 친구를 보고 깊은 감명을 받아 수1의 정석을 구매해서 행렬만 보고 때려치웠던 기억이 나네요.ㅡ_ㅡ;

게다가 수2는 엄두도 안나고, 수학에 흥미를 (이라고 쓰고 공부에 흥미를 읽습니다.).. 옛날 얘기는 이만 하고,

그런 저도 풀 수 있었으니, 아마 보시면 충분히 보시고 이해하시리라 싶습니다.

아마 정보처리기사 필기를 보셨다면, 전자계산기와 네트워크 관련 문제들에서 log 라는 것도 종종 보셨을 텐데요. '샤논의 법칙?' 이라든가..

다행히도, 자바, 안드로이드, 오라클, 스프링, node, 뭐 어딜 봐도 아직까지는 그 이상으로 난해한 문제는 없었던 것 같습니다.

그러니 '최소한 이정도만 하면, 프로그래밍하는데 당장은 지장이 없겠지.' 하고 접근해보면 어떨까 싶습니다. 그래서 가지고 있는 목차에서 단위를 나눠서 정리를 하려고요. 그 첫번째는 소수 (Prime Number) 입니다.

먼저 소수의 간단한 정의부터 보면

'양의 정수가 1과 자기 자신 뿐인 1보다 큰 자연수' 로 정의 되며, 암호분야에서 중요성이 부각되고 있다. 라고 하는군요. 더 자세한 링크는 아래에 적어둡니다.

그리고 이제부터 하나하나 해나갈 소수에 관련한 내용은 다음과 같습니다.

Prime Number 1. 소수 판별 (while, if)

Prime Number 2. 소수의 합 구하기 (while, if)

Prime Number 3. 소수의 개수 구하기 (1차원 배열, do ~ while, while, if)

간단한 정의, 즉 '양의 정수가 1과 자기 자신 뿐인 1보다 큰 자연수'라는 걸 기준으로 잡고 먼저 소수 판별하기를 보겠습니다.

아, 포스팅할때 제목을 보통 순서도와 Code를 ' 2 ', ' 1 ' 이렇게 두었었는데, 순서도를 보고 coding을 해야 편해서.. 순서를 앞으로는 바꿀까 합니다.

순서도를 그려보면 아래와 같습니다.

보아두시면 좋으실 듯... 한건,

divN과 compN 을 비교할경우,

만약 inputN이 1인 경우에는 compN이 0이 되겠죠?, 혹은 inputN이 2인 경우에는 compN은 1이 되어 시작할거에요.

그럼 나누는 수로 쓰이는 divN보다 작은 수가 되기때문에, 확실히 1, 또는 2인경우 달리 말해서는 무조건 소수인 경우를 제외시킬 수 있어서,

비교할 때에 ' >' 크다가 적용돼요. ' 설마 등호가 나올까.. 싶기는 하지만.. 신경이 쓰이더라고요.'

소수인지 판별하는 방법에는 이 외에도 제곱근을 이용하는 방법도 있어요.

예를 들어, 25가 소수인지 판별할 때에는 25의 제곱근을 구하고, 위와 같이 2부터 시작해서 5까지 진행해서 나머지가 있는지 없는지를 보는 겁니다.

(25의 경우는 나누는 수 가 제곱근 5가 되었을 때 나머지가 0이 되니까 소수가 아니고, 12인 경우는 3.XXXX 이렇게 나올텐데,

2에서 나머지가 0이 되니까, 제곱근이 되기 전에 나누어 떨어지고, 소수가 아닌게 되는겁니다. 이런 경우는 SQR(X)를 사용해요.

그럼 11의 경우는 (3 x 3 = ) 9 와 (4 x 4 =) 16 사이에 있으니까, 제곱근이 3.xxxx 이렇게 나올건데, 나누는 수를 2부터 시작해서 3까지 진행을 해도 나머지가 생기기 때문에,

소수가 된다는 거지요. )

중요.?;;;

위와 같은 순서도대로 진행하는 경우, 1을 입력했을 때 code를 실행하면 1도 소수로 나오더라고요.;

아무리 생각해도 아닌것 같아, code를 수정해보고, 그에 맞춰 순서도도 약간 수정을 했어요.