[알고리즘][소수] 소수💫 판별하기

반갑습니다 :)

 

 

오늘은 소수를 판별하는 알고리즘에 대해 살펴보려고 해요!

 

 

 

 

소수란?

prime number,

1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수

 

예시를 볼까요?

 

 

소수의 예

 

 

이렇게 1과 자신으로밖에 이뤄진 것을

 

소수라고합니다!

 

 

 

 

이를 판별하기 위해서는

 

곱해서 나올 수 있는 경우를 생각하면 됩니다!

 

 

 

 

그럼 다음 경우는 어떨까요?

 

3 x 4 와 4 x3 은 같다고 생각하여 적지 않았습니다!

 

 

 

이렇게 1과 자기자신 말고도

 

다양한 자연수가 존재한다면

 

소수가 아닙니다!

 

 

 

 

그럼

 

소수를 판별하기 위해서는

 

1과 자신밖에 없어야하군요!

 

 

 

 

그렇기 위해

 

도움숫자라는것을 두어서

 

 

하나씩 증가한 뒤,

 

나누면 되겠네요?

 

 

언제까지?

 

자기자신 숫자가 될 때 까지!

 

 

 

<알고리즘 1>

변수

입력한 숫자

도움 숫자

 

 

<알고리즘 2>

도움숫자를 2로 지정

(2로 지정한 이유는 소수는 1과 자신밖에 존재하지않기 때문)

 

 

 

 

 

 

그럼 5를 예시로 들어봐요!

 

나머지가 0이 아니라면 도움숫자를 1 증가!

 

다시 1 증가!

 

다시 1 증가!

 

나머지가 0일 때, 숫자와 도움숫자가 같다면 소수! 즉 5는 소수!

 

 

<알고리즘 3>

숫자 나누기 도움숫자 나머지가 0이 아니면

도움숫자를 1만큼 바꾸기

다시 숫자 나누기 도움숫자 나머지가 0인지 판별

 

 

<알고리즘4>

만약 숫자 나누기 도움숫자 나머지가 0일 때,

숫자와 도움숫자가 같다면 소수!

아니라면 소수가 아님!

 

 

 

 

 

그럼 다른 숫자로 해볼까요?

 

나머지가 0인데, 숫자와 도움숫자가 같지 않아요! 즉 4는 소수가 아니에요!

 

이해되셨나요? :B

 

 

 

---

 

 

그럼 이를 순서도로 그려보아요!

 

 

 

 

 

오늘은 소수를 판별하는 알고리즘에 대해

 

알아보았어요!

 

 

스크래치로 구현하기

↓

 

2020/03/18 - [스크래치(Scratch)] - [스크래치] 소수 판별하기

[스크래치] 소수 판별하기

 

 

 

많은 도움되셨다면❤와 구독 부탁드릴게요!

:)