素数与丑数

题目1：给出n中所有素数的个数。

：暴力解法

每个数i都判断其是否被前面2~i的数整除，如果是不是素数，全部都不能整除，为素数。

bool isPrime(int n)
{
    if(n<2) return false;
    for(int i=2;i<n;i++)
    {
        if(n%i==0) return false;
    }
    return true;
} 

解法2：建立一个bool数组，从2的倍数开始，如果为其倍数的数都不是素数，依次遍历到n.然后再遍历一遍bool数组，输出素数。

    int n;
    cin>>n;
    if(n<2) return 0;
    bool *nums=(bool *)malloc(sizeof(bool)*n);
    for(int i=2;i<n;i++)
    {
        if(!nums[i])
        {
            for(int j=2;j*i<n;j++)
                nums[j*i]=true;
        }
    }
    int count=0;
    for(int i=2;i<n;i++)
    {
        if(nums[i]==false)
            count++;
    }
    cout<<count<<endl;
    free(nums);

---

题目2：

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

解法1：暴力解法

bool isUgly(int number)
{
    while(number%2==0)
        number/=2;
    while(number%3==0)
        number/=3;
    while(number%5==0)
        number/=5;
    return (number==1)?true:false;
}

解法 2：

根据丑数的定义我们可以将丑数分成下列3个组：
（1）1*2，2*2，3*2，4*2....
（2）1*3，2*3，3*3，4*3….
（3）`1*5，2*5，3*5，4*5….

一个新的丑数可以看成一个旧的丑数乘以2，3，5（1除外）。那么如何维护丑数数列成为从小到大排序的顺序就成了本题的难点。

思路如下：

• 维护三个列表，分别是当前遍历的丑数num的2,3,5倍，三个列表内的数都是有序的。
• 每次三个列表分别获得第一个节点（列表最小节点），取得最小的数则为当前所需遍历的丑数。
• 删除当前丑数在指定列表的节点，计数值+1。

class Solution {
public:
    int nthUglyNumber(int n) {
        int count = 1;
        int num = 1;
        list<int> l2;
        list<int> l3;
        list<int> l5;

        while(count != n)
        {
            l2.push_back(2*num);
            l3.push_back(3*num);
            l5.push_back(5*num);

            int l2min = l2.front();
            int l3min = l3.front();
            int l5min = l5.front();

            int minNum = min(l2min, min(l3min, l5min));
            if(l2min == minNum) l2.pop_front();
            if(l3min == minNum) l3.pop_front();
            if(l5min == minNum) l5.pop_front();
            num = minNum;
            ++count;
        }
        return num;
    }
};

解法 3：

我们考虑用一个数组，数组存储的是当前的丑数，以后的每个丑数，都是用之前的数组的元素相乘的来的。接下来就是如何得到后面的丑数并保证它是有序的。可以想到，数组的第一个元素是1,1与2 3 5分别相乘，可以得到三个值，这三个值里面最小的，肯定就是下一个丑数的最大值，接着这个t2下标后移，继续比较，t3,t5同理。

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index<7) return index;
        vector<int> res(index);//辅助数组保存排序的丑数
        res[0]=1;//第一个丑数为1
        int t2=0,t3=0,t5=0,i;//t2为丑数为2的倍数中，目前已遍历的丑数的最大值的下标。。以此类推
        for(i=1;i<index;i++)
        {
            res[i]=min(res[t2]*2,min(res[t3]*3,res[t5]*5));//得出第i个丑数的值
            if(res[i]==res[t2]*2) ++t2;//更新t2,t3,t5值
            if(res[i]==res[t3]*3) ++t3;
            if(res[i]==res[t5]*5) ++t5;
        }
        return res[index-1];
    }
};