오일러 프로젝트라고... 프로그래밍 언어로 코딩해서 푸는 문제거든?..
문제는 짤방이구..
내가 어떻게 풀었냐면..
예를 들어 a= 2일때, b가 2에서 100까지 증가함에 따라 작은것부터 늘어놓으면
2^2 2^3 2^4 ........................ 2^100 이잖어..?
그리고 a=16 일때, b가 2에서 100까지 증가함에 따라 작은것부터 늘어놓으면
16^2 16^3 ......................... 16^100 까지 있을꺼잖아..
근데 16 = 2^4 이니까, 다시 쓰면
2^8 2^12 ........................ 2^400
이중에서, 2^8, 2^12 ... 2^100(=16^25) 까진 중복이니까 카운팅을 안하는거야..
일반화 시키면
어떤 자연수 a^b가 에서 자연수 a가 c의 n제곱일때, n*b <= 100 의 조건을 만족하면, 중복이란 소리니까 카운팅을 하지 않는다 (단, 2<= a, b <= 100)
근데 왜 숫자가 정답보다 많이 나올까...
내가 뭐 빼먹은거 있나?..ㅜㅜ 좀 도와줘..엉엉
// problem29.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//
#include "stdafx.h"
#include "time.h"
#include "math.h"
int squareN(int a, int factor); // factor 가 a 의 임의의수 n 제곱근인지 확인하는 함수. 제곱근이면, n 을 반환, 아니면 100보다 크수 반환.
int _tmain(int argc, _TCHAR* argv[])
{
double start, finish; //걍 시간잴때 쓰면 변후
start = clock(); //걍 시간 재는거
int arr_test[101] = {0,0}; // 1이면, 카운팅, 0이면 카운팅에서 제외. 이중 arr_test[0], arr_test[1] 은 사용하지 않음.
int answer = 0; // 답!!!!!
for(int a = 2; a <= 100; a++)
{
printf("%3d : ", a); // 실제 문제에서의 a
for(int b = 2; b <= 100; b++) // 실제 문제에서의 b
{
arr_test[b] = 1; // 일단 a^b 의 값이 유일하다고 가정하고, 1 대입
for(int factor = 2; factor*factor <= a; factor++) // 2이상, 루트a 이하의 자연수중에서 제곱근이 있는지 찾는 부분
{
if(squareN(a, factor) * b <= 100) // 만약 n 과 b의 곱이 100이하이면, 중복이니까 arr_test[b]에 0을 넣어, 중복효과 제거
{
arr_test[b] = 0;
}
}
printf("%d", arr_test[b]); // 1이면 중복 아님, 0이면 중복
answer = answer + arr_test[b]; // 1과 0을 계속 더해서 답을 구함.
}
}
printf("The answer is %d\\n", answer);
finish = clock(); // 걍시간구할때 쓰는거
printf("Time : %.3lf", (finish-start)/CLK_TCK); //걸린 시간 출력
getchar(); // 콘솔창 꺼지는거 방지
return 0;
}
int squareN(int a, int factor)
{
int n = 0; //n제곱 초기화 // 2부터 유효한 값임
int copy_a = a; //a 저장용
while(copy_a%factor == 0) // a를 factor 로 계속 나눠서 factor 가 a의 임의의 n 제곱근인지 확인. 여기서 n 도 구함.
{
copy_a = copy_a/factor;
n = n + 1;
}
if((n == 0) || (n == 1) || (copy_a != 1)) // 제곱근이 아닌경우, 100보다 큰 10000 반환.
{
return 10000;
}
return n; // 제곱근이면 n 을 반환
}
댓글 영역
획득법
① NFT 발행
작성한 게시물을 NFT로 발행하면 일주일 동안 사용할 수 있습니다. (최초 1회)
② NFT 구매
다른 이용자의 NFT를 구매하면 한 달 동안 사용할 수 있습니다. (구매 시마다 갱신)
사용법
디시콘에서지갑연결시 바로 사용 가능합니다.