找到数字的主要因素的更好方法

Question

我正在解决一个问题，您得到了一些测试用例。对于每种情况，您都会得到一个范围（从 x 到 y，包括端值）。在这个范围内我必须数出所有质因数之和恰好为K的数。

例如：

5 15 2

我们知道有 5 个数字恰好有 2 个质因数（6、10、12、14 和 15）。

现在我的代码可以完美运行，但是太慢了。我一直在寻找一种通过 C++ 生成素数的更快方法。这是我的代码。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <math.h>
#include <string>
#include <sstream>
#include <vector>
#include <iomanip>
#include <deque>
#include <queue>

#define Fill(s, v) memset(s, v, sizeof(s))
#define skipChar() (scanf("%c", &useless));
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar());x=(x<<3)+(x<<1)+_-'0');}while(0)
#define rekt return false;
#define notrekt return true;
char _, useless;

using namespace std;
typedef pair <int, int> intpair;
vector<int> primes;

void sieve(int n){
bool *prime = new bool[n +1];
fill(prime, prime + n+1, true);
prime[0] = false;
prime[1] = false;
int m = sqrt(n);
for(int i = 2; i <= m; i++)
    if(prime[i])
        for(int k = i*i; k <= n; k+=i){
            prime[k] = false;
            if(prime[k])primes.push_back(k);
        }
for(int i = 0; i <n; i++){
    if(prime[i])
        primes.push_back(i);
     }
}

int main()
{
int t;
int c = 1;
scan(t);
sieve(1000);
while(t--){
    int a, b, k;
    scan(a);
    scan(b);
    scan(k);
    int realCount = 0;
    for(int i = a; i <= b; i++){
        int count = 0;
        for(int j = 0; j < primes.size(); j++){
            if(i % primes[j] == 0){
                    count++;
            }
        }
        if(count == k)realCount++;
    }
    cout << "Case #"<< c << ": "<< realCount <<endl;
    c++;
    }
}

感谢您的帮助！

感谢大家的贡献！这是快速优化的代码！

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <math.h>
#include <string>
#include <sstream>
#include <vector>
#include <iomanip>
#include <deque>
#include <queue>

#define F(a, s, val) fill(a, a + s, val);
#define skipChar() (scanf("%c", &useless));
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=_=getchar());x=(x<<3)+(x<<1)+_-'0');}while(0)
#define rekt return false;
#define notrekt return true;
char _, useless;

using namespace std;
typedef pair <int, int> intpair;

int *omega = new int[10000001];

void omg(){
    for(int i = 2; i < 10000000; i++)
            if(omega[i] == 0)
                    for(int j = i; j < 10000001; j+=i)
                            omega[j]++;
}

int main(){
    int t;
    int c = 1;
    F(omega, 10000001, 0);
    omg();
    scan(t);
    while(t--){
        int a, b, k;
        scan(a);
        scan(b);
        scan(k);
        int cc = 0;
        for(int i = a; i <= b; i++)
                    if(omega[i] == k)
                            cc++;
        printf("Case #%i: %i\n", c, cc);
        c++;
        }
    }

Answer 1

您的筛选功能可能会像这样优化。

vector<int> siev(int max) {
    vector<int> ret;
    bool isPrime[max];

    for(int i=2; i<max; i++) isPrime[i]=true; // reset all bits

    for(int i=2; i<max; i++) {
        if(isPrime[i]) {
            ret.push_back(i);
            for(int j=i*i; j<max; j+=i) {
                isPrime[j]=false;
            }
        }
    }

    return ret;
}

Answer 2

您使用埃拉托色尼筛法正确地预先计算了所需范围内的素数，这很好。但是，您想知道的是范围内每个数字的不同质因数的数量，而不是它是质数还是合数。

那个计算也可以通过筛分来完成。不要保留一个布尔数组，而是保留一个整数数组来计算不同素数的数量，并为在筛选过程中找到的每个素数增加它。

筛分是这样的；我们称数组为 omega 因为那是数论学家给函数的名称 returns 一个数的不同因子的数量：

omega := makeArray(2..limit, 0)

for i from 2 to limit
    if omega[i] == 0
        for j from i to limit step i
            omega[j] := omega[j] + 1

omega数组的前几个元素是1,1,1,1,2,1,1,1,2,1,2,1,2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2‌ , 2, 1, 3 (A001221).

一旦您拥有 omega，您就可以将其用于所有查询：

function f(a, b, c)
    count := 0
    for k from a to b
         if omega[k] == c
             count := count + 1
    return count

例如f(5,15,2) = 5（集合6、10、12、14、15），f(2,10,1) = 7（集合2、3、4、5、7、8、9）， f(24,42,3) = 2（集合30、42），以及f(2,10000000,7) = 1716.

如果您的范围太大而无法方便地筛选，您将必须对范围内的每个数字进行因式分解，并计算具有正确数量的不同因数的那些。

找到数字的主要因素的更好方法

Better way of finding Prime Factors of a number

c++

math

primes