c++ - 找出1到10,000,000之间不是丑数的数

Question

我在尝试找出不难看的数字时遇到了一些问题。 丑数是指质因数只有 2、3 或 5 的数。那么非丑数又如何呢？ 我试图找出 1 到 100,000,000 之间不丑陋的数字。我的程序可以解决问题，但似乎有点慢。我怎样才能让它更快？ 这是代码:

#include <iostream>
#include <queue>
using namespace std;
typedef pair<unsigned long,int> node_type;
main()
{
    //generates 1500 ugly numbers into result[];
    unsigned long result[1500];
    priority_queue<node_type,vector<node_type>,greater<node_type> > Q;
    Q.push(node_type(1,2));
    for(int i=0;i<1500;i++)
    {
        node_type node = Q.top();
        Q.pop();
    switch(node.second)
    {
        case 2:Q.push(make_pair(node.first*2,2));
        case 3:Q.push(make_pair(node.first*3,3));
        case 5:Q.push(make_pair(node.first*5,5)); 
    }
    result[i]=node.first;
}
/*****************************************************
//Here is the approach I used:
//The initial value of the integer k is 1;
//and will increase by 1 every time 
//k will be checked if it's a ugly number,if not increase by 1,keep doing
//this till k is not a ugly number,then count how much ugly number(we may 
//call it n) is less the the
//current value of k.The result of (k-n) is the order number of this (k)　not ugly
//for example:the 1st not ugly number is 7.
// there are 6 ugly number less than 7,which are 1 2 3 4 5 6,
// k=1-->k==2-->.....k=7, k-n=7-6=1,so 7 is the 1st not ugly number
***************************************************************/
int T;  // The amount of cases
cin>>T;
while(T--)
{
    int n;
    int k=0,i=0,count=0;
    cin>>n;

    while(n)
    {
        if((k+1)==result[i]) {k++;i++;count++;}
        else 
        {
            k++;
            if(k-count==n) {cout<<k<<endl;break;}
        }
    }
}}

最大的问题是它似乎不够快!你能告诉我如何让它更快吗？或者有其他方法可以解决这个问题？

Answer 1

好吧，我会咬人的。根据这个定义，测试一个数字是否丑陋，在计算上实际上相当简单。暴力测试 1 亿个数字

#include <iostream>

bool is_ugly(unsigned n) {
  while(n % 5 == 0) n /= 5;
  while(n % 3 == 0) n /= 3;
  while(n % 2 == 0) n /= 2;

  return n == 1;
}

int main() {
  unsigned counter = 0;
  for(unsigned i = 1; i <= 100000000; ++i) {
    if(!is_ugly(i)) {
      ++counter;
    }
  }

  std::cout << counter << std::endl;
}

在我的基准测试中只需要半秒多一点¹，这是非常可行的。当然，打印它们需要更长的时间，因为在 100000000 以下有 99998895 个非难看的数字，您的终端必须渲染它们。甚至重定向到 /dev/null (将渲染排除在等式之外)这里打印需要 6 秒(比检查长约 10 倍)，使用 libstdc++ 和 gcc 4.9 和 -O2 .如果你要生成所有非丑陋的数字，这并不容易克服，因为瓶颈不是你可以摆脱的东西。

另一方面，如果您的目标是生成所有低于阈值的丑陋数字(或计算非丑陋数字，这与计算丑陋数字并从阈值中减去数字是一回事)测试所有非丑陋的数字和丑陋的数字相差甚远。更好的方法是只生成丑陋的数字，因为它们很少。使用递归最容易做到这一点:

#include <iostream>
#include <set>      // could also use an unordered_set, except that it turns
                    // out to be a pessimization

void generate_uglies(unsigned n, std::set<unsigned> &num, unsigned threshold) {
  // Abort recursion if we break the upper limit or find a number
  // that was already tested
  if(n <= threshold && num.find(n) == num.end()) {
    // Remember this ugly number
    num.insert(n);

    // Since n is an ugly number, these three are also ugly numbers.
    generate_uglies(n * 2, num, threshold);
    generate_uglies(n * 3, num, threshold);
    generate_uglies(n * 5, num, threshold);
  }
}

int main() {
  std::set<unsigned> num;

  generate_uglies(1, num, 100000000);

  std::cout << num.size() << std::endl;
}

这报告回来了，嗯...

$ time ./a.out 
1105

real    0m0.001s
user    0m0.000s
sys     0m0.000s

您可以使用它，希望 num.find(n) == num.end()是比 is_ugly(n) 更快的非丑陋测试(使用之前的 is_ugly 函数)，但在我的基准测试中差异可以忽略不计，并且使用 std::unordered_set实际上慢 2-3 倍。

附录:可以节省一些时间的是将丑陋的数字生成为 std::vector<bool>像这样有 1 亿个元素:

// num is to have the wanted size in advance and be full of false
void generate_uglies(unsigned n, std::vector<bool> &num) {
  if(n < num.size() && !num[n]) {
    num[n] = true;
    generate_uglies(n * 2, num);
    generate_uglies(n * 3, num);
    generate_uglies(n * 5, num);
  }
}

并使用 !num[i] 测试非丑陋数字之后。 !num[i]测试比 is_ugly 快得多函数(对于低于 1 亿的值，平均乘以 ~5)¹。出于上述原因，如果您要打印它们，这并不重要，但在不同的上下文中，它可能会产生明显的差异。请注意，此表需要 12.5 MB RAM。

¹ 你的里程数会不同，因为你的机器不是我的。我使用的是 1.5 岁的 i7。