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

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

Есть какие-нибудь советы по его дальнейшей оптимизации?


python primes prime-factoring sieve-of-eratosthenes
person Ole Gooner    schedule 09.07.2013    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Это должно делать то, что вы пытаетесь сделать:

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 в список факторов).

person SylvainD    schedule 09.07.2013

arrow_upward
2
arrow_downward

Я не знаю python [; (], но знаю, как его оптимизировать. Здесь мы можем использовать линейное сито - это модификация сита Эрастотена, которое работает для 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] и посчитать расстояние. простые делители, чтобы ответить на вопрос:

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

person h8red    schedule 09.07.2013
comment
вот простейшая наглядная адаптация простого сита Эратосфена для сравнения. Кажется, работает в 3 раза быстрее. - person Will Ness; 09.08.2013