Подсчитать числа полупростых в заданном диапазоне [a..b]

Question

Я решаю проблему Codility CountSemiprimes: Подсчитать числа полупростых в заданном диапазоне [a..b] .

Описание задачи

A штрих - это положительное целое число X, которое имеет ровно два различных делителя: 1 и X. Первые несколько простых целых чисел - это 2, 3, 5, 7, 11 и 13.

A semiprime - натуральное число, являющееся произведением двух (не обязательно различных) простых чисел.Первые несколько полупростых чисел: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.

Вам даны два непустых массива P и Q, каждый из которых состоит из M целых чисел.Эти массивы представляют собой запросы на количество полупростых в указанных диапазонах.

Запрос K требует, чтобы вы нашли количество полупростых в диапазоне (P [K], Q [K]), где 1 ≤ P [K] ≤ Q [K] ≤ N.

Напишите эффективный алгоритм для следующих предположений:

• N - целое число в диапазоне [1..50,000];
• M - целое число в диапазоне [1..30,000];
• каждый элемент массивов P, Q - целое число в диапазоне [1..N];P [i] ≤ Q [i].

Мое решение

Моя текущая оценка составляет 66%, и проблема заключается в выполнении для большого набора данных:

• большой случайный, длина = ~ 30000
• все максимальные диапазоны

Тест говорит, что это займет около 2 секунд, но мое решение занимает более 7 секунд.

Этомое текущее решение

class Solution {
    private static List<Integer> getPrimes(int max) {
        List<Integer> primes = new ArrayList<>(max / 2);

        for (int i = 0; i < max; i++)
            if (isPrime(i))
                primes.add(i);

        return primes;
    }

    private static boolean isPrime(int val) {
        if (val <= 1)
            return false;
        if (val <= 3)
            return true;

        for (int i = 2, sqrt = (int)Math.sqrt(val); i <= sqrt; i++)
            if (val % i == 0)
                return false;

        return true;
    }

    private static boolean[] getSemiPrimes(int N) {
        List<Integer> primes = getPrimes(N);
        boolean[] semiPrimes = new boolean[N + 1];

        for (int i = 0; i < primes.size(); i++) {
            if (primes.get(i) > N)
                break;

            for (int j = i; j < primes.size(); j++) {
                if (primes.get(j) > N || N / primes.get(i) < primes.get(j))
                    break;

                int semiPrime = primes.get(i) * primes.get(j);

                if (semiPrime <= N)
                    semiPrimes[semiPrime] = true;
            }
        }

        return semiPrimes;
    }

    public static int[] solution(int N, int[] P, int[] Q) {
        boolean[] semiPrimes = getSemiPrimes(N);
        int[] res = new int[P.length];

        for (int i = 0; i < res.length; i++)
            for (int j = P[i]; j <= Q[i]; j++)
                if (semiPrimes[j])
                    res[i]++;

        return res;
    }
}

Есть идеи по улучшению производительности?Последнее, что я должен был удалить Set для хранения полупростых чисел с массивом.Это помогло мне решить пару тестов производительности.

Answer 1

Java-решение, которое получает 100%, выглядит следующим образом:

• Найдите набор простых чисел, для которых их произведения не превосходят N

• создайте из них полу-простое число как битовый массив из 0 и 1

• создайте префиксную сумму из полу-простых чисел

• вычисляет запросы от P[i] до Q[i] в O(M)

Весь алгоритм равен O(N * log(log(N)) + M), указанному в результате оценки результатов теста Codility.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CountSemiPrime {

    public static void main(String[] args) {
        int[] P = new int[] {1, 4, 16};
        int[] Q = new int[] {26, 10, 20};
        System.out.println( Arrays.toString( new CountSemiPrime().solution( 26, P, Q ) ) );
    }

    public int[] solution(int N, int[] P, int[] Q) {

        Integer[] primes = sieve(N/2+1);

        int[] temp = new int[N+1];
        for (int i = 0; i < primes.length; i++) {
            for (int j = 0; j < primes.length; j++) {
                int semiPrime = primes[i] * primes[j];
                if(semiPrime <= N)
                    temp[semiPrime] = 1;
            }
        }

        int[] prefix = new int[N+1];
        for (int i = 1; i < temp.length; i++) {
            prefix[i] = temp[i] + prefix[i-1];
        }

        int[] retVal = new int[P.length];
        for (int i = 0; i < retVal.length; i++) {
            retVal[i] = prefix[Q[i]] - prefix[P[i]-1];
        }

        return retVal; 
    }


    public Integer[] sieve(int n) {

        boolean[] temp = new boolean[n+1];
        for (int i = 0; i < temp.length; i++) {
            temp[i] = true;
        }
        temp[0] = temp[1] = false;

        int i = 2;
        while (i * i <= n) {
            removeProducts( temp, i );
            i++;
        }

        List<Integer> ret = new ArrayList<>();
        for (int j = 0; j < temp.length; j++) {
            if(temp[j])
                ret.add( j );
        }

        return ret.toArray( new Integer[ret.size()] );
    }

    private void removeProducts(boolean[] temp, int i) {
        for (int j = i*i; j < temp.length; j++) {
            if(temp[j] && j % i == 0) {
                temp[j] = false;
            }
        }
    }
}

Answer 2

Рубиновый 100% раствор

require 'prime'
require 'set'

def solution(n, p, q)
    primes = Prime::EratosthenesGenerator.new.take_while {|i| i <= n/2 }
    sqrt = Math.sqrt(n)
    semiprimes = primes.each_with_index.inject(Set.new) do |acc, (e,i)|
      break acc if e > sqrt.to_i
      primes[i..-1].each{ |pr| e*pr > n ? break : acc << e*pr }
      acc
    end
    offsets = semiprimes.sort.each_with_index.inject([]) {|acc,(el,i)| acc[el] = i+1;acc  }

    p.each_with_index.inject([]) do |acc, (el,i)|
      next acc << 0 unless offsets[el..q[i]]

      left =  offsets[el..q[i]].detect{|a| a}
      next acc << 0 unless left

      right = offsets[el..q[i]].reverse_each.detect{|a| a}

      acc << ((left..right).size)
    end
end

Answer 3

Мое решение использует сито Эратосфена, так что наименьший простой множитель числа N хранится в массиве Factor [N].Тогда, если Factor [N / Factor [N]] = 0, у нас есть полу-простое число, увеличивающее сканирование суммы.Запись r возвращаемого массива будет тогда: A [r] = Inclusive_scan [Q [r]] - Inclusive_scan [P [r] -1].

Здесь соответствующий код Python (100% оценка задачи):

def solution(N, P, Q):
 A=len(P)*[0]
 if N<4:
     return A
#Minimum prime factor of n stored in Factor[n]
 Factor = [0] * (N + 1)
 i = 2
 while (i * i <= N):
  if (Factor[i] == 0):
   k = i * i
   while (k <= N):
    if (Factor[k] == 0):
     Factor[k] = i;
    k += i
  i += 1
#Count semi prime numbers and store 
#sum scan in array Incluse_scan   
 Incluse_scan=[0] * (N + 1)
 cnt_semi=0
 for k in range(4,N+1):
     if Factor[k]!=0:
         d=int(k/Factor[k])
         if Factor[d]==0:
             cnt_semi+=1                 
     Incluse_scan[k]=cnt_semi   
#Do the difference of semi prime counters
 for r in range(0,len(P)):
     if(P[r]<=4):
       min_inclusive=0
     else:
       min_inclusive=P[r]-1 
     A[r]=Incluse_scan[Q[r]]-Incluse_scan[min_inclusive] 
 return A

Answer 4

const isSemiPrime = (num) => {
    let cnt = 0
    for (let i = 2; cnt < 2 && i * i <= num; ++i) {
        while (num % i == 0) {
            num /= i
            ++cnt
        }
    }
    if (num > 1)++cnt
    return cnt == 2 ? true : false
}

console.log(
    [4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55].filter(isSemiPrime)
        .length
)

Answer 5

Вы можете предварительно вычислить массив A размером N + 1, который хранит в A [i] число полуэлементов, меньших или равных i.Тогда запрос p, q может быть вычислен немедленно: число полупростых чисел между p и q (включительно) равно A[q] - A[p-1].

Этот массив может быть эффективно вычислен: пусть P - массив простых чисел, меньший илиравно N / 2.Затем (в псевдокоде, подобном java):

A = new int[N+1]
for (int p : P) {
  for (int q : P) {
      if (p*q > N || q > p) break;
      A[p*q] = 1
  }
}

for (int i = 1; i <= N; i++)
    A[i] += A[i-1]

Это работает, помечая полуприборы 1 в массиве, а затем беря кумулятивную сумму.Это работает лучше, чем O (N ^ 2) и хуже, чем O (N) времени - около N/2logN простых чисел в P, поэтому первая часть - это O ((N / logN) ^ 2), исуммирование O (N).[Примечание: я думаю, что первая часть имеет большую сложность, чем O ((N / log N) ^ 2) из-за раннего завершения внутреннего цикла, но я не доказал это].Вычисление простых чисел в P - это O (N log log N) с использованием сита Эрастотена.

В версии Python этой программы требуется 0,07 с для предварительного вычисления A для N=50000 и выполнения 30000запросы.Он получает идеальный балл (100) при запуске на codility, и codility сообщает, что обнаруживает, что код имеет сложность O (N log (log (N)) + M).

Answer 6

Это была интересная проблема.Я попробовал это и получил 88%.

Вот моя стратегия:

• Я использовал Сито Эратосфена для получения BitSet для простых чисел.
• Теперь я зациклился на этом BitSet и добавил все простые числа в primeList.
• Моя стратегия поиска полупростых чисел была немного интересной, и я постепенно достигал этой стратегии.

private static boolean isSemiPrime(int n) {&#10;    if(n==1 || n==0 || primeBitSet.get(n))&#10;        return false;&#10;    int firstFactor = findFirstFactor(n);&#10;    if(firstFactor==0 || firstFactor==1)&#10;        return false;&#10;    return isPrime(n / firstFactor);&#10;}&#10;&#10;private static int findFirstFactor(int n) {&#10;&#10;    for (int i = 0; i < primeList.size(); i++) {&#10;        if (n % primeList.get(i) == 0)&#10;            return primeList.get(i);&#10;    }&#10;    // should never be the case&#10;    return 0;&#10;}

Я не очень уверен, почему я набрал 88% баллов.(Что мне не хватает)

Но самой интересной и заслуживающей внимания частью была стратегия проверки того, является ли данное число полупростым или нет:

• Найдите первое простое числофактор данного числа
• Затем проверяется, является ли частное данного числа и первого простого множителя простым или нет.
• Если оно простое, то данное число являетсяполу-простое, иначе данное число не является полу-простым.

Обратите внимание, что я также сделал очень наивную форму бухгалтерского учета, где я сделал накопительный массив, который хранит общее количество полупростые числа до индекса x.Один раз заполнение этого массива и ответ на каждый запрос в O(1) снова является очевидной оптимизацией.

Не связано с решением, но мои Task Score составили 88%, Correctness 100% и Performance80%.Я буду рад услышать предложения и все, что я пропустил.

Надеюсь, это поможет.:)