1

问：给定 A、B 和 K。找出 A 和 B（含）之间所有具有 K 个 DISTINCT 素因子的数。这就是我所做的。我已经实现了埃拉托色尼筛并计算了所有素数，直到 A、B 的上限。然后我继续找出这些素数中的哪一个是 A 和 B 之间数字的因数。如果不同素数的数量等于 K，我增加计数。我遇到的问题是时间问题。即使在实施筛子之后，计算 2,10000,1 的答案也需要 10 秒（2 到 100000 之间的数字具有 1 个不同的素因子）这是我的代码

    import math

    #Sieve of erastothenes
    def sieve(n):
        numbers=range(0,n+1)
        for i in range(2,int(math.ceil(n**0.5))):
            if(numbers[i]):
                for j in range(i*i,n+1,i):
                    numbers[j]=0

        #removing 0 and 1 and returning a list          
        numbers.remove(1)
        prime_numbers=set(numbers)
        prime_numbers.remove(0)

        primes=list(prime_numbers)
        primes.sort()
        return primes

    prime_numbers=[]
    prime_numbers=sieve(100000)
    #print prime_numbers
    def no_of_distinct_prime_factors(n):

        count=0
        flag=0
        #print prime_numbers
        for i in prime_numbers:
            #print i
            if i>n:
                break
            if n%i==0:
                count+=1
                n=n/i
        return count
    t=raw_input()
    t=int(t)
    foo=[]
    split=[]
    for i in range (0,t):
        raw=raw_input()
        foo=raw.split(" ")
        split.append(foo)
    for i in range(0,t):
        count=0
        for k in range(int(split[i][0]),int(split[i][1])+1):
            if no_of_distinct_prime_factors(k)==int(split[i][2]):
                count+=1
        print count

关于如何进一步优化它的任何提示？

4

2 回答 2

2

我不知道 python [ ;( ]，但我知道如何优化它。我们可以在这里使用线性筛 - 它是对 Erastothenes 筛的修改，适用于 O(n) 并允许快速分解（ O(k )，其中 k 是分解中的素数数量)。

我们要做的是有 2 个数组 - pr（具有素数的数组：pr[i] 是第 i 个素数）和 lp（具有最少除数的数组：lp[i] 是是 i) 的除数。lp 数组中的初始值为零。我们将遍历 [2, X] 中的所有数字。对于每个数字（我们称之为 i），有 2 种可能的变体： 1. lp[i] = 0 表示 i 之前没有数字是 i 的除数，因此 i 是质数。2. lp[i] != 0 意味着 i 不是素数（我们已经找到了它的最小除数）。现在让我们考虑所有的数字 x[j] = i * pr[j]。如果 pr[j] 满足 pr[j]<=lp[i]，则 x[j] 的最小除数是 pr[j]（很明显 - 询问是否不是）。

然后我们可以编写如下代码（C++，因为我不熟悉python）：

const int N = 100001; //the maximum possible input
int lp[N+1];
vector<int> pr;

void init()
{
    for (int i=2; i<=N; ++i) 
    {
        if (lp[i] == 0) //i is prime
        {
            lp[i] = i;
            pr.push_back (i);
        }
        for (int j=0; j<pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
            lp[i * pr[j]] = pr[j];
    }
}

现在我们有了 lp 数组，我们可以轻松地分解每个数字 n：lp[n] 是 n 的除数。然后我们可以分配 n = n / lp[n] 并继续这个过程。由于 lp 是最小除数，因式分解中的所有除数只能以升序出现。所以很容易计算不同的素数除数的数量：

int count(int n)
{
    int ans = 0;
    int curprime = 0;
    while (n!=1)
    {
        int minp = lp[n];
        if (minp != curprime) ++ans, curprime = minp;

        n/=minp;
    }
    return ans;
}

然后我们可以观察 [A,B] 中的每个数字并计算 dist 的数量。主要除数来回答这个问题：

int f(int a, int b, int c)
{
    int cnt = 0;
    for (int i = a; i <= b; ++i)
        if (count(i)==c)
            ++cnt;
    return cnt;
}

即使测试 (2,1000000,1) 也运行不到 1 秒：http: //ideone.com/rMTIBj

于 2013-07-09T13:57:04.227 回答
2

这应该做你想做的事情：

max=100000
k=6
nb_factors=[1]*max
for i in range(2,max):
    if nb_factors[i] == 1:
        for j in range(i, max, i):
            nb_factors[j]+=1

print [(i,f) for i,f in enumerate(nb_factors) if f > k]

我没有检查正确性（特别是对于像 0 和 1 这样的边缘情况），但它似乎没问题（您可以在第 3 行和第 5 行替换1，0具体取决于您是否要在因素列表中包含 1）。

于 2013-07-09T10:55:38.817 回答