1978. 소수 찾기

https://www.acmicpc.net/problem/1978

 

 

 

✔ 유형 : 수학

✔ 문제 풀이: 소수의 특성과 두 수의 곱의 특성을 이용

 

소수의 정의

소수의 정의

소수 : 1과 자기 자신으로만 나누어지는 수

        : 약수가 2개인 수

 

합성수: 1과 자기 자신을 제외한 다른 약수를 가지고 있는 수

 

소수 판정법

소수 판정법

소수 = 1과 자기 자신으로만 나누어지는 수

        = 약수가 2개인 수

        = 2부터 N - 1 까지의 수로 나누어지지 않는 수

 

⬇️ 코드로 풀어보면 다음과 같다.

def isprime(int n)
   if n == 1 : return 0
   for i in range(2, n)
   	if n % i == 0 : return 0
    
   return 1

---

 

합성수 N에서 1을 제외한 가장 작은 약수는 √N 이하이다. 

N = 18 : 2 ≤ √18 , N = 25 : 5 ≤ √25, N = 21 : 3 ≤ √21

 

<증명>

합성수 N에서 1을 제외한 가장 작은 약수를 X라 하자.
N / X는 1이 아닌 약수이므로 X ≤ N/X
우변의 분모를 좌변으로 옮기면 X^2 ≤ N

 

 

✨ 2부터 √N까지의 수로 나누어지지 않는 수

def isprime(int n)
   if n == 1 : return 0
   for i in range(2, n)
    if( i * i > n ) break
   	if n % i == 0 : return 0
    
   return 1