丑数

你的名字 2022-05-18 10:55 223阅读 0赞

求第1500个丑数。丑数是不能被2.3.5之外的其他素数整除的数，把丑数从小到大排起来，然后打印第1500个

先写一个典例，我写的，

//这是我写的，运行了大概15秒才出来结果，一开始以为由bug
    //debug了半小时   点了运行去了厕所 回来心都碎了  没有bug  只是算法问题 
    
    #include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cmath>
    #include<queue>
    #include<set>
    using namespace std;
    typedef long long ll;
    
    bool chou(signed long long x){
    	while(x%2==0) {x=x/2;}
    	while(x%3==0) { x=x/3;}
    	while(x%5==0)  {x= x/5;}
     	if(x==1) return true;
     	else return false;
    } 
    
    int main()
    {
    	priority_queue<ll> s;  set<ll> s2;
    	int num=1;
    	s.push(1);  s2.insert(1);
    	signed long long  i ;
    	for(i=1;;i++){
    		if(chou(i)&&!s2.count(i)) {
    			++num;
    			s2.insert(i);
    			s.push(i);
    		}
    		if(num==1500){
    			cout<<i<<endl;
    			break;
    		}
    	}
    	return 0;
    }

判断一个数是否为丑数的办法是，将这个数与2除，除到没有余数为止，再与3除，再与5除，   得到最后的数x，如果x=1，则为丑数，否则不为，本题计算量大，这个程序大概要15秒才能得出结果，明显不行

同时，由丑数的定义知，丑数是2，3，5的乘积，所以换一种思路

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cmath>
    #include<queue>
    #include<set>
    using namespace std;
    typedef long long ll;
    const int www[3]={2,3,5};
    typedef signed long long  ll; 
    
    
    int main()
    {
        priority_queue<ll.vector<ll>,greater<ll> >  pp;//得出一个从小到大的优先队列
        set<ll> s;//主要是得到一个判断不重复的方法
        ll x x1;
        pp.push(1);
        s.insert(1);
        for(int i=1;;i++){
            x=pp.top();
            pp.pop();
            if(i==1500){            //为什么是i=1500呢  推一下下面的for循环
                cout<<x<<endl;
                break;
            }
            for(int j=0;j<3;j++){    
                x1=x*www[j];        
                if(!s.count(x1)){        
                    s.insert(x1);
                    pp.push(x1);
                }
            }
        }
        return 0;
    }