C++:完美數(Perfect Number)

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

我的Algorithm是和底下的網址一樣的(花了我兩個小時去想出來,結果網路上居然有.....),不過我不會證明,而這個網頁上有證明了這個Algorithm是對的 ^.^"

http://euler.tn.edu.tw/allno.htm


#include <iostream>
#include <cmath>

using namespace std;

bool isPrimes(unsigned long n);

int main(int argc, char *args[])
{
  bool isPrime;
  unsigned long input;
  input = atoi(args[1]);
  unsigned long num = 0;
  int p = 1;

  for(unsigned long n = 6; n <= input; n+= 2) {
  //找出小於n的數中,找出有可能成為Perfect number的最大值
    while(true) {
      if(pow(2, (double)p) - pow(2, (double)(p/2)) <= n)
      {
        p += 2;
      }
      else
      {
        p -= 2;
        break;
      }
  }

    num = pow(2, (double)p) - pow(2, (double)(p/2));
    if(n == num) { //若找出的 Perfect number 等於 n,再判斷
      isPrime = isPrimes(pow(2, (double)((p+1)/2)) - 1);
    if(isPrime)
      cout << num << " is Perfect Number." << endl;
    }
  }
  return 0;
}

bool isPrimes(unsigned long n)
{
  for(int i = 3; i*i <= n; i+= 2)
    if(n % i == 0)
    return false;
  return true;
}


沒有留言: