[ACM ] 題號136 找第一千五百個不含任何２，３，５以外質因數的數

[tw00088437 (喵貓 loves fish)]

題號：
136
http://tinyurl.com/yhnvpqp

遇到的問題：
雖然是算出來答案傳上去了，但是跑法很慢感覺沒效率（大概要跑幾萬ms)
不知道要怎麼改進（答案大約八億多）

ps: 請問d>>=1跑的會比d/=2快嗎?

有問題的code： (請善用置底文的標色功能)
#include<iostream>
using namespace std;
long long a,d;
int main()
{
    int num=1;

    for(a=2;a>=1;a++)
    {
    d=a;
    if(d%7==0||d%11==0||d%13==0||d%17==0||d%23==0||d%29==0)
    continue;
    while(d%2==0)
    d>>=1;
    while(d%3==0)
    d/=3;
    while(d%5==0)
    d/=5;
    if(d==1)
    num++; //found an ugly number!
    if(num==1500)
    break;


}
cout<<a;
system("pause");
 return 0;
}



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.104.73

※ 編輯: tw00088437      來自: 61.228.104.73        (11/04 22:15)
→ netsphere:printf("The 1500'th ugly number is 859963....
→ tw00088437:我是跑出來並且ＡＣ了啊=.=只是這樣感覺很沒意義
→ bleed1979:這題網路上的解答應該蠻多的
→ bleed1979:你可以反過來想，我只需要那些因數所組成的數
推 BSpowerx:有一作法是用2,3,5組合出約兩千組數字再排序
→ BSpowerx:不過不知道為何我怎麼做都錯orz
推 rifiz:至少可以一次跳二.....五的倍數也有規則....
→ rifiz:用樓上的方法應該就可以很快了.....我是這個方式AC的....
→ tw00088437:@@?
→ tw00088437:一次跳二?
推 walker2009:http://paste.plurk.com/show/59601/  分享我的作法
推 ssagit:http://www.tcgs.tc.edu.tw/~sagit/acm/view.php?id=136
→ ssagit:↑我也分享我的做法
→ tw00088437:謝謝: )