소수 쌍
문제 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {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
입력할 때 무조건 오름차순이어야 하는 건가요?
-
C295HB,
2016/10/03 17:16
정답을 출력할때 오름차순으로 출력하시면 됩니다! 리스트에 있는 수들은 오름차순으로 주어진다는 보장이 없습니다.
-
iljimae,
2016/10/04 05:21
16개의 풀이가 있습니다.
소수인지 검사
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
계속하려면 아무 키나 누르십시오 . . .
소수인지 검사
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
def primes_under(n):
nums, primes = set(range(2, n)), set()
while nums:
p = min(nums)
primes.add(p)
nums -= set(range(p, n, p))
return primes
def pairable(lst):
global primes
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'
n, *lst = map(int, inp.split())
primes = primes_under(1001)
for i in range(1, n):
if lst[0]+lst[i] in primes and pairable(lst[1:i]+lst[i+1:]):
print(lst[i], end=' ')
def isPrime(num):
return all([num%i for i in range(2, num//2+1)]) if num > 1 else False
def popFriend(arr):
for i in range(1, len(arr)):
if isPrime(arr[0]+arr[i]):
return [arr[0], arr[i]], arr[1:i]+arr[i+1:]
return False, []
inp = '6\n1 4 7 10 11 12'
n, nums = int(inp.split()[0]), [int(i) for i in inp.split()[1:]]
res = []
for i in range(1, len(nums)):
nums = nums[:1]+nums[2:]+[nums[1]]
tmp = nums
sol = []
while len(tmp):
friends, tmp = popFriend(tmp)
if friends:
sol.append(friends)
if len(sol) == len(nums)//2:
res.append(sol[0][1])
if len(res):
print(sorted(res))
else:
print('-1')
val primes = Array.fill(2001)(false)
for(i <- 2 until primes.length){
var j = 1
var cnt = 0
while(j <= Math.sqrt(i).toInt){
if(i % j == 0) cnt += 1
j += 1
}
if(cnt == 1) primes(i) = true
}
def primeSet(list:List[Int]):List[Int] = {
def check(idx:Int, comb:Array[Boolean]):Boolean = {
println(idx, comb.toList.mkString(" "))
idx match {
case x if list.length - 1 == idx => comb.count(_ == false) == 0
case x if comb(idx) => check(idx + 1, comb)
case _ => {
var res = false
for(i <- idx + 1 until list.length){
var bool = false
if(!comb(i) && primes(list(idx) + list(i))){
comb(i) = true
comb(idx) = true
println(idx, i)
bool = check(idx + 1, comb)
}
if(bool) res = true
}
res
}
}
}
var ans = List[Int]()
for(i <- 1 until list.length){
if(primes(list(0) + list(i))){
println(list(i))
var combination = Array.fill(list.length)(false)
combination(0) = true
combination(i) = true
if(check(1 , combination)){
ans = list(i) +: ans
}
}
}
ans.sorted
}
println(primeSet(List(1, 4, 7, 10, 11, 12)))
import sys
def is_prime_no( n ):
if n % 2 == 0:
return 0
else:
for i in range(2,(n>>1)+1):
if n % i == 0:
return 0
return 1
def swap_v(l, i1, i2):
tmp = l[i1]
l[i1] = l[i2]
l[i2] = tmp
def is_prime_pair_list(l, s, depth):
#print("{}{}".format(' '*depth*2, l[s:]))
if (len(l) - s) == 2:
if is_prime_no(l[s] + l[s+1]) == 1:
return 1
else:
return 0
ret = 0
v1 = l[s]
for i in range(s+1, len(l)):
v2 = l[i]
if is_prime_no(v1 + v2) == 1:
if i > (s+1):
swap_v(l, s+1, i)
if is_prime_pair_list(l,s+2, depth+1) == 1:
ret = 1
break
return ret
number_list = list(map(int, raw_input().split(' ')))
if len(number_list) % 2 != 0:
print("you need to type event count of numbers")
sys.exit(0)
v1 = number_list[0]
l = []
for i in range(1, len(number_list)):
number_list = sorted(number_list)
v2 = number_list[i]
#print("[{}:{}]".format(v1,v2))
if is_prime_no(v1 + v2) == 1:
if i > 1:
swap_v(number_list, 1, i)
if is_prime_pair_list(number_list,2, 1) == 1:
l.append(number_list[1])
print("{}".format(l))
def isprime(n):
for i in range(2,int(n**0.5)+1):
if n%i == 0: return False
return True
def paircheck(lst):
ret = []
if lst == []: return True
for i in range(1,len(lst)):
if isprime(lst[0]+lst[i]) and bool(paircheck(lst[1:i]+lst[i+1:])):
ret.append(lst[i])
return ret
inp = [1,4,7,10,11,12]
x = sorted(paircheck(inp))
print( x if x else -1 )
package test;
import java.util.ArrayList;
import java.util.Scanner;
public class test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int numTemp[] = new int[sc.nextInt()];
for (int i = 0; i < numTemp.length; i++)
numTemp[i] = sc.nextInt();
ArrayList<Integer> num = new ArrayList<>();
ArrayList<Integer> ans = new ArrayList<>();
for (int i = 0; i < numTemp.length; i++)
num.add(numTemp[i]);
int with1st = 0;
int[] Pnum = Pnum(num.get(num.size() - 2) + num.get(num.size() - 1));
for (int n = 0; n < numTemp.length - 1; n++) {
for (int l = 0; l < numTemp.length / 2; l++)
end: for (int i = 0; i < num.size() - 1; i++)
for (int j = i + 1; j < num.size(); j++)
restart: for (int k = 0; k < Pnum.length; k++)
if (num.get(i) + num.get(j) == Pnum[k]) {
if (num.get(i) == numTemp[0])
for (int m = 0; m < ans.size(); m++)
if (ans.get(m) == num.get(j))
break restart;
if (num.get(i) == numTemp[0])
with1st = num.get(j);
num.remove(j);
num.remove(i);
break end;
}
if (num.size() == 0 && with1st != 0)
ans.add(with1st);
with1st = 0;
for (int i = 0; i < numTemp.length; i++)
num.add(numTemp[i]);
}
for (int i = 0; i < ans.size(); i++)
System.out.print(ans.get(i) + " ");
}
private static int[] Pnum(int n) {
ArrayList<Integer> Pnum = new ArrayList<>();
Boolean go = true;
for (int i = 3; i < n + 1; i++) {
for (int j = 2; j < i; j++)
if (i % j == 0)
go = false;
if (go)
Pnum.add(i);
go = true;
}
int[] temp = new int[Pnum.size()];
for (int i = 0; i < Pnum.size(); i++)
temp[i] = Pnum.get(i);
return temp;
}
}
import sys
# 2000이하 소수 리스트
primes = list(range(2, 2001))
for i in range(2, 2001):
primes = list(filter(lambda x : not (x%i == 0 and x > i), primes))
k = 0
def f(L, idx=1, ans=[]):
if not L:
global k
k += 1
sys.stdout.write(str(ans[1]) + ' ')
return
if idx == len(L):
return
if L[0] + L[idx] in primes:
T = L[:]
A = ans[:]
A.append(T.pop(0))
A.append(T.pop(idx-1))
f(T, 1, A)
f(L, idx+1, ans)
N = int(sys.stdin.readline())
L = list(map(int, sys.stdin.readline().strip('\n').split()))
L.sort()
f(L)
if k == 0: sys.stdout.write('-1')
result = []
def isPrime(num):
for i in range(2, (num // 2) + 1):
if num % i == 0:
return False
return True
def findPrime(i, lst, nums):
if len(lst) == len(nums):
result.append(lst)
return
for n in range(i, len(nums) - 1):
if nums[n] not in lst:
for j in range(n + 1, len(nums)):
if (nums[j] not in lst) and isPrime(nums[n] + nums[j]):
newlst = lst.copy() + [nums[n], nums[j]]
findPrime(n, newlst, nums)
N = int(input('리스트의 크기: '))
nums = [int(i) for i in input('리스트에 들어있는 수: ').split()]
findPrime(0, [], nums)
s = set()
for r in result:
s.add(r[1])
print(sorted(s) if len(s) >0 else -1)