Armstrong.cpp

有人要的阿姆斯壯數


g++ -pipe -O -o p2 p2.cpp && time p2

find Armstrong number from: 1

find Armstrong number to: 100000000

1 is Armstrong number.

2 is Armstrong number.

3 is Armstrong number.

4 is Armstrong number.

5 is Armstrong number.

6 is Armstrong number.

7 is Armstrong number.

8 is Armstrong number.

9 is Armstrong number.

153 is Armstrong number.

370 is Armstrong number.

371 is Armstrong number.

407 is Armstrong number.

1634 is Armstrong number.

8208 is Armstrong number.

9474 is Armstrong number.

54748 is Armstrong number.

92727 is Armstrong number.

93084 is Armstrong number.

548834 is Armstrong number.

1741725 is Armstrong number.

4210818 is Armstrong number.

9800817 is Armstrong number.

9926315 is Armstrong number.

24678050 is Armstrong number.

24678051 is Armstrong number.

88593477 is Armstrong number.

30.028u 0.002s 0:38.23 78.5%    53+1924k 0+0io 0pf+0w

---

// 2007/5/18 1:5:20-1:15:4,2007/5/22 17:17:41-17:38:2

//g++ -pipe -O -o p2 p2.cpp && time p2



#include <iostream>



long long unsigned int digit_power(const unsigned long int& num, const unsigned int& pow){

 static long long unsigned int p[12][10]; // [power][num]

 if(num<0||num>9)return NULL;

 if(num==0)return 0;

 if(num==1)return 1;

 if(!p[pow][num]){

  p[pow][num]=1;

  for(int i=0;i<pow;i++)p[pow][num]*=num;

 }

 return p[pow][num];

}



int main(void){

 long unsigned int from,to,digit_number=10;

 unsigned int digit=1;

 std::cout<<"find Armstrong number from: ";

 std::cin>>from;

 std::cout<<"find Armstrong number to: ";

 std::cin>>to;



 long long unsigned int n,s;

 for(long unsigned int i=from,n,s;i<=to;i++){

  while(digit_number<i)digit_number*=10,digit++; // 確定位數, 10^digit=digit_number

  n=i,s=0;

  while(n)

   s+=digit_power(n%10,digit),n/=10;

  if(s==i)std::cout<<i<<" is Armstrong number."<<std::endl;

 }



 return 0;

}

---

啊…好像不需要那麼隆重…下面就可以了。

// 2007/5/18 1:5:20-1:15:4,2007/5/22 17:17:41-18:1:18

//g++ -pipe -O -o p2 p2.cpp && time p2



#include <iostream>



unsigned int digit_power(const unsigned int& num, const unsigned int& pow){

 static unsigned int p[12][10]; // [power][num]

 if(num<0||num>9)return NULL;

 if(num==0)return 0;

 if(num==1)return 1;

 if(!p[pow][num]){

  p[pow][num]=1;

  for(int i=0;i<pow;i++)p[pow][num]*=num;

 }

 return p[pow][num];

}



int main(void){

 unsigned int from,to,digit_number=10;

 unsigned int digit=1;

 std::cout<<"find Armstrong number from: ";

 std::cin>>from;

 std::cout<<"find Armstrong number to: ";

 std::cin>>to;



 unsigned int n,s;

 for(unsigned int i=from,n,s;i<=to;i++){

  while(digit_number<i)digit_number*=10,digit++; // 確定位數, 10^digit=digit_number

  n=i,s=0;

  while(n)

   s+=digit_power(n%10,digit),n/=10;

  if(s==i)std::cout<<i<<" is Armstrong number."<<std::endl;

 }



 return 0;

}

不過速度差不多。

g++ -pipe -O -o p2 p2.cpp && time p2

find Armstrong number from: 1

find Armstrong number to: 100000000

1 is Armstrong number.

2 is Armstrong number.

3 is Armstrong number.

4 is Armstrong number.

5 is Armstrong number.

6 is Armstrong number.

7 is Armstrong number.

8 is Armstrong number.

9 is Armstrong number.

153 is Armstrong number.

370 is Armstrong number.

371 is Armstrong number.

407 is Armstrong number.

1634 is Armstrong number.

8208 is Armstrong number.

9474 is Armstrong number.

54748 is Armstrong number.

92727 is Armstrong number.

93084 is Armstrong number.

548834 is Armstrong number.

1741725 is Armstrong number.

4210818 is Armstrong number.

9800817 is Armstrong number.

9926315 is Armstrong number.

24678050 is Armstrong number.

24678051 is Armstrong number.

88593477 is Armstrong number.

28.928u 0.002s 0:30.35 95.2%    53+1922k 0+0io 0pf+0w

---

倒是digit_power改inline就有感覺了。

終極版…在2.80GHz的機器上跑這樣…

g++ -pipe -O -o p2 p2.cpp && time p2

find Armstrong number from: 1

find Armstrong number to: 100000000

1 is Armstrong number.

2 is Armstrong number.

3 is Armstrong number.

4 is Armstrong number.

5 is Armstrong number.

6 is Armstrong number.

7 is Armstrong number.

8 is Armstrong number.

9 is Armstrong number.

153 is Armstrong number.

370 is Armstrong number.

371 is Armstrong number.

407 is Armstrong number.

1634 is Armstrong number.

8208 is Armstrong number.

9474 is Armstrong number.

54748 is Armstrong number.

92727 is Armstrong number.

93084 is Armstrong number.

548834 is Armstrong number.

1741725 is Armstrong number.

4210818 is Armstrong number.

9800817 is Armstrong number.

9926315 is Armstrong number.

24678050 is Armstrong number.

24678051 is Armstrong number.

88593477 is Armstrong number.

22.182u 0.002s 0:23.42 94.7%    53+1922k 0+0io 0pf+0w



雖然還有進步空間，不過…其他，不想改了。

// 2007/5/18 1:5:20-1:15:4,2007/5/22 17:17:41-18:1:18

//g++ -pipe -O -o p2 p2.cpp && time p2



#include <iostream>

const int debug=0;



inline unsigned int digit_power(const unsigned int& num, const unsigned int& pow){

 static unsigned int p[12][10]; // [power][num]

 //if(num<0||num>9)return NULL; // error!

 if(num<2)return num;

 if(!p[pow][num]){

  if(debug)std::cout<<"計算 "<<num<<" ^ "<<pow<<std::endl;

  p[pow][num]=1;

  for(int i=0;i<pow;i++)p[pow][num]*=num;

 }

 return p[pow][num];

}



int main(void){

 unsigned int from,to,digit_number=10;

 unsigned int digit=1;

 std::cout<<"find Armstrong number from: ";

 std::cin>>from;

 std::cout<<"find Armstrong number to: ";

 std::cin>>to;



 unsigned int n,s;

 for(unsigned int i=from,n,s;i<=to;i++){

  if(debug&&i%10000==0)std::cout<<i<<"\r";

  while(digit_number<i)digit_number*=10,digit++; // 確定位數, 10^digit=digit_number

  n=i,s=0;

  while(n)

   s+=digit_power(n%10,digit),n/=10;

  if(s==i)std::cout<<i<<" is Armstrong number."<<std::endl;

 }



 return 0;

}

---

好吧，我還是手癢。

實際CPU time十一秒，接著還要再減，就要更深入分析了。

// 2007/5/18 1:5:20-1:15:4,2007/5/22 17:17:41-18:1:18,20:55:49

//g++ -pipe -O -o p2 p2.cpp && time p2



#include <iostream>

const int debug=0;



inline unsigned int digit_power(const unsigned int& num, const unsigned int& pow){

 static unsigned int p[12][10]; // [power][num]

 if(debug)if(num<0||num>9)return NULL; // error!

 if(num<2)return num;

 if(!p[pow][num]){

  if(debug)std::cout<<"計算 "<<num<<" ^ "<<pow<<std::endl;

  p[pow][num]=1;

  for(int i=0;i<pow;i++)p[pow][num]*=num;

 }

 return p[pow][num];

}



int main(void){

 unsigned int from,to,digit_number=10;

 unsigned int digit=1;

 std::cout<<"find Armstrong number from: ";

 std::cin>>from;

 std::cout<<"find Armstrong number to: ";

 std::cin>>to;



 unsigned int n,s,count=0,max_delta=9;

 for(unsigned int i=from,n,s;i<=to;){

  if(debug&&i%10000==0)std::cout<<i<<"\r";

  while(digit_number<i){

   digit_number*=10,digit++; // 確定位數, 10^digit=digit_number

   max_delta=digit_power(9,digit)-9;

  }

  n=i,s=0;

  while(n)

   s+=digit_power(n%10,digit),n/=10;

  if(s==i)std::cout<<++count<<": "<<i<<" is Armstrong number."<<std::endl;

  i+= (i%10==0&&(s>i||i-s>max_delta))?10:1; // 在個位數為零時偵測若s>i或i-s差距大於max_delta，則個位數一直增到九也不會是Armstrong number。

 }



 return 0;

}

g++ -pipe -O -o p2 p2.cpp && time p2

find Armstrong number from: 1

find Armstrong number to: 100000000

1: 1 is Armstrong number.

2: 2 is Armstrong number.

3: 3 is Armstrong number.

4: 4 is Armstrong number.

5: 5 is Armstrong number.

6: 6 is Armstrong number.

7: 7 is Armstrong number.

8: 8 is Armstrong number.

9: 9 is Armstrong number.

10: 153 is Armstrong number.

11: 370 is Armstrong number.

12: 371 is Armstrong number.

13: 407 is Armstrong number.

14: 1634 is Armstrong number.

15: 8208 is Armstrong number.

16: 9474 is Armstrong number.

17: 54748 is Armstrong number.

18: 92727 is Armstrong number.

19: 93084 is Armstrong number.

20: 548834 is Armstrong number.

21: 1741725 is Armstrong number.

22: 4210818 is Armstrong number.

23: 9800817 is Armstrong number.

24: 9926315 is Armstrong number.

25: 24678050 is Armstrong number.

26: 24678051 is Armstrong number.

27: 88593477 is Armstrong number.

11.590u 0.003s 0:18.11 63.9%    53+1922k 0+0io 0pf+0w