[백준] 1837. 암호제작
2020. 4. 20. 20:10
https://www.acmicpc.net/problem/1837
1837번: 암호제작
문제 원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 만들었다. 개인마다 어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키로 두었다. 이렇게 해 주면 두 소수 p,q를 알지 못하는 이상, 비밀 키를 알 수 없다는 장점을 가지고 있다. 하지만 원룡이는 한 가지 사실을 잊고 말았다. 최근 컴퓨터 기
www.acmicpc.net
소수와 수학 관련 문제였습니다.
1부터 K까지 의 소수들로 암호를 나누어 보면 됩니다.
주어진는 암호가 10의 100승 까지 이므로 문자열로 받아야 합니다.
* 문자열로 받은 암호를 소수로 나눌때
암호를 각 자리수 별로 나누었다가 합칠때, 자리수 별로 소수로 나누어 보면 됩니다.
소수를 구하는 알고리즘은 에라토스테네스의 체 알고리즘을 사용해야 시간초과에 안걸립니다.
소수를 구하는 알고리즘
소수 2를 제외한 자연수 중 나누어 떨어지는 수가 1과 자신뿐인 수 소수를 구하는 알고리즘 가장 기본적인 방법 정의를 그대로 구현한 것으로 2 부터 주어진 수 - 1 까지의 자연수로 계속 나누어 본다. O(n)의 시간복잡도를 가진다. 하지만, 숫자가 주어질 때 마다 판별해야한다. 메모이제이션 2 부터 n 사이의 소수로 나누었을 때 떨어지지 않으면 수수...
velog.io
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 4179. 불! (0) | 2020.04.22 |
|---|---|
| [백준] 5427. 불 (0) | 2020.04.21 |
| [백준] 5014. 스타트링크 (BFS) (0) | 2020.04.03 |
| [백준] 1748. 수 이어 쓰기 1 (0) | 2020.04.02 |
| [백준] 1024. 수열의 합 (0) | 2020.04.01 |