한강Slave II · 901726 · 19/09/15 19:39 · MS 2019

ㅋㅋㅋㅋㅋ

좋아요 0 답글 달기 신고
Holomorphic21 · 870073 · 19/09/15 20:54 · MS 2019

191543 맞나요?

좋아요 0 답글 달기 신고
헐랭퐁당 · 711166 · 19/09/15 20:55 · MS 2016

오 혹시 근거가 있나여??

좋아요 0 답글 달기 신고
Holomorphic21 · 870073 · 19/09/15 21:05 · MS 2019

저도 도저히 생각이 안나서, 직접 계량하는 프로그램을 만들어 보았습니다.

약수 개수가 6개이면, 서로 다른 소수 p, q에 대해

p^1 q^2
p^5

의 꼴로 나타낼 수 있습니다. 다음과 같은 계량 함수를 정의합니다 :

소수의 부분집합 X = { x : x^2 ≤ n}을 정의하고,

f(n) = Σ_{k ∈ X} π( n/k^2 ) + π( n^1/5 ) - π ( n^1/3)

(첫번째 식은 p^1 q^2꼴 다 더하는 것, 두번째 식은 p^5꼴 더하는 것, 세번째 식은 중복 제거)

그리고 정수 n을 입력하면 약수 개수가 6개인 n 이하의 자연수의 개수를 출력하는 프로그램을 작성합니다 :

#include
using namespace std;

int prime[1000000] = {0};
int pi[1000000];
int main(){
int n = 0, result = 0;
cin >> n;

prime[0] = prime[1] = 1;
for (int i = 2; i <= 1000; i++){
if(prime[i]) continue;
for (int j = i + i; j <= 1000000; j += i)
prime[j] = 1;
}

pi[0] = 0;
for (int i = 1; i <= 1000000; i++) {
pi[i] = pi[i - 1] + !prime[i];
}

for (int i = 1; i * i <= n; i++) {
if (prime[i]) continue;
result += pi[n / (i * i)];
}

int i = 1, j = 1;
for (; i * i * i * i * i <= n; i++);
for (; j * j * j <= n; j++);
result += pi[i - 1] - pi[j - 1];

cout << result << endl;
return 0;
}

그리고 이분법으로 찾으면 됩니다.

p.s. #include 뒤에 <> 쓰고 그 안에 iostream 넣어야 하는데, 오르비 댓글에서는 잘 안 먹네요 ㅋㅋㅋ

좋아요 0 답글 달기 신고
헐랭퐁당 · 711166 · 19/09/15 21:12 · MS 2016

정답 인정ㅋㅋㅋ

대단하시네여ㅋㅋㅋㅋ

좋아요 0 답글 달기 신고
Holomorphic21 · 870073 · 19/09/15 21:15 · MS 2019

ㅋㅋㅋㅋㅋ... 아직 검증은 어떻게 할지 모르겠지만

좋아요 0 답글 달기 신고
헐랭퐁당 · 711166 · 19/09/15 21:18 · MS 2016

저정도 코드면 정답찾기는 그냥 간단한 노가다니깐ㅋㅋ

좋아요 0 답글 달기 신고