[Java/Algorithm]소수와 합성수

자연수(-음수를 제외한 정수 0~99~)를 분류하는 두가지 종류
소수와 합성수

---

소수
Prime Number

• 1과 자기 자신 외에는 약수를 가지지 않는 자연수.

약수란?
6을 나눴을 때 0이 되는 수.
6의 약수는 1,2,3,6입니다.
자연수를 나눴을 때 나눠 떨어지게 하는(6%3는 2로 나누어 떨어집니다) 자연수를 말합니다.

• 2, 3, 5, 7, 11, 13, 17...
• 가장 작은 소수는 2이며, 이는 유일한 짝수 소수입니다.
• 모든 소수는 1보다 크고, 홀수입니다. (단, 2는 예외)

2~ 1000 사이 소수를 찾는 프로그램 코드. 나눗셈을 수행한 횟수 : 78022

• ↑ 코드 설명
  • 2(가장 작은 소수)~100사이의 소수를 찾습니다.(바깥 쪽 for문)
  • 1과 자기 자신 외에는 약수를 가지지 않아야 하기 때문에 안쪽 for문은 2~부터 n미만까지 for문을 사용합니다.
  • 만약 n이 사라면 안쪽 for문에서 4 % 2, 3이 돌아가겠죠.
    그럼 if문에서 4 % 2 의 나머지는 0이기 때문에 소수가 아닙니다.
  • 그럼 4 % 3을 할 필요가 없기 때문에
    break;를 통해 안쪽 for문만 빠져나갑니다. (바깥 for문은 계속 다시 실행되 다음 차례인 5가 실행됩니다.)

수행횟수를 줄이기 위해 
소수가 2를 제외하면 모두 홀수라는 점과
2 or 3으로 나누어 떨어지지 않으면 2x2인 4 와 3x2인 6으로도 나누어 떨어지지 않는 점을 이용하면
아래와 같이 이미 구한 소수로만 나누어 계산할 수 있습니다.

1000이하 소수를 구하는 프로그램2(개선version) 나눗셈을 수행한 횟수 : 78022

두 프로그램을 비교하면 알고리즘은
빠른 알고리즘은 메모리를 많이 요구한다.
는 걸 알 수 있습니다.

개선에 개선한 코드. 너무 잘 짜여진 코드라 올려봅니다...

---

합성수

• 약수와 반대되는 수.
• 합성수는 1보다 큰 자연수로 정의되며, 최소 합성수는 4입니다.
• 짝수이든 홀수이든 합성수가 될 수 있습니다.
• 1과 자기 자신 이외에도 약수를 가지는 자연수. 적어도 세 개 이상의 약수를 가집니다.
  ex) 4의 약수는 1, 2, 4입니다.