소수 쌍

문제 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다.

1 + 4 = 5, 7 + 10 = 17, 11 + 12 = 23

또는

1 + 10 = 11, 4 + 7 = 11, 11 + 12 = 23

수의 리스트가 주어졌을 때, 지민이가 모든 수를 다 짝지었을 때, 첫번째 수와 어떤 수를 짝지었는지 오름차순으로 출력하는 프로그램을 작성하시오. 위의 예제에서 1 + 12 = 13으로 소수이다. 그러나, 남은 4개의 수를 합이 소수가 되게 짝지을 수 있는 방법이 없다. 따라서 예제의 답은 4, 10이다.

입력 첫째 줄에 리스트의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이며, 짝수이다. 둘째 줄에 리스트에 들어있는 수가 주어진다. 리스트에 들어있는 수는 1,000보다 작거나 같은 자연수이며, 중복되지 않는다.

출력 첫째 줄에 정답을 출력한다. 없으면 -1을 출력한다.

예제 입력

6

1 4 7 10 11 12

예제 출력

4 10

네트워크 플로우 이분 매칭 소수 판정
코드 테스트하는 저지: https://www.acmicpc.net/problem/1017 - iljimae, 2016/09/30 08:11 M D
입력할 때 무조건 오름차순이어야 하는 건가요? - C295HB, 2016/10/03 17:16 M D
정답을 출력할때 오름차순으로 출력하시면 됩니다! 리스트에 있는 수들은 오름차순으로 주어진다는 보장이 없습니다. - iljimae, 2016/10/04 05:21 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

9개의 풀이가 있습니다.

소수인지 검사


bool is_prime_number(int num)
{
    for (int n = 2; n < (num / 2); n++)
    {
        if (num % n == 0)
            return false;
    }

    return true;
}

배열을 순회/재귀하며 사용하지 않은 값들로 소수 짝을 이룰 수 있는지 검사


bool check_child_prime(int size, int arr[])
{
    int key = -1;
    for (int n = 0; n < size; n++)
    {
        if (arr[n] == 0)
            continue;

        if (key == -1)
        {
            key = n;
        }
        else if (is_prime_number(arr[key] + arr[n]))
        {
            int key_val = arr[key];
            int n_val = arr[n];
            arr[key] = 0;
            arr[n] = 0;
            bool res = check_child_prime(size, arr);

            arr[key] = key_val;
            arr[n] = n_val;

            if (res == true)
                return true;
        }
    }

    for (int n = 0; n < size; n++)
    {
        if (arr[n] != 0)
            return false;
    }

    return true;
}

배열의 원본 데이터를 순회하며 출력할 값이 있으면 출력


void do_pair_prime(int size, int arr[])
{
    // 짝을 이뤄야하기 때문에 홀수는 안됨
    if (size <= 0 || size % 2 != 0)
    {
        printf("-1");
        return;
    }

    int key = arr[0];
    arr[0] = 0;

    int search_count = 0;

    for (int n = 1; n < size; n++)
    {
        if (is_prime_number(key + arr[n]))
        {
            int n_val = arr[n];
            arr[n] = 0;
            if (check_child_prime(size, arr))
            {
                search_count++;
                printf("%d ", n_val);
            }
            arr[n] = n_val;
        }
    }

    if (search_count <= 0)
        printf("-1");
}

값을 입력 받고 첫번째 수를 제외, 오름차순으로 정렬

void pair_prime()
{
    int in_size;
    scanf_s("%d", &in_size);

    std::list<int> in_list;
    for (int n = 0; n < in_size; n++)
    {
        int val;
        scanf_s("%d", &val);
        in_list.push_back(val);
    }
    int front = in_list.front();
    in_list.pop_front();
    in_list.sort();
    in_list.push_front(front);

    int* in_arr = new int[in_size];
    for (int n = 0; n < in_size; n++)
    {
        in_arr[n] = in_list.front();
        in_list.pop_front();
    }

    do_pair_prime(in_size, in_arr);

    delete[] in_arr;

    printf("\n");
    system("pause");
}

출력 값

6
1 4 7 10 11 12
4 10
계속하려면 아무 키나 누르십시오 . . .

2016/10/07 16:34

이 광표

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

소수인지 검사

bool is_prime_number(int num)
{
    for (int n = 2; n < (num / 2); n++)
    {
        if (num % n == 0)
            return false;
    }

    return true;
}



배열을 순회/재귀하며 사용하지 않은 값들로 소수 짝을 이룰 수 있는지 검사

bool check_child_prime(int size, int arr[])
{
    int key = -1;
    for (int n = 0; n < size; n++)
    {
        if (arr[n] == 0)
            continue;

        if (key == -1)
        {
            key = n;
        }
        else if (is_prime_number(arr[key] + arr[n]))
        {
            int key_val = arr[key];
            int n_val = arr[n];
            arr[key] = 0;
            arr[n] = 0;
            bool res = check_child_prime(size, arr);

            arr[key] = key_val;
            arr[n] = n_val;

            if (res == true)
                return true;
        }
    }

    for (int n = 0; n < size; n++)
    {
        if (arr[n] != 0)
            return false;
    }

    return true;
}


배열의 원본 데이터를 순회하며 출력할 값이 있으면 출력

void do_pair_prime(int size, int arr[])
{
    // 짝을 이뤄야하기 때문에 홀수는 안됨
    if (size <= 0 || size % 2 != 0)
    {
        printf("-1");
        return;
    }

    int key = arr[0];
    arr[0] = 0;

    int search_count = 0;

    for (int n = 1; n < size; n++)
    {
        if (is_prime_number(key + arr[n]))
        {
            int n_val = arr[n];
            arr[n] = 0;
            if (check_child_prime(size, arr))
            {
                search_count++;
                printf("%d ", n_val);
            }
            arr[n] = n_val;
        }
    }

    if (search_count <= 0)
        printf("-1");
}



값을 입력 받고 첫번째 수를 제외, 오름차순으로 정렬
void pair_prime()
{
    int in_size;
    scanf_s("%d", &in_size);

    std::list<int> in_list;
    for (int n = 0; n < in_size; n++)
    {
        int val;
        scanf_s("%d", &val);
        in_list.push_back(val);
    }
    int front = in_list.front();
    in_list.pop_front();
    in_list.sort();
    in_list.push_front(front);

    int* in_arr = new int[in_size];
    for (int n = 0; n < in_size; n++)
    {
        in_arr[n] = in_list.front();
        in_list.pop_front();
    }

    do_pair_prime(in_size, in_arr);

    delete[] in_arr;

    printf("\n");
    system("pause");
}


출력 값
6
1 4 7 10 11 12
4 10
계속하려면 아무 키나 누르십시오 . . .

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

JAVA

첫 숫자를 기준 값으로 놓고, 이 기준값과 순회 하면서 짝을 짓습니다. 짝을 지은 수 중 합이 소수면 일단 기준 값의 짝을 저장합니다. 그런후 기준 값과 짝을 제외한 List로 재귀 호출을 합니다. 재귀 호출할 process 함수는 인자로 받은 리스트의 첫번째 값을 지역 기준값으로 놓고, 순회하면서 짝과의 합이 소수인지 검사하고 소수라면 기준값과 짝을 제거한 List로 process함수를 재호출 합니다. 이렇게 해서 List가 모두 비어졌으면 최초 기준값의 짝을 print 합니다.


    private static void setPrimeNumber(int num);

이 함수는 인자로 받은 num 이하의 숫자들이 소수인지 아닌지 판단할 수 있는 값을 계산합니다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;

/**
 * Created by moonti on 2016. 10. 16..
 */
public class PrimeNumberPair {

    private static final int SIZE = 1005;
    private static int[] sPN = new int[SIZE];
    private static int n;
    private static LinkedList<Integer> numbers = new LinkedList<>();
    private static int firstNumbersPair;
    private static LinkedList<Integer> result = new LinkedList<>();


    public static void main(String[] args) {
        n =  Integer.parseInt(args[0]);
        for (int i=1; i<=n; i++) {
            numbers.add(Integer.parseInt(args[i]));
        }
        setPrimeNumber(1000);

        int first = numbers.get(0);
        for (int i = 1; i<n; i++) {
            if (isPrimeNumber(first + numbers.get(i))) {
                firstNumbersPair = numbers.get(i);
                LinkedList<Integer> clone = (LinkedList<Integer>) numbers.clone();
                clone.remove(0);
                clone.remove(i-1);
                if (clone.size() == 0) {
                    result.add(firstNumbersPair);
                } else {
                    process(clone);
                }
            }
        }
        Collections.sort(result);
        for (Integer num: result) {
            System.out.print(" " + num);
        }

    }

    private static void process(LinkedList<Integer> list) {
        int first = list.get(0);
        for (int i = 1; i<list.size(); i++) {
            if (isPrimeNumber(first + list.get(i))) {
                LinkedList<Integer> clone = (LinkedList<Integer>) list.clone();
                clone.remove(0);
                clone.remove(i-1);
                if (clone.size() == 0) {
                    result.add(firstNumbersPair);
                } else {
                    process(clone);
                }
            }
        }
    }

    private static void setPrimeNumber(int num) {
        for (int i=1; i<=num; i++) {
            for (int j=1; j*i<= num; j++) {
                sPN[j*i]++;
            }
        }
    }

    private static boolean isPrimeNumber(int num) {
        if (sPN[num] < 3) {
            return true;
        } else {
            return false;
        }
    }
}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

#include <stdio.h>
#include <stdlib.h>

int size;
int* flag;
int* data;
int* out;
int index;

void coupling(int count, int value);
bool verdict(int a, int b);
void initflag();
void sorting();
void main() {
    int count = 0;
    index = 0;

    scanf("%d", &size);
    data = (int*) malloc (sizeof(int) * size);
    for(int i = 0; i < size; i++) 
        scanf("%d", &data[i]);

    sorting();

    out = (int*) malloc (sizeof(int) * size);
    for(int i = 0; i < size; i++) 
        out[i] = 0;

    flag = (int*) malloc (sizeof(int) * size);
    for(int i = 0; i < size; i++) 
        flag[i] = 0;
    flag[0] = 1;

    for(int i = 1; i < size; i++) { 
        if(!verdict(data[0], data[i])) continue; // 소수가 아니라면 패스
        flag[i] = 1;
        coupling(1, data[i]);
        flag[i] = 0;
        initflag();
    }

    bool b = false;
    for(int i = 0; i < size; i++)
        if(out[i] != 0) {
            printf("%d\n", out[i]);
            b = true;
        }
    if(b == false)
        printf("-1");
}

void coupling(int count, int value) {
    if(count == 3) {
        bool clear = true;
        for(int i = 1; i < size; i++)
            if(flag[i]==0)
                clear = false;

        if(clear == true) {
            out[index] = value;
            index++;
        }
    }

    for(int i = 1; i < size; i++) {
        if(flag[i] == 0) {
            flag[i] = 1;
            for(int j = 1 ; j < size; j++) {
                if(flag[j] == 0 && i!=j) {
                    if(!verdict(data[i], data[j])) continue; // 소수가 아니라면 패스
                    flag[j] = 1;
                    count++;
                    coupling(count, value);
                    flag[j] = 0;
                }
            }
            flag[i] = 0;
        }
    }
}

bool verdict(int a, int b) { //소수면 1
    int temp = a+b;
    int k = temp/2;
    if(temp == 2)
        return true;

    for(int i = 2; i <= k; i++) 
        if(temp%i==0)
            return false;
    return true;
}

void initflag() {
    for(int i = 1; i < size; i++) 
        flag[i] = 0;
}

void sorting() {
    for(int i = 1 ; i < size  ; i++) {
        int index = i;
        for(int j = i-1  ; j >= 0  ; j--) {
            int temp;
            if(data[index] < data[j]) {
                temp = data[index];
                data[index] = data[j];
                data[j] = temp;
                index = j;
            }
        }
    }
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

재귀로 풀어서 엄청 느리겠지만...일단 이분매칭이 뭔지 좀 공부해봐야겠네요.

# 1000보다 작은 수 두개의 합이 소수인지 판별해야하므로 2000이하의 소수를
# 에라토스테네스의 체로 판별합니다.
p = [False, False] + [True] * 2000
for i, n in enumerate(p):
    if n:
        p[i*2:-1:i] = [False] * (2000 // i - 1)
primes = [x for x in range(2000) if p[x]]


def do(xs):
    if len(xs) is 0:
        return [], True
    if len(xs) is 1:
        return [], False
    result = []
    (x, *ys) = xs
    for (i, y) in enumerate(ys):
        zs = ys[:i] + ys[i+1:]
        if p[x + y]:
            k, r = do(zs)
            if r:
                result.append(y)
    j = len(result) > 0
    return result, j


def main():
    n = int(input())
    xs = [int(x) for x in input().split(' ')][:n]
    ys, z = do(xs)
    if z:
        print(" ".join(str(x) for x in sorted(ys)))
    else:
        print(-1)


if __name__ == '__main__':
    main()
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

1000보다 작은 소수를 미리 구해놓으면 쉽겠군요. 에라토스테네스의 체로

char primes[1000];

int main(int argc, const char * argv[]) {
    memset(primes, -1, 1000); // -1 for undecided yet
    // sieve
    primes[0] = 0;
    primes[1] = 0;
    for (int i=2; i<1000; i++) {
        if (primes[i] == 0)
            continue;
        primes[i] = 1;
        for (int p=i*2; p<1000; p += i) {
            primes[p] = 0;
        }
    }

이제 primes[i]는 i가 소수일 때 1, 아니면 0입니다.

리스트의 첫 숫자와 결합하여 소수인 수들에 대해서 남은 수들도 짝으로 소수가 만들어지는지 확인해봐야겠네요.

    int nums[] =  {1, 4, 7, 10, 11, 12};

    for (int i=1; i<6; i++) {              // 1자리부터 시작
        if (primes[nums[0] + nums[i]]) {   // 0자리와 i자리 합쳐 소수?
            swap(nums, i, 1);              // i자리를 1번으로 옮긴 뒤 2~6 자리들에 확인
            if (pairprime(nums, 2, 6)) { 
                swap(nums, i, 1);
                printf("%d ", nums[i]);    // 맞으면 출력
            } else {
                swap(nums, i, 1);          // 맞든 틀리든 원래대로 값 되돌려놓기
            }
        }
    }

그런데 이 로직은 pairprime에서 그대로 사용될 듯 합니다. 범위 i~j 의 값들이 짝 소수 되려면 첫 값이랑 소수 되는 짝을 제외한 나머지들에 대해 재귀적으로 확인하면 되겠네요.

int pairprime(int nums[], int start, int end) {
    if (start >= end) return 1;
    for (int i=start + 1; i<end; i++) {
        if (primes[nums[start] + nums[i]]) {
            swap(nums, i, start + 1);
            if (pairprime(nums, start + 2, end)) {
                swap(nums, i, start + 1);
                return 1;
            }
            swap(nums, i, start + 1);
        }
    }
    return 0;
}

swap을 했다가 되돌리는 걸 빼먹어서 틀린 답이 나오더군요. ㅎㅎ

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def prime(n):
    if n<2:
        return 0
    if sum(x for x in range(2,n) if n%x==0)==0:
        return 1
    else:
        return 0
def prime_ex(data):
    if data==[]:
        return 1
    n=data.pop(0)
    for i in range(len(data)):
        if prime(n+data[i])==1:
            if prime_ex(data[0:i]+data[i+1:])==1:
                return 1
            else:
                return -1

def prime_pair(data):
    n=data[0][0]
    data=data[1]
    result=[]
    a=data.pop(0)
    for i in range(n-1):
        if prime(a+data[i])==1:
            if prime_ex(data[0:i]+data[i+1:])==1:
                result+=[data[i]]
    result.sort()
    if result==[]:
        return -1
    else:
        return result
prime_pair([[6],[1,4,7,10,11,12]])
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

python 3.6 using itertools.combinations()

from itertools import combinations
from math import sqrt

def generate_groups(lst, n):
    if not lst: 
        yield [] 
    else: 
        for group in (((lst[0],) + xs) for xs in combinations(lst[1:], n-1)):
            for groups in generate_groups([x for x in lst if x not in group], n): 
                yield [group] + groups

def isPrime(n):
    find_factor = list((i, n//i) for i in range(1, int(sqrt(n))+1) if n%i == 0)
    if len(find_factor) == 1: return True
    else: return False

입출력문

# input
from random import sample

how_many_numbers = int(input())
in_lst = sorted(sample(range(1,1001), how_many_numbers))
print(*iter(in_lst), sep=' ')

# output
result = []

for x in generate_groups(in_lst, 2):
    a = True
    for y in x: a &= isPrime(sum(y))
    if a == True: result.append(x[0][1])

if result: print(*iter(set(result)), sep=' ')
else: print('-1')

>>>
 6
342 490 547 623 932 977
-1
>>>
 8
3 9 10 11 14 17 18 20
10 14 20
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Python3

def primes_under(n):
    nums = set(range(2, n))
    primes = set()
    while nums:
        p = min(nums)
        primes.add(p)
        nums -= set(range(p, n, p))

    return primes

def pairable(lst):
    if not lst: 
        return True

    for i in range(1, len(lst)):
        if lst[0] + lst[i] in primes and pairable(lst[1:i] + lst[i+1:]):
            return True

    return False

inp = '6 1 4 7 10 11 12'
lst = [int(x) for x in inp.split()[1:]]
primes = primes_under(1001)

for i in range(1, len(lst)):    
    if lst[0] + lst[i] in primes and pairable(lst[1:i] + lst[i+1:]):
        print(lst[i], end=' ')
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

네트워크 플로우 x 1
이분 매칭 x 1
소수 판정 x 1

언어별 풀이 현황
전 체 x 9
cpp x 3
java x 1
기 타 x 2
python x 3