문제:

환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이어붙이고 그 끈을 다시 길이가 소수인 끈 두개로 정확히 나눌 수 있다면 두 사람은 환상의 짝꿍이라고 한다. 하지만 그들은 길이가 소수인 두개의 끈으로 나눌 수 있는지 판단하는 것이 어려워서 대부분 서로가 인연임을 모르고 그냥 지나간다고 한다. 애석하게도...

그런 그들을 위해서 어떤 두 사람이 환상의 짝꿍인지 판단하는 프로그램을 작성하라.

편의상 두 사람의 끈을 이어붙일 때와 나눌 때 손실되는 끈의 길이는 0이라고 가정한다.

입력:

첫째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 500)가 주어진다.

둘째 줄부터 T개 줄에 두 사람이 가지고 있는 끈의 길이를 나타내는 정수 A, B가 공백으로 구분되어 주어진다. (1 ≤ A, B ≤ 2 × 10^12)

출력:

각 테스트 케이스마다 한 줄씩 두 사람의 끈을 이어붙이고 그 끈을 다시 길이가 소수인 두개의 끈으로 정확히 나눌 수 있다면 YES, 불가능하면 NO를 출력하라.

풀이방법:

**pypy3으로 통과한 코드입니다.**

 

 A와 B의 합이 두 개의 소수의 나누어지는지 완전알고리즘 방법으로 모두 찾는 것은 힘들다.(A,B는 최대 2x10^12)

따라서 '골드바흐의 추측'을 사용하면 경우의 수를 크게 줄일 수 있다.

 

 골드바흐의 추측은 2보다 큰 모든 짝수는 두 개의 소수의 합으로 표시할 수 있다는 것이다. 즉, 두 수의 합이 2를 제외한 짝수라면 골드바흐의 추측으로 인해 두 소수의 합으로 나눌 수 있다. 그러므로 이제 두 수의 합이 홀수인 경우에 대해서만 생각하면 된다. (확인된 수치적 결과로는 10^18까지 확인되었다고 한다. 따라서 범위 안의 수들은 모두 골드바흐 추추측을 만족한다.)

 

 두 소수의 합이 홀수가 되기 위해서는 짝수 소수 + 홀수 소수 인 경우만 존재한다. 소수 중에서 짝수인 소수는 2만 존재하기 때문에 A+B-2가 소수인지만 확인하면 된다. 하지만 A와 B의 수가 매우 큰 수까지 존재하기 때문에 해당 수 까지 소수인지 확인하는 것은 어렵다.(혹은 메모리초과가 발생한다.) 따라서 소수를 판정하는 방법을 두 가지로 나눠서 파악한다.

 

 A+B의 합은 최대 4x10^12까지 가능하다. 그리고 일반적으로 소수를 판정하는 방법으로는 1부터 해당 수의 sqrt() 값까지 확인하면 된다. 즉, 4x10^12까지의 소수를 찾아놓는 것이 아닌 sqrt() 값인 2x10^6까지만 소수를 찾아서 효율성을 향상시키도록 한다. 2x10^6까지는 에라토스테네스의 체를 사용해서 소수를 찾아두고, 이 이상의 수가 들어오게 된다면, 찾아놓은 소수로 나눠서 나눠지는 수가 있는지 확인한다. 따라서 A+B-2가 소수라면 YES를 아니라면 NO를 출력하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import sys
 
def check(prime):
    try:
        if sosu[prime]:
            return True
        else:
            return False
    except:
        for s in sosulist:
            if prime%s==0:
                return False
        return True
        
= int(sys.stdin.readline())
sosu = [True]*(2*pow(10,6)+1)
sosulist=[]
sosu[0],sosu[1]=False,False
for i in range(2,len(sosu)):
    if sosu[i]:
        sosulist.append(i)
        for j in range(i*2,len(sosu),i):
            sosu[j]=False
 
for _ in range(n):
    a,b = map(int,sys.stdin.readline().split())
    line = a+b
    if line%2==0:
        if line==2:
            print("NO")
        else:
            print("YES")
    else:
        if check(line-2):
            print("YES")
        else:
            print("NO")
cs

문제링크:

www.acmicpc.net/problem/15711

 

15711번: 환상의 짝꿍

환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이

www.acmicpc.net

 

'Algorithm > Python' 카테고리의 다른 글

[BOJ]2003. 수들의 합 2  (0) 2021.01.19
[BOJ]2661. 좋은 수열  (0) 2021.01.14
[BOJ]14938. 서강그라운드  (0) 2021.01.07
[BOJ]1922. 네트워크 연결  (0) 2021.01.05
[BOJ]1613. 역사  (0) 2020.12.31

문제:

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

 

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

 

예를 들어 8은 3+5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 +17 = 7+13, 42 = 5+37 = 11+ 31 = 13 + 29 = 19 +23 이다.

 

이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력:

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 <= n <=1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력:

각 테스트 케이스에 대해서, n = a+b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자를 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong"을 출력한다.

풀이방법:

 여러 케이스에서 소수를 사용해야 하는데, 그 때마다 계산을 해야 하는 소수들을 구하면 너무 오랜 시간이 걸리기 때문에 최대 1,000,000를 넘지 않는다는 것을 이용해서 미리 소수들을 구하도록 한다. 

 따라서 소수를 효율적으로 구할 수 있는 방법 중 하나인 에라토스테네스의 체 방법을 사용해서 배열을 구한다. 그 뒤로는 입력으로 들어온 n 이하에 존재하는 소수들에 대해서 합을 구해본다. 이 때 n//2까지만 반복문을 돌아도 되는데, 그 뒤에 있는 값들은 이미 이 전에 검사했을 것이기 때문이다. (ex) 3+5=8, 5+3=8)

 그리고 두 수간의 차이가 가장 큰 경우를 출력해야 하므로 작은 수부터 즉 3부터 확인을 하며 처음으로 추측을 만족시킬 때가 간격이 가장 크기 때문에 break를 걸고 형식에 맞게 출력을 하도록 한다.

 원래는 추측이 틀렸을 때에는 지정된 문구를 출력해야 하지만, 이 추측은 실제로 존재하며 아직 반례를 찾지 못했기 때문에 틀린 경우가 없기 때문에 생략했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def isPrime(n):
    numbers=[1]*n
    
    for i in range(2,int(n**0.5)+1):
        if numbers[i]==1:
            for j in range(i+i,n,i):
                numbers[j]=0
    return numbers
    
numbers=isPrime(1000000)
 
while True:
    n=int(input())
    if n==0:
        break
    for i in range(3,n//2+1):
        if numbers[i] and numbers[n-i]:
            print("{} = {} + {}".format(n,i,n-i))
            break
cs

문제링크:

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

 

6588번: 골드바흐의 추측

문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모

www.acmicpc.net

 

'Algorithm > Python' 카테고리의 다른 글

[BOJ]2579. 계단 오르기  (0) 2020.03.10
[BOJ]13458. 시험 감독  (0) 2020.03.05
[Programmers]2019 Kakao.길 찾기 게임  (0) 2020.02.27
[BOJ]13305. 주유소  (0) 2020.02.25
[BOJ]2485. 가로수  (0) 2020.02.20

+ Recent posts