1

Q: A、B、K が与えられた場合、K DISTINCT の素因数を持つ A と B の間 (両端を含む) の数をすべて見つけます。これが私がやったことです.エラトステネスのふるいを実装し、A、Bの上限まですべての素数を計算しました。次に、これらの素数のどれが A と B の間の数の約数であるかを見つけます。異なる素数の数が K に等しい場合、count をインクリメントします。私が直面している問題は、時間の問題です。ふるいを実装した後でも、2,10000,1 (1 つの異なる素因数を持つ 2 から 100000 までの数値) の答えを計算するのに 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

さらに最適化するためのヒントはありますか？

4

2 に答える 2

2

Python [ ;( ] はわかりませんが、最適化の方法は知っています。ここでは、線形ふるいを使用できます。これは、O(n) に対して機能し、素早い因数分解 ( O(k )、ここで、k は因​​数分解の素数の量です)。

私たちがやろうとしているのは、2 つの配列を持つことです - pr (素数の配列: pr[i] は i 番目の素数) と lp (最小約数の配列: lp[i] は最小の数です。は i) の除数です。lp 配列の初期値はゼロです。[2, X] のすべての数値を反復処理します。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] です (非常に明白です - そうでないかどうか尋ねてください)。

次に、次のコードを記述できます (私は Python に詳しくないので C++ です)。

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 に答える