CodeDrive

문제:

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력:

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력:

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

풀이방법:

 보통 일반적인 소수 문제의 경우에는 에라토스테네스의 체를 사용해서 소수인 수들을 모두 찾고 하는 것이 빠른 경우가 많으나, 이 문제의 경우에는 N = 8 인 경우에 수가 엄청 커지게 되고, 시간이 오래 걸리게 된다.

 따라서 이 문제의 경우에는 dfs를 사용해서 한자리씩 붙여 나가면서 소수를 판정하는 방식을 사용하도록 한다. 문제의 특징으로 인해 75가 소수가 아니므로, 그 뒤는 판정할 필요가 없기 때문이다. dfs의 종료 조건은 숫자의 길이가 N이 될 때까지 진행한다.

문제링크:

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

문제:

암호화 방식 중에는 소수를 이용하는 것들이 많다. 보통은 매우 큰 두 개의 소수를 선택하고, 두 소수를 곱한 값을 암호화에서의 키로 사용하고는 한다. 이러한 방법이 좋은 이유는 일반적으로 매우 큰 수를 소인수분해 하는 것이 어렵기 때문이다.

소수를 택할 때 큰 수를 택하면, 이 둘을 곱해서 얻어지는 키 값도 커지게 된다. 하지만 그 반대는 성립하지 않을 수도 있다. 즉, 키 값이 매우 큰 경우에도 이를 소인수분해 하는 것은 쉬울 수도 있다.

따라서 암호문이 크랙되지 않도록 하기 위해서는, 키 값이 적절히 큰 수들의 곱으로 이루어져 있는지를 확인해야 할 필요가 있다. 키 값 K(4≤K≤10^100)와 정수 L(2≤L≤1,000,000)이 주어졌을 때, K를 인수분해 했을 때, 항상 L 이상의 값으로만 이루어져 있는지를 확인하고 싶다. 물론 인수분해 할 때 1로 나누는 경우는 고려하지 않는다.

예를 들어 K=143인 경우, 이는 11과 13의 곱으로 이루어져 있다. 즉, 이를 인수분해 하는 방법은 11×13, 143의 두 가지 경우뿐이다. 따라서 L이 11일 경우에는 인수분해 했을 때 나온 수들이 모두 L 이상이므로 좋은 경우지만, L이 12이상일 경우에는 좋은 암호가 아니다.

K와 L이 주어졌을 때, 좋은 암호인지 판단하는 프로그램을 작성하시오.

입력:

첫째 줄에 두 정수 K, L이 주어진다.

출력:

좋은 암호인 경우에는 GOOD을 출력한다. 나쁜 암호일 경우에는 BAD를 출력하고, K의 가장 작은 (1 아닌) 인수를 출력한다.

풀이방법:

K가 L 미만의 소수로 나눠지는지 확인하면 되는 문제다. 따라서 에라토스테네스의 체를 사용해서 L 미만의 소수를 찾은 뒤에 그 소수들로 K로 나눠본다.

나눠지면 BAD와 함께 그 수를 출력하고, 나눠지지 않는다면 GOOD을 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/2061

문제:

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

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

편의상 두 사람의 끈을 이어붙일 때와 나눌 때 손실되는 끈의 길이는 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를 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/15711

문제:

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다.

출력:

첫째 줄에 조건을 만족하는 수를 출력한다.

풀이방법:

 소수를 판정하는 알고리즘 중 에라토느테네스의 체와 팰린드롬 알고리즘을 함께 사용하는 알고리즘이다. N으로 들어올 수 있는 가장 큰 숫자인 1,000,000에 해당하는 답은 1003001이라는 사실을 사용해서 그 만큼을 sosu 리스트를 초기화했다. (혹은 넉넉하게 큰 길이로 초기화해도 된다.) 이 sosu 리스트를 에라토스테네스의 체를 사용해서 소수만 남겨둔다.

 이후 while 반복문을 통해서 sosu이면서 팰린드롬인 경우에 그 숫자를 출력하고 break를 통해 정지시키면 된다.

문제링크:

www.acmicpc.net/problem/1747

문제:

원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 만들었다.

개인마다 어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키로 두었다. 이렇게 해 두면 두 소수 p,q를 알지 못하는 이상, 비밀 키를 알 수 없다는 장점을 가지고 있다.

하지만 원룡이는 한 가지 사실을 잊고 말았다. 최근 컴퓨터 기술이 발달함에 따라, 소수가 작은 경우에는 컴퓨터로 모든 경우의 수를 돌려보아 비밀 키를 쉽게 알 수 있다는 것이다.

원룡이는 주성조교님께 비밀 키를 제출하려던 바로 직전에 이 사실을 알아냈다. 그래서 두 소수 p,q 중 하나라도 K보다 작은 암호는 좋지 않은 암호로 간주하여 제출하지 않기로 하였다. 이것을 손으로 직접 구해보는 일은 매우 힘들 것이다. 당신은 원룡이를 도와 두 소수의 곱으로 이루어진 암호와 K가 주어져 있을 때, 그 암호가 좋은 암호인지 좋지 않은 암호인지 구하는 프로그램을 작성하어야 한다.

입력:

암호 P(4<=P<=10^100)와 K (2<=K<=10^6)이 주어진다.

출력:

만약에 그 암호가 좋은 암호이면 첫째 줄에 GOOD을 출력하고, 만약에 좋지 않은 암호이면 BAD와 소수 r을 공백으로 구분하여 출력하는데 r은 암호를 이루는 두 소수 중 작은 소수를 의미한다.

풀이방법:

 n보다 작은 소수를 찾아서 이를 P에다가 나눠본다. 이 때 나눠진다면 좋지 못한 암호이기 때문에 BAD와 그 수를 출력하면 된다. 이 때, K가 최대 10^6까지 가능하기 때문에 소수를 구하는 최적의 알고리즘이 필요할 것이라고 생각했고, 가장 효율적인 소수 알고리즘 중 하나인 에라토스테네스의 체를 사용했다.

 길이가 K이고 값들이 1인 배열을 만들었고, 에라토스테네스의 체를 사용해서 소수를 구했다. 에라토스테네스의 체를 간단히 설명하면 한 소수 n의 배수들은 이 소수 n로 다 나눠질 것이기 때문에 소수가 아니라는 것이다.

 따라서 해당하는 인덱스의 배열 값이 1이고, 소수라면 그 배수들의 배열값들을 다 0으로 만들어준다. 그리고 추후 탐색을 편하게 하기 위해서 인덱스를 answer 리스트에 담아둔다.

 이렇게 하면 answer에는 소수만 남게 되고, 이를 P에다가 나눠보면서 좋은 암호인지 판단한다.

문제링크:

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

문제:

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를 걸고 형식에 맞게 출력을 하도록 한다.

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

문제링크:

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

문제:

출력:

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

풀이방법:

문제:

입력:

출력:

풀이 방법:

문제:

풀이 방법:

하지만 이 방법은 효율적이지 못한 방법이라 큰 수의 경우에는 통과를 하지 못한다.

 그 이유는 2부터 x-1까지 검사하기 때문에 엄청 큰 소수 인 경우 x-1까지 반복해야하기 때문이다.

하지만 수학적으로 생각해보면 만약 어떤 수의 약수가 존재한다면 x-1까지 검사할 필요 없이 sqrt(x)까지만 검사를 해보아도 충분하다는 것을 알 수 있다.

따라서 위 코드를 다음과 같이 수정을 하였다.

math에 있는 루트 함수인 sqrt와 올림 함수인 ceil을 사용해서 범위를 잡아 주었다. 그러면 다음과 같이 큰 수의 경우에도 통과를 하는 것을 알 수 있다.

 하지만 이 방법이 소수를 판별하는 문제에서 최적의 효율을 나타내지는 않는다. 소수를 판별하는 문제에서 가장 효율이 좋은 코드는 '에라토스테네스의 체' 원리를 사용하는 것이다. 소수가 1과 자기 자신으로 나누어 지는 수라고 가정하면 소수가 아닌 수는 임의의 소수 하나로 나눌 수 있다는 말이 된다. 따라서 2부터 x-1까지 나누어보는 것이 아닌 소수 배열을 만들어서 임의의 소수로 나누어 지지 않는다면 소수가 된다는 것이다. 다음은 에라토스테네스의 체 원리를 이용해 작성한 코드다.

다음과 같이 더 빨리 통과함을 알 수 있다. 효율성 테스트에서는 더 빨리 통과한다는 것을 체감할 수 있다.