BOJ 기본수학(소수)

소수에 대해 알아보자.

소수란?

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

매우 많이 들어본 정의이다.

소수와 반대되는 개념은 합성수인데 1은 소수와 합성수 모두 아니다.
소수는 2,3,5..등이 있다.

소수를 어떻게 판별하지?

1. 소수는 1이외에 약수를 가지면 안된다.
   그러므로 어떤 수 N이 소수인지 판별하기 위해선

   단순히 N보다 작은 수로 N을 나누어보면 된다.

2. 약수는 대칭성을 가진다.
   예를 들어 64의 약수를 살펴보자.
   
   64의 제곱근을 기준으로 대칭성을 가진다.

그렇다면

N의 제곱근보다 작은 수에서 약수가 존재하는 지 찾는다.

추가적으로 고려해줄 사항

• 1은 제외
• 짝수는 제외
• 2는 짝수이나 소수임을 고려

def is_prime(n):
    if n==2:
        return True
    if n==1 or n%2==0:
        return False
    else:
        for i in range(3, int(n**(1/2))+1):
            if n%i==0:
                return False
        return True

에라토스테네스의 체

소수를 약수로 가지는 수는 소수가 아니다

'약수는 대칭성을 가진다'는 원리가 여기서도 이용된다.

1~N까지의 수중에서 소수를 구해보자.

1. N의 제곱근보다 작은 수 중에서 소수를 찾아본다.
2. 소수의 배수들을 지워나간다.
3. 남은 수가 소수..!

위와 같은 원리를 파악하고 코딩해봤으나, 시간초과..^^

def is_prime(n):
    if n==2:
        return True
    if n==1 or n%2==0:
        return False
    else:
        for i in range(3, int(n**(1/2))+1):
            if n%i==0:
                flag = True
                return False
        return True
        
m = int(input())
n = int(input())
prime_lst = []
for i in range(2,int((n)**(1/2))+1):
    if is_prime(i) is True:
        prime_lst.append(i)

all_lst = list(range(m, n+1))
for p in prime_lst:
    l = 1
    while p*l <= n:
        l += 1
        if p*l in all_lst:
            all_lst.remove(p*l)
if 1 in all_lst:
    all_lst.remove(1)
if len(all_lst)==0:
    print(-1)
else:
    print(sum(all_lst))
    print(min(all_lst))

서칭해본 솔루션

def prime_list(n):
    sieve = [True]*n
    m = int(n**0.5)
    for i in range(2, m+1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False
    return [i for i in range(2, n) if sieve[i]==True]
print(prime_list(int(input())))

코드길이부터 차이가 심해서 현타씨게 맞았다,,

• n이하의 소수를 찾고 -> 각 소수들의 배수를 찾는 과정이 아니다.
• 일단 다 소수라고 가정한 후 앞에서부터 각 수의 배수를 제거해나간다.

골드바흐의 추측

• 나의 솔루션
  내가 풀때는 소수의 합이 n인 조합을 찾을 때 반으로 나눠서 찾지않고 앞에서부터 찾아나가면서 기존 소수조합보다 소수들의 차가 가장 작은 것을 업데이트하는 방법으로 작성했다.

def prime_list(n):
    sieve = [True]*n
    m = int(n**0.5)
    for i in range(2, m+1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False
    return [i for i in range(2, n) if sieve[i]==True]

def gold(n):
    prime_lst = prime_list(n)
    comb1 = 0; comb2 = 100000
    for i in prime_lst:
        if (n-i) in prime_lst:
            if i == n-i:
                return i, i
            if  abs(2*i-n) < abs(comb2 - comb1):
                comb1=i; comb2=n-i
    return comb1, comb2

iteration = int(input())
for _ in range(iteration):
    n = int(input())
    comb1 , comb2 =  gold(n)
    print(comb1 , comb2)

하지만 시간초과..!

• 서칭한 솔루션

def prime_list(n):
    sieve = [True]*n
    m = int(n**0.5)
    for i in range(2, m+1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False
    return [i for i in range(2, n) if sieve[i]==True]
def sosu(n):
    li=prime_list(n)
    idx = max([i for i in range(len(li)) if li[i]<=n/2])
    for i in range(idx,-1,-1):
        for j in range(i,len(li)):
            if li[i]+li[j]==n:
                return [li[i], li[j]]
for _ in range(int(input())):
    n = int(input())
    print(" ".join(map(str,sosu(n))))

위의 솔루션 원리는 아래와 같다.

• prime_list(이하 li)를 반으로 나누고 중간부터 앞으로 loop를 돌면서(i)
• i~n 까지 조건을 만족하는 수를 찾는다 (j)
  

코드 출처