首页 文章

一个数字的不同素数因子的数量

提问于
浏览 次
1

问：给定A，B和K.找到具有K DISTINCT素因子的A和B（包括）之间的所有数字 . 这就是我所做的 . 我已经实施了Eratosthenes的Sieve并计算了所有素数直到A，B的上界 . 然后我继续找到这些素数中的哪一个是A和B之间数字的因子 . 如果不同质数的数量等于K，我增加计数 . 我遇到的问题是时间问题 . 即使在实施筛子后，计算答案为2,10000,1（2到100000之间的数字有1个不同的素数因子）需要10秒钟，这是我的代码

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

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

python primes sieve-of-eratosthenes prime-factoring

2 回答

  • 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行用 0 替换 1 ，具体取决于你是否要在因子列表中包含1） .

    回复于
  • 2

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

    我们要做的是有2个数组 - pr（具有素数的数组：pr [i]是第i个素数）和lp（具有最少除数的数组：lp [i]是最小的数字是i）的除数 . lp数组中的初始值为零 . 我们将遍历[2，X]中的所有数字 . 对于每个数字（让我们称之为i），有两种可能的变体：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]（非常明显 - 询问它是否不是） .

    然后我们可以编写以下代码（因为我不熟悉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;
}

    测试时运行不到1秒（2,1000000,1）：http://ideone.com/rMTIBj

    回复于

相关问题