2013年8月9日

UVa 11752 - The Super Powers

#include <cstdio>
#include <cmath>
#include <set>
using std::set;

typedef unsigned long long ULL;
const int MAX = (1 << 16);

inline ULL power(int n, int e) {
  ULL sum = 1;
  for (int i = 0; i < e; i++) {
    sum *= n;
  }
  return sum;
}

int main() {
  bool notPrime[64] = {};
  notPrime[0] = notPrime[1] = true;
  for (int i = 2; i < 64; i++) {
    if (!notPrime[i]) {
      for (int j = i + i; j < 64; j += i) {
        notPrime[j] = true;
      }
    }
  }
  int exp[100] = {}, L = 0;
  for (int i = 4; i < 64; i++) {
    if (notPrime[i]) {
      exp[L++] = i;
    }
  }
  set<ULL> all;
  all.insert(1);
  for (int i = 2; i < MAX; i++) {
    double limit = 64.0 / (log(i) / log(2));
    for (int j = 0; exp[j] < limit; j++) {
      all.insert(power(i, exp[j]));
    }
  }
  for (std::set<ULL>::iterator it = all.begin(); it != all.end(); it++) {
    printf("%llu\n", *it);
  }
  return 0;
}

沒有留言:

張貼留言