골드바흐의 추측_9020번
https://www.acmicpc.net/problem/9020

1. 문제 이해

1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.
골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.
2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

• 아이디어
  1. 2보다 큰 짝수 n에 대하여 소수+소수로 나타낼 수 있으면 출력하라.
  2. 단, 그 경우가 여럿일 때는 소수와 소수의 차가 가장 작은 것을 출력하라.
  [결론] 소수의 구하기 문제다.
  

2. 첫번째 구현(1804ms)

from sys import stdin;
input = stdin.readline;

def findPrime(p):
    if p == 1:
        return 0;
    if p == 2 :
        return p;
    if p % 2 == 0:
        return 0;
    
    for i in range(3, p, 2):
        if p % i == 0 :
            return 0;
    else :
        return p;

if __name__ == "__main__":
    T = int(input());
    nums = list(int(input()) for _ in range(T));
    
    for n in nums:
        n1 = n//2;
        while True :            
            if findPrime(n1) == 0 :
                n1 -= 1;
                continue;
            else :
                n2 = n - n1;
                if findPrime(n2) == 0 :
                    n1 -= 1;
                    continue;
                else : 
                    print(f"{n1} {n2}");
                    break;

• findPrime 함수는 매개변수 p를 받아서 소수인지 판별 해주는 함수다.
• 이렇게 풀어도 통과는 되지만, 알고리즘 스터디를 같이 하는 팀원들은 88ms, 216ms인데 반해 나의 코드는 너무나도 느렸다(1804ms).

2. 에라토스테네스의 체

다른 팀원과 나의 코드 차이는 이것이었다. 여러 수를 같이 소수 판별하기 위해서는 에라토스테네스의 체 알고리즘이 효과적이다.

def is_prime_num(n):
    arr = [True] * (n + 1) 
    arr[0] = False
    arr[1] = False

    for i in range(2, n + 1):
        if arr[i] == True: 
            j = 2

            while (i * j) <= n:
                arr[i*j] = False 
                j += 1

    return arr

개념은 쉽다. 2부터 n까지의 수에 배수란 배수들은 다 없애주는 알고리즘이다.
다음은 위의 '골드바흐의 추측'문제에 이 알고리즘을 적용해본다.

3. 두번째 도전('에라토스테네스의 체' 사용 - 시간초과)

from sys import stdin;
input = stdin.readline;

def is_prime(n):
    arr = [True] * (n+1);
    arr[0] = False;
    arr[1] = False;

    
    for i in range(2, n+1):
        if arr[i]:
            for j in range(2*i, n+1, i):
                arr[j] = False;
    return arr;
                
if __name__ == "__main__":
    T = int(input());
    for _ in range(T):
        n = int(input());
        primes = is_prime(n);        
        for j in range(n//2,1,-1):
            if primes[j] and primes[n-j] :
                print(f"{j} {n-j}");
                break;

미치겠네 진짜 ㅋㅋㅋㅋㅋㅋ
시간으로는 역대급을 찍었습니다. 공부 하나도 안하고 했을 때도 4초는 안 걸렸는데,,, ㅋㅋㅋㅋㅋ

4. 세번째 도전(김현진)

현진 누나 코드를 봤다..

from sys import stdin;
input = stdin.readline;

if __name__ == "__main__":
    prime = [False, False] + [True] * 9999; 
    for i in range(2, int(10001 ** 0.5)+1):
        if prime[i]:
            for j in range(2*i, 10001, i):
                prime[j] = False;
                
    T = int(input());
    for _ in range(T):
        n = int(input());
        for j in range(n//2,1,-1):
            if prime[j] and prime[n-j] :
                print(f"{j} {n-j}");
                break;

• 아이디어
  1) 숫자의 최댓값이 너무 크지 않으면, 초장에 소수를 포함한 배열을 만들어 놓으면 빠르다.
  => '이것이 코딩테스트다 - 나동빈 저(108p)' : 파이썬 3.7 코드 작성 시, 자신의 코드가 1초에 2000만 번의 연산을 수행할 수 있다고 가정하고 문제를 풀면 안정적이다. 라고 했다.
  => 다시 위의 문제의 경우, for i in range(2, int(10001 * 0.5) +1)에 for j in range(2i, 10001, i) 연산을 돌려준다. 전자의 경우 98회에 후자의 경우 훨씬 더 적겠지만, 대충 회당 10000번씩 돈다고 쳐도, 980000회로 20000만회에 훨씬 밑도는 수다. 실제로는 98만회보다 훨씬 더 적게 연산할 것이므로 초반에 소수를 포함하는 배열을 만드는게 유리하게 된다.
  

5. 소수 찾기 다른 문제 도전

소수의 연속합 (1644번)
https://www.acmicpc.net/problem/1644

5-1. 첫번째 시도(2228ms)

from sys import stdin;
input = stdin.readline;

if __name__ == "__main__":    
    
    N = int(input());
    # 1. 소수 판별
    prime = [False,False]+ [True] * N;
    for i in range(2, int((N+1)**0.5)+1):
        if prime[i] :
            for j in range(2*i, N+1, i):
                prime[j] = False;
                
    # print('>>>>', len(prime), prime);
    primes = [];   
    
    for k in range(2, len(prime)):
        # print(f"total : {len(prime)+1} // k : {k}")
        if prime[k]:
            primes.append(k);            
    count = 0;
    
    for a in range(len(primes)):
        if primes[a] > N:
            break;
        s = 0;
        for b in range(a, len(primes)):
            if s > N :
                break;
            elif s == N :
                count +=1 ;
                break;
            else :
                s += primes[b]
                
    print(count)            

5-2. 두번째 시도(1680ms)

from sys import stdin;
input = stdin.readline;

def get_prime(n):
    prime = [False,False]+ [True] * n;
    for i in range(2, int((n+1)**0.5)+1):
        if prime[i] :
            for j in range(2*i, n+1, i):
                prime[j] = False;
    return [k for k in range(2,n+1) if prime[k] == True];

if __name__ == "__main__":   
    N = int(input());
    primes = get_prime(N);
    count = 0;
    
    for a in range(len(primes)):  
        s = 0;
        for b in range(a, len(primes)):
            s += primes[b];
            if s > N :
                break;
            elif s == N :
                count +=1 ;
                break;               
        
    print(count)            

6. 결론

소수 판별 문제는 두 가지로 좁혀서 생각해볼 수 있다. 첫 번째는 해당 수가 소수인지 판별하는 문제(골드바흐의 추측), 두 번째는 해당 수까지의 소수들을 가지고 뭔가를 하는 문제(소수의 합)이다.

그래서 두 유형에 따라 소수 판별 공식도 달라진다.

# 1. 소수 판별(에라토스테네스의 체) > True or False
def is_prime(n) :
    prime = [False,False]+ [True] * n;
    for i in range(2, int((n+1)**0.5)+1):
        if prime[i] :
            for j in range(2*i, n+1, i):
                prime[j] = False;
    return prime;

# 2. n까지의 소수 목록 산출 
def get_prime(n):
    prime = [False,False]+ [True] * n;
    for i in range(2, int((n+1)**0.5)+1):
        if prime[i] :
            for j in range(2*i, n+1, i):
                prime[j] = False;
                
    return [k for k in range(2,n) if prime[k] == True];