정처기 실기 소수 구하기

소수 : 1보다 크며, 1과 자기자신만을 약수로 가지는 수.

 

방법1. 주어진 수 X를 2 ~ (X-1)까지의 숫자로 차례대로 나누면서 나머지가 있는지 없는지를 체크한다.

1) 나누어떨어진다 => 소수가 아니다

2) 안떨어진다 => 소수일 가능성이 있다. 만약에 피제수 X가 소수라면, X와 제수가 같은 경우에만 나누어 떨어진다.

3) 단 한번도 안떨어진다 => X는 소수이다

 

 

방법2. 주어진 수 X를 2 ~ √X까지의 숫자로 차례대로 나누면서 나머지가 있는지 없는지를 체크한다.

X의 제곱근은 SQR(X)로 구한다.

1) 나누어떨어진다 => 소수가 아니다

2) 안떨어진다 => 소수일 가능성이 있다. 만약에 피제수 X가 소수라면, X와 제수가 같은 경우에만 나누어 떨어진다.

3) 단 한번도 안떨어진다 => X는 소수이다