c++ - 没有大于 k 的质因数的正数

Question

我试图创建一个函数，它接受两个变量 n 和 k。

该函数返回质因数均小于或等于k 的正整数的个数。正整数的个数受 n 限制，它是最大的正整数。

例如，如果k = 4 和n = 10；具有所有小于或等于 4 的质因数的正整数是 1、2、3、4、6、8、9、12...(由于某种原因 1 总是部分，即使它不是质数)但是因为 n 为 10、12 和更高的数字将被忽略。

因此该函数将返回 7。我编写的代码适用于较小的 n 值，而它只是继续运行较大的值。

如何优化这段代码？我是否应该从头开始并提出更好的算法？

int generalisedHammingNumbers(int n, int k)
{
    vector<int>store;
    vector<int>each_prime = {};

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            if (i%j == 0 && is_prime(j))
            {
                each_prime.push_back(j);   //temporary vector of prime factors for each integer(i) 
            }
        }
        for (int m = 0; m<each_prime.size(); ++m)
        {
            while(each_prime[m] <= k && m<each_prime.size()-1)  //search for prime factor greater than k
            {
                ++m;
            }
            if (each_prime[m] > k);  //do nothing for prime factor greater than k
            else store.push_back(i);  //if no prime factor greater than k, i is valid, store i
        }
        each_prime = {};
    }

    return (store.size()+1);
}

bool is_prime(int x)
{
    vector<int>test;
    if (x != 1)
    {
        for (int i = 2; i < x; ++i)
        {
            if (x%i == 0)test.push_back(i);
        }
        if (test.size() == 0)return true;
        else return false;

    }
    return false;

}


int main() 
{
    long n;
    int k;
    cin >> n >> k;
    long result = generalisedHammingNumbers(n, k);
    cout << result << endl;


}

Answer 1

Should I start from scratch and come up with a better algorithm?

是的……我想是的。

在我看来，这是埃拉托色尼筛法的工作。

所以我建议

1) 创建一个 std::vector<bool>通过 Eratosthenes 检测到 n 的素数

2) 删除从 k+1 开始的素数，以及它们的倍数，来自你的号码池(另一个 std::vector<bool> )

3) 计算true池 vector 中的剩余值

下面是一个完整的工作示例

#include <vector>
#include <iostream>
#include <algorithm>

std::size_t foo (std::size_t n, std::size_t k)
 {
   std::vector<bool> primes(n+1U, true);
   std::vector<bool> pool(n+1U, true);

   std::size_t const sqrtOfN = std::sqrt(n);

   // first remove the not primes from primes list (Sieve of Eratosthenes)
   for ( auto i = 2U ; i <= sqrtOfN ; ++i )
      if ( primes[i] )
         for ( auto j = i << 1 ; j <= n ; j += i )
            primes[j] = false;

   // then remove from pool primes, bigger than k, and multiples
   for ( auto i = k+1U ; i <= n ; ++i )
      if ( primes[i] )
         for ( auto j = i ; j <= n ; j += i )
            pool[j] = false;

   // last count the true value in pool (excluding the zero)
   return std::count(pool.begin()+1U, pool.end(), true);
 }

int main ()
 {
   std::cout << foo(10U, 4U) << std::endl;
 }