Количество различных простых факторов числа

Question

Q: Даны A,B и K. Найдите все числа между A и B(включительно), которые имеют K DISTINCT простых факторов. Вот что я сделал. Я реализовал сито Эратосфена и вычислил все простые числа до верхней границы A,B. Затем я продолжаю выяснять, какое из этих простых чисел является множителем чисел между A и B. Если число различных простых чисел равно K, я увеличиваю счет. Проблема, с которой я сталкиваюсь - это проблема времени. Даже после внедрения решета требуется 10 секунд, чтобы вычислить ответ на 2 100000,1 (числа между 2 и 100 000, которые имеют 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), но кажется, что все в порядке (вы можете заменить 1 от 0 в строке 3 и 5 в зависимости от того, хотите ли вы включить 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 означает, что 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;
}

Запускается менее 1 секунды даже для теста (2 100000 1): http://ideone.com/rMTIBj