📣 #12 수학

2021.10.14에 작성한 글

BaaaaaaaarKingDog 실전 알고리즘

 

---

💡 소수

• 1과 자기 자신으로만 나눠지는 수 = 약수가 2개인 수
• 반대개념 : 합성수

📌 소수 판정법

1. 소수의 정의 이용
   👉2부터 N-1까지의 수로 나누어지지 않는 수이다.
   시간 복잡도는 O(N)

bool isprime(int n) {
	if (n == 1 ) return 0; //1은 소수X
    for (int i= 2; i < n; i++) {
    	if (n % i == 0) return 0;
    }
    return 1;
}

   2. 합성수 N에서 1을 제외한 가장 작은 약수는 √N이하이다.
       👉 2부터 √N까지의 수로 나누어지지 않으면 소수이다.
       시간복잡도는 O(√n)

bool isprime(int n) {
	if (n == 1 ) return 0; //1은 소수X
    //주의할 점 : sqrt쓰지말기(실수의 저장, 연산과정에서 오차발생하기때문에 i*i로 써서 연산을 정수에서 처리할 것)
    for (int i= 2; i*i <= n; i++) {
    	if (n % i == 0) return 0;
    }
    return 1;
}

   3.개선

   4.에라토스테네스의 체

---

💡최대공약수

• 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계
  • 512MB = 1.2억개의 int
  • int = 4byte

---

💡연립합동방정식

📌

---

💡 이항계수

• int(4 byte) : 21억 비슷(2,147,483,647)
  • 10의 10제곱 안됨. longlong 쓰기
• longlong(8 byte)
  • 80번째 피보나치 수를 구하는 문제와 같이 int 자료형이 표현할 수 있는 범위 넘어서면 integer overflow 주의. 대신 longlong 사용