Факторы В Java - PullRequest
Новая
       96

Факторы В Java

2 голосов
/ 12 марта 2020

Я пытаюсь вычислить список простых факторов факториала n, причем простые факторы отсортированы в порядке возрастания, и каждый из них в этом списке ровно столько раз, сколько он будет отображаться при простой факторизации факториала.

У меня есть программа, которая вычисляет связанный список простых чисел до указанного числа, но я не уверен, как реализовать это, добавляя простые множители целого числа, которое в настоящее время умножается на факториал:

Ответы [ 4 ]

0 голосов
/ 12 марта 2020

Это еще один способ. Он включает в себя несколько проверок для обеспечения ненужного тестирования, чтобы как можно скорее выйти из циклов. Это работает так же, если вы хотите найти число 0 в конце N факториала. Чтобы сделать это, просто сложите коэффициенты деления N на последовательные степени 5 (так как 5 - это больший коэффициент 10).

Это работает путем сложения факторов N путем непрерывного деления на каждое простое число. 

    public static List<Integer> getNFactorialFactors(int n, List<Integer> primes) {
        List<Integer> factors = new ArrayList<>();
        int nn = n;
        for (int p : primes) {
            while (nn > 1) {
                for (int i = nn / p; i > 0; i--) {
                    factors.add(p);
                }
                nn /= p;
            }
            nn = n;
        }

        return factors;
    }
0 голосов
/ 12 марта 2020 
public static List<Integer> getFactorialPrimeFactors(int n)
{
    List <Integer> primes = primeNum(n);

    ArrayList <Integer> primeDivisors = new ArrayList<>();
    for(int i: primes)
    {
        int count = 0;
        for(int num = i; num <= n; num *= i)
        {
            count += n/num;
        }

        while(count > 0)
        {
            primeDivisors.add(i);
            count--;
        }
    }

    return primeDivisors;
}

Пояснение - https://math.stackexchange.com/a/642220

0 голосов
/ 12 марта 2020

У вас также должен быть метод, который вычисляет основные множители числа и возвращает его в виде списка. Вы передаете список простых чисел, полученных от primeNum, который возвращает список простых чисел вплоть до числа. 

public static List<Integer> primeFactors(int number, List<Integer> primes) {
    List<Integer> ans = new ArrayList<>();
    // test condition includes number >= primes.get(i)
    // so the loop exits when the current prime is greater than the number
    for(int i = 0; i < primes.size() && number >= primes.get(i); i++){
        while(number % primes.get(i) == 0){
            ans.add(primes.get(i));
            number = number / primes.get(i);
        }
    }
    return ans;
}

Затем в вашем основном методе вы можете написать forl oop, который перебирает все числа от 1 до n и вызывать этот метод primeFactors каждые l oop. Вы перебираете результат, полученный при вызове этого метода, и добавляете эти простые числа в список. Наконец, вы можете отсортировать список, если хотите, чтобы числа были в порядке. 

List<Integer> primes = primeNum(n);
for(int i = 1; i <= 10; i ++){
    List<Integer> temp = primeFactors(i,primes);
    for(int j = 0; j < temp.size(); j++){
        list.add(temp.get(j));
    }
}
0 голосов
/ 12 марта 2020

Допустим, вы вычислили все простые числа из [2..N] и давайте назовем этот набор P , затем для каждого p in P вы можете получить каждое число n из [2..N] и проверить, сколько раз p делит n и поместите его в связанный список. Если вы думаете немного больше о том, что MT756 сказал в комментарии выше, вы можете сделать алгоритм, который я сказал, немного быстрее. Я не ставил код java, чтобы сделать эту задачу немного увлекательной для вас. :)

...