Найдите число, которое имеет 4 различных простых фактора - PullRequest
Новая
       18

Найдите число, которое имеет 4 различных простых фактора

2 голосов
/ 01 июля 2019

Получите число n от пользователя. Затем выведите n-е число, которое имеет как минимум 4 различных простых множителя.Например, (210 простых множителей (2,3,5,7)) 210 - это первое число, имеющее 4 различных простых фактора, следующее число - 330 (2,3,5,11).Вход: 2 выход: 330 и Вход: 3 выход: 390. Я не знаю, как это сделать? Я пытался найти основные факторы для числа. 

 for (int i = 2; i <= number; i++) {
     while (number % i == 0) {
        System.out.print(i + " ");
        number = number / i;
     }
 }
 if (number < 1) 
     System.out.println(number);

Но я хочу напечататьn-е число, имеющее 4 различных простых фактора.

Ответы [ 2 ]

2 голосов
/ 01 июля 2019

Вы можете использовать следующий код: 

public static boolean findPrimeFactors(int n) {
    Set<Integer> primeFactorSet = new HashSet<>();
    while (n % 2 == 0) {
        // here number is even so adding 2
        primeFactorSet.add(2);
        n /= 2;
    }

    // number would be odd in this loop
    for (int i = 3; i <= Math.sqrt(n); i += 2) {
        while (n % i == 0) {
            primeFactorSet.add(i);
            n /= i;
        }
    }

    if (n > 2) {
        primeFactorSet.add(n);
    }

    // true if the unique prime-factors are greater than or equal to 4
    return primeFactorSet.size() >= 4 ? true : false;
}

Теперь вызовите его, используя: 

public static void main(String[] args) {
    List<Integer> primeFactorList = new ArrayList<Integer>();
    // accept this from user
    int n = 2;

    for (int i = 210;; i++) {
        // find prime factors for each number
        if (findPrimeFactors(i)) {
            primeFactorList.add(i);
        }
        if (primeFactorList.size() == n) {
            System.out.println(primeFactorList.get(n - 1));
            break;
        }
    }
}

Пояснение:

  1. Цикл повторяется от 210 до n-го числа, которое имеет четыре или более различные простые факторы.
  2. Для каждого числа, которое соответствует критериям, метод возвращает true, иначе false.
  3. Затем выполняется проверка, чтобы увидеть, равен ли размер списка номер (n), введенный пользователем. Если оно равно n-1 й Индекс извлекается и цикл завершается.
0 голосов
/ 03 июля 2019

Одна проблема с вышеупомянутым методом состоит в том, что он делит на все нечетные числа вплоть до квадратного корня кандидата.Было бы лучше разделить на ранее накопленные простые числа.Это легко сделать следующим образом: 

      List<Integer> primes = new ArrayList<>(List.of(2));
      outer:
      for (int i = 3; i < n; i++) {
         int end = (int)Math.sqrt(i);
         for (int k = 0, p = primes.get(0); p <= end; p =
               primes.get(k++)) {
            if (i % p == 0) {
               continue outer;
            }
         }
         primes.add(i);
      }

И вывести вычисление квадратного корня из цикла.Оценивается на каждом цикле.

...