오일러 프로젝트라고... 프로그래밍 언어로 코딩해서 푸는 문제거든?..

문제는 짤방이구..

내가 어떻게 풀었냐면..

예를 들어 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 을 반환
}