CodeDrive

문제:

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력:

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력:

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

풀이방법:

 소수를 찾기 위한 에라토스테네스의 체와 그리고 한 소수로부터 다른 소수로 이동하기 위한 bfs를 사용하는 문제다.

우선 네 자리 수인 모든 소수를 찾기 위해서 에라토스테네스의 체를 사용한다. 에라토스테네스의 체를 1부터 10000까지 적용을 한 뒤에 filter를 사용해 1000보다 큰 수들만 남기도록 한다.

 네 자리 소수를 모두 구한 뒤에는 bfs를 사용해서 기준이 되는 숫자와 네 자리 소수를 모두 비교해서 하나만 다른 경우에만 새 queue에 넣는 방식으로 진행한다. 이 때 중복 방문을 피하기 위해서 visited 배열을 사용한다. 만약 목적지 소수를 발견하면 bfs를 종료하고 answer를 출력하며, 만약 모든 소수를 방문해도 도달하지 못했다면 Impossible을 출력하게 한다.

문제링크:

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

문제:

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

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

따라서 암호문이 크랙되지 않도록 하기 위해서는, 키 값이 적절히 큰 수들의 곱으로 이루어져 있는지를 확인해야 할 필요가 있다. 키 값 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

문제:

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

- 3 : 3 (한 가지)

- 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)

- 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 N이 주어진다. (1<=N<=4,000,000)

출력:

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

풀이방법:

투 포인터를 사용하는 슬라이딩 윈도우랑 소수를 구하는 알고리즘 중 하나인 에라토스테네스의 체를 사용하도록 한다.

우선 자연수 N 이하의 소수들을 에라토스테네스의 체를 이용해서 찾는다. 이 때, 소수인 값들만 남기기 위해서 set을 사용해서 소수가 아닌 것들을 제거하도록 했다.

이렇게 자연수 N 이하의 소수들이 담긴 배열을 구했으면, 이를 투 포인터를 이용한 슬라이딩 윈도우를 통해서 부분합을 구한다. 자연수 N보다 부분합이 작다면 end를 움직여서 부분합을 증가시키고, 부분합이 더 크다면 start를 줄여서 부분합을 증가시킨다.

N이 되는 경우는 count를 1씩 늘리며 부분합을 줄이도록 한다.

문제링크:

www.acmicpc.net/problem/1644

문제:

원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 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

문제:

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱 ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱 ㄴㄴ수가 몇 개 있는지 출력한다.

입력:

첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000.000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 [min,max]구간에 제곱ㄴㄴ 수가 몇 개인지 출력한다.

풀이방법:

어떤 수 X가 한 제곱수로 나누어지는지 확인하는 것 보다 제곱수가 나누어 떨어지게 만들 수 있는 수들을 지워나가는 것이 시간복잡도를 줄일 수 있다.(에라토스테네스의 체와 비슷)

문제링크:

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

문제:

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

 1. 2부터 N까지 모든 정수를 적는다.

 2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.

 3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.

 4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

입력:

첫째 줄에 N과 K가 주어진다. (1<=K<,max(2,K) < N <=1000)

출력:

첫째 줄에 K번째 지워진 수를 출력한다.

풀이방법:

우선 N까지 수가 있는 배열을 만들고 이를 에라토스테네스의 체 규칙에 따라서 하나씩 지워나간다. 이 때마다 하나씩 count를 늘려주면서 K번째가 되면 현재 지운 값을 출력하도록 한다.

문제링크:

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

문제:

출력:

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

풀이방법: