数字的不同质数的数量

Question

Q：给定A，B和K。找出A和B（含）之间所有具有K DISTINCT主因子的数字。这是我所做的。我已经实现了Eratosthenes筛，并计算了所有素数，直到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

关于进一步优化它的任何技巧？

Answer 1

这应该做您想做的事情：

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中包括1）因素）。

Answer 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表示我不是素数（并且我们已经找到它的最小除数）。现在让我们考虑所有数字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