仅使用质数2、3和5生成序列，然后显示第n项(C++)

Question

我正在解决一个问题，要求使用质数2、3和5生成一个序列，然后显示序列中的第n个数字。所以，如果我要求程序显示第1000个数字，它应该显示它。

我不能使用数组或类似的东西，只能使用基本的判定和循环。

我开始研究它然后撞到了墙上。下面是我得到的信息：

#include <iostream>

using namespace std;
int main() {
    unsigned int n=23;
    for(int i=2; i<n; i++){
        if(i%2==0){
            cout<<i<<", ";
        }else if(i%3==0){
            cout<<i<<", ";
        }else if(i%5==0){
            cout<<i<<", ";
        }
    }

    return 0;
}

不幸的是，这些代码并不能完成所需的工作。它显示像14这样的数字，其中包括质数7....这些数字只能被3个指定的素数(2,3,5)整除。

我发现了一些我正在尝试理解的信息，但到目前为止还不确定如何实现它……也许使用了大量的for()循环？所以，似乎我必须使用2^n * 3^m * 5^k的概念，其中n+m+k>0。

我想我必须通过测试来运行一个数字，首先检查它是否能被2^1 * 3^0 *5^0完全整除，然后是2^0 * 3^1 * 5^0，然后是2^0 * 3^0 * 5^1，依此类推……只是不知道从哪里开始。

Answer 1

看看这个。

#include <iostream>
using namespace std;

int IsPrime(int var);
int CheckifPrimeGreaterThaFive(int Num);
int GetFactors(int Num)
{
    int i =0,j=0;
    for (i =2,j=0; i <= Num; i++)
    {
        if (Num%i == 0)
        {
           if (1 == CheckifPrimeGreaterThaFive(i))
           {
                 return 1;
              }
        }
    }
    return 0;
}

int CheckifPrimeGreaterThaFive(int Num)
{
   if ((Num != 2 && Num != 3 && Num != 5) && IsPrime(Num))
   {

           return 1;
   }

    return 0;
}

int IsPrime(int var)
{
    for (int i = 2; i <= var/2; i++)
    {
        if (var % i == 0)
           return 0;
    }
    return 1;
}


int main() {
    int n=98;
    int i, FactorsCount=0;

    for(i=2; i<n; i++)
    {
        if (0 == GetFactors(i))
        {  
           cout<<" "<<i;
        }   
    }
    return 0;
}

Answer 2

这是一个著名的问题，以Richard Hamming的名字命名为Hamming's problem，Dijkstra的著名著作《编程纪律》中对此进行了介绍。数学家称这些数为(如果包括1) 5 -光滑数，因为它们的素数分解只包含小于或等于5的素数。

您应该注意到的是，您可以从彼此生成数字。以下是思考这个问题的一种方式：

#include <set>
#include <iostream>

using namespace std;

int
main()
{
    const unsigned n = 23;

    set<unsigned> s;
    s.insert(2);
    s.insert(3);
    s.insert(5);

    for (unsigned i = 0; i < n; ++i)
    {
        // This returns the smallest element in the set.
        unsigned x = *s.begin();
        cout << x << '\n';

        // Erase the smallest element.
        s.erase(s.begin());

        // Insert the multiples of x.
        s.insert(2*x);
        s.insert(3*x);
        s.insert(5*x);
    }
}

这需要O(n log n)时间来打印n个数字。使用类似的算法，通过合并惰性流，可以在O(n)时间内完成。我的解决方案使用了boost::transform_iterator和boost::iterator_facade，所以我不建议初学者这样做。

Answer 3

这段代码可以做到这一点。将问题分解成更小的问题通常是一个好的计划。

int main() {
    unsigned int n=23;

    unsigned int counter=0;
    unsigned int answer;
    for ( answer = 2; counter < n; ++answer ) {
        if ( isNotDivisibleByAPrimeGreaterThan5( i ) {
           ++counter;
        }
    }
    cout << answer;
    return 0;
}

现在你只需要编写这个函数。

bool isNotDivisibleByAPrimeGreaterThan5( unsigned int i ) {
  // return true if i is not divisable by a prime greater than 5.
}