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

Я хочу рассчитать количество различных простых множителей каждого целого числа до n. Например, 12 = 2 * 2 * 3, поэтому у него есть 2 разных простых множителя, 2 и 3. Я хочу сохранить каждое из этих значений в массиве result[] размера n+1, в котором result[i] содержит количество различных простых множителей целого числа i.

В своем решении я должен использовать следующий внешний метод:

List<Integer> getPrimes(int n) {
    // create array to determine which numbers are prime
    boolean isPrime[] = new boolean[n+1];
    for(int i=2; i<=n; i++)
      isPrime[i] = true; // assume all are prime, we'll filter below
    
    for(int i=3; i*i<=n; i+=2) {
      if (isPrime[i]) {             // i is prime, so...
        for(int j=i*i; j<=n; j+=i)  //  remove all its multiples
          isPrime[j] = false;       //  by updating array
      }
    }
    
    // create list with only the prime numbers
    List<Integer> primes = new LinkedList<>();
    primes.add(2);
    for(int i=3; i<=n; i+=2)
      if (isPrime[i])
        primes.add(i);
    return primes;
  }

который использует решето Эратосфена для возврата списка всех простых чисел до n. Это было мое решение:

int[] getNumPrimeFactors(int n) {
        int[] result = new int[n + 1];
        int counter; // counts the number of different prime factors
        boolean isPrime = true;
        List<Integer> primeList = getPrimes(n);

        for (int i = 2; i < result.length; i++) {
            counter = 0;
            
            // checks if i is prime 
            if (i % 2 == 0) {
                isPrime = false;
            } else {
                for (int j = 3; j * j <= i; j += 2) {
                    if (i % j == 0)
                        isPrime = false;
                }
            }
            // if i isnt prime, counts how many different prime factors it has
            if (!isPrime) {
                for (int prime : primeList) {
                    if (i % prime == 0)
                        counter++;
                }
                result[i] = counter;
            } else {
                result[i] = 1;
            }
        }
        return result;
    }

Этот алгоритм дает правильные результаты, однако я хочу проверить n ‹ = 5_000_000, и он недостаточно эффективен. Можно ли как-то улучшить код для очень больших экземпляров n? Вот несколько примеров результатов теста:

Большое спасибо за Вашу помощь :)


java list prime-factoring
person tango    schedule 21.03.2021    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Это точно не самый эффективный алгоритм, но на моем старом компе (i5 3570K) работает до 5_000_000 чуть больше 10 секунд. Сумма массива результатов для 5_000_000 составляет 14838426.

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

public class Main {

    public static List<Integer> primeFactors(int number) {
        int n = number;
        List<Integer> factors = new ArrayList<Integer>();
        for (int i = 2; i <= n / i; i++) {
            while (n % i == 0) {
                factors.add(i);
                n /= i;
            }
        }
        if (n > 1) {
            factors.add(n);
        }
        return factors;
    }

    public static void main(String[] args) {
        int[] result = new int[5_000_001];
        for (int i = 0; i < result.length; i++) {
            result[i] = (int) primeFactors(i).stream().distinct().count();
        }
        System.out.println(Arrays.stream(result).sum());
    }
}
person chptr-one    schedule 21.03.2021

arrow_upward
1
arrow_downward

Одно стандартное усовершенствование, которое я часто нахожу полезным при просеивании таким образом, — это настройка наименьших простых множителей для всех значений (вместо просто значения true/false). Тогда первое решение - это проверка того, меньше ли наименьший простой множитель lpf значения. Это в основном почти так же быстро, как простое решето, но затем дает более прямой путь к факторизации чисел в диапазоне.

В Питоне:

lim = 5000000+1 

# precalc all least prime factors for composites in range
lpf = [i for i in range(lim)]
for m in range(4,lim,2):
    lpf[m] = 2
k = 3
while k*k <= lim:
    if lpf[k] == k:
        for m in range(k*k, lim, 2*k):
            if lpf[m] == m:
                lpf[m] = k
    k += 2

print('lpf done',lim) ############

# find number of distinct prime factors for each
result = [0]*lim
for a in range(2,lim):
    pf = lpf[a]
    fc = 1
    res = a
    while pf < res:
        res //= pf
        if pf != lpf[res]:
            fc += 1
            pf = lpf[res]
    result[a] = fc
    
print(result[:11])
print(sum(result[:10+1]))
print(sum(result[:1234+1]))
print(sum(result[:1000000+1]))

Сито здесь занимает чуть более двух секунд, что составляет около четверти всего времени.

person Joffan    schedule 06.04.2021