본문 바로가기

Programming Problems/Number theory

주어진 소수들이 소인수인 수 중 N 번째 작은 수를 찾아보자. ex)소수 : [2,3]N = 4표현 가능한 수 : [1,2,3,4,6,8,9,12...]답 : 4풀이 : 수열이 각 소수의 곱셈에 따라 반복적으로 구성된다. 즉,1 2 3 4 6 8 ..이 포함되면2 4 6 8 12 16 ..3 6 9 12 18 24 ..이 각각 포함된다.따라서 1을 처음에 놓고, 다음 후보군은2,3 중 하나다. 작은 2를 뺴고, 2의 다음 후보 4를 놓는다.계속 가장 작은 것 하나를 빼고 진행한다.이렇게 N 개 세면 된다.타임 ..
분수의 순환소수를 찾아보자. 분수가 주어지는 경우, 소숫점 표현법으로 바꿔보자. 순환소수가 있는 경우 괄호를 출력한다.ex)1/3 = 0.(3)2/4 = 0.5(0)22/7 = 3.(142857)솔루션:분모를 소인수분해해서 2와 5로만 구성되 있으면 그냥 나눈걸 출력한다. 끝에 (0)을 붙인다.아니면 아래의 알고리즘을 쓴다.정수로 나눈 값이 0이면 분자에 10을 곱한다. 정수로 나눈 값이 다음 자릿수다.0이 아니면 그걸 그냥 그대로 붙이고 넘어간다.지금까지 나온 소숫점 아래 숫..
N 보다 작으면서 3 또는 5의 배수인 숫자들의 합 구하기 처음에는 3또는 5만 소인수로 갖는 것들의 합 구하기로 생각해서, 3의 거듭제곱 중 가장 작으면서 큰거 i, 5의 거듭제곱 중 가장 작으면서 큰거 j 라고 하면(i,j) 2중 for 루프의 모든 숫자들 중 N 보다 작은 것들을 전부 더해나갈 생각이었다. 갯수는 log^2N 이고 각각에 대해 합을 구하는건 단계별로 3씩 곱해나가는 셈이니까 1이 걸려서 총 시간 복잡도는 O(log^2N) 쯤 되겠다.---근데 이 문제는 "3 또는 5의 배수" 이기 때문..