Алгоритм нахождения наибольшего простого множителя числа

183

Каков наилучший подход к вычислению наибольшего простого множителя числа?

Я думаю, что наиболее эффективным будет следующее:

  1. Найти наименьшее простое число, которое делит чисто
  2. Проверьте, является ли результат деления простым
  3. Если нет, найдите следующий самый низкий
  4. Перейти к 2.

Я основываю это предположение на том, что легче вычислить малые простые факторы. Это правильно? Какие еще подходы я должен рассмотреть?

Редактировать: Теперь я понял, что мой подход бесполезен, если в игре более двух основных факторов, поскольку шаг 2 не выполняется, когда результат является продуктом двух других простых чисел, поэтому необходим рекурсивный алгоритм.

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

Меркуцио
источник
Мой подход был: (1) разделить большое, возможное число на 2; (2) проверить, делится ли большое число равномерно на него; (3) если так, проверьте, простое ли число, деленное на 2. Если это так, верните его. (4) Иначе, вычтите 1 из числа, разделенного на 2, и вернитесь к шагу 3.
Кевин Мередит,
1.найти любое число, которое делится четко (для i = 2 на int (sqr (num))), 2.разделить на это число (num = num / i) и повторять до тех пор, пока ничего не будет найдено в интервале 1. 3. num - это самый большой фактор
user3819867
1
Мы можем разделить с небольшими простыми числами, и тот, который, наконец, оставлен, является самым

Ответы:

134

На самом деле есть несколько более эффективных способов найти факторы больших чисел (для более мелких пробное деление работает достаточно хорошо).

Один метод, который очень быстр, если входное число имеет два фактора, очень близких к его квадратному корню, известен как факторизация Ферма . Он использует тождество N = (a + b) (a - b) = a ^ 2 - b ^ 2 и прост для понимания и реализации. К сожалению это не очень быстро в целом.

Наиболее известным методом для вычисления чисел длиной до 100 цифр является квадратичное сито . В качестве бонуса, часть алгоритма легко выполняется с параллельной обработкой.

Еще один алгоритм, о котором я слышал, - это алгоритм Полларда Ро . Это не так эффективно, как Quadratic Sieve в целом, но, кажется, его легче реализовать.


Как только вы решили, как разделить число на два фактора, вот самый быстрый алгоритм, который я могу придумать, чтобы найти наибольший простой фактор числа:

Создайте очередь с приоритетами, в которой изначально хранится сам номер. На каждой итерации вы удаляете наибольшее число из очереди и пытаетесь разделить его на два фактора (конечно, не позволяя 1 быть одним из этих факторов). Если этот шаг не пройден, число простое, и у вас есть свой ответ! В противном случае вы добавляете два фактора в очередь и повторяете.

Artelius
источник
3
Поллард Ро и метод эллиптической кривой намного лучше избавляются от небольших простых множителей вашего числа, чем квадратичное сито. QS имеет примерно одинаковое время выполнения независимо от количества. Какой подход быстрее, зависит от того, какой у вас номер; QS будет быстрее взламывать трудно-факторные числа, тогда как rho и ECM будут быстрее взламывать легко-факторные числа.
tmyklebu
Спасибо за предложение о квадратичной вариации. Мне нужно было реализовать это для одного из моих клиентов, первоначальная версия, которую я придумал, была чем-то вроде того, что @mercutio предложил в своем вопросе. Квадратичное решение - это то, что теперь помогает моему клиенту по адресу math.tools/calculator/prime-factors .
DORS
Если существует эффективный способ решения этой проблемы, не означает ли это, что веб-шифрование небезопасно?
BKSpurgeon
141

Вот лучший алгоритм, который я знаю (в Python)

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1

    return factors


pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list

Вышеприведенный метод работает в O(n)худшем случае (когда вход является простым числом).

РЕДАКТИРОВАТЬ:
Ниже приведена O(sqrt(n))версия, как предлагается в комментарии. Вот код, еще раз.

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1
        if d*d > n:
            if n > 1: factors.append(n)
            break
    return factors


pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list
Триптих
источник
11
Пожалуйста, прочитайте и / или запустите этот код, прежде чем голосовать за него. Работает нормально. Просто скопируйте и вставьте. Как написано, prime_factors (1000) вернет [2,2,2,5,5,5], что следует интерпретировать как 2 ^ 3 * 5 ^ 3, то есть простую факторизацию.
Триптих
11
«работает в O(sqrt(n))худшем случае» - нет, он работает в O(n)худшем случае (например, когда nэто простое число)
Шелдон Л. Купер
16
Легко сделать это O (sqrt (n)), вы просто останавливаете цикл, когда d * d> n, и если n> 1 в этой точке, то его значение должно быть добавлено к списку простых факторов.
Сумуду Фернандо
5
Есть ли название для этого?
дальновидный
11
поскольку 2 - единственное четное простое число, поэтому вместо добавления 1 каждый раз вы можете выполнять итерацию отдельно для d = 2, а затем увеличивать ее на 1, а затем, начиная с d = 3, вы можете увеличивать на 2., так что это уменьшит число итераций ... :)
tailor_raj
18

Мой ответ основан на Триптихе , но значительно улучшается. Он основан на том факте, что за пределами 2 и 3 все простые числа имеют вид 6n-1 или 6n + 1.

var largestPrimeFactor;
if(n mod 2 == 0)
{
    largestPrimeFactor = 2;
    n = n / 2 while(n mod 2 == 0);
}
if(n mod 3 == 0)
{
    largestPrimeFactor = 3;
    n = n / 3 while(n mod 3 == 0);
}

multOfSix = 6;
while(multOfSix - 1 <= n)
{
    if(n mod (multOfSix - 1) == 0)
    {
        largestPrimeFactor = multOfSix - 1;
        n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
    }

    if(n mod (multOfSix + 1) == 0)
    {
        largestPrimeFactor = multOfSix + 1;
        n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
    }
    multOfSix += 6;
}

Недавно я написал статью в блоге, объясняющую, как работает этот алгоритм.

Я бы рискнул, что метод, в котором нет необходимости в тесте на первичность (и нет конструкции сита), будет работать быстрее, чем тот, который его использует. Если это так, то это, вероятно, самый быстрый алгоритм здесь.

sundar - Восстановить Монику
источник
12
На самом деле вы можете принять эту идею еще дальше, например, за пределами 2,3,5 все простые числа имеют вид 30n + k (n> = 0), где k принимает только те значения между 1 и 29, которые не делятся на 2,3 или 5, то есть 7,11,13,17,19,23,29. Вы можете даже динамически адаптировать его после каждых нескольких простых чисел, которые вы нашли до 2 * 3 * 5 * 7 * ... * n + k, где k не должно делиться ни на одно из этих простых чисел (обратите внимание, что не все возможные k нужны будьте простыми, например, для 210n + k вы должны включить 121, в противном случае вы бы пропустили 331 )
Тобиас Кинцлер
2
Я думаю, это должно бытьwhile (multOfSix - 1 <= n)
Надер Ганбари
8

Код JavaScript:

'option strict';

function largestPrimeFactor(val, divisor = 2) { 
    let square = (val) => Math.pow(val, 2);

    while ((val % divisor) != 0 && square(divisor) <= val) {
        divisor++;
    }

    return square(divisor) <= val
        ? largestPrimeFactor(val / divisor, divisor)
        : val;
}

Пример использования:

let result = largestPrimeFactor(600851475143);

Вот пример кода :

Влад Безден
источник
7

Похоже на ответ @Triptych, но также отличается. В этом примере список или словарь не используется. Код написан на Ruby

def largest_prime_factor(number)
  i = 2
  while number > 1
    if number % i == 0
      number /= i;
    else
      i += 1
    end
  end
  return i
end

largest_prime_factor(600851475143)
# => 6857
Угниус Малукас
источник
Наконец что-то читаемое и мгновенно (в js) исполняемый одновременно. Я пытался использовать бесконечный основной список, и он был слишком медленным на 1 миллион.
Ebuall
4

Все числа могут быть выражены как произведение простых чисел, например:

102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89

Вы можете найти их, просто начав с 2 и просто продолжая делить, пока результат не станет кратным вашему числу:

712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1

используя этот метод, вам не нужно фактически вычислять какие-либо простые числа: все они будут простыми числами, основываясь на том факте, что вы уже максимально разложили число со всеми предыдущими числами.

number = 712;
currNum = number;    // the value we'll actually be working with
for (currFactor in 2 .. number) {
    while (currNum % currFactor == 0) {
        // keep on dividing by this number until we can divide no more!
        currNum = currNum / currFactor     // reduce the currNum
    }
    if (currNum == 1) return currFactor;    // once it hits 1, we're done.
}
nickf
источник
Да, но это ужасно неэффективно. После того, как вы разделили все 2, вам действительно не следует пытаться делить на 4, или на 6, или ...; На самом деле в пределе гораздо эффективнее проверять только простые числа или использовать какой-либо другой алгоритм.
wnoise
6
+1 к смещению wnoise, который я считаю неправильным. Попытка делить на 4 произойдет только один раз, и сразу же потерпит неудачу. Я не думаю, что это хуже, чем удаление 4 из списка кандидатов, и это, безусловно, быстрее, чем поиск всех простых чисел заранее.
Триптих
2
@Beowulf. Попробуйте запустить этот код до голосования Это возвращает главные факторы; Вы просто не понимаете алгоритм.
Триптих
3
код работает нормально, но медленно, если входящий номер простое. Я бы также прибегал только к квадрату и увеличивал на 2. Хотя это может быть слишком медленно для очень больших чисел.
blabla999
4
Blabla999 совершенно верно. Пример: 1234567898766700 = 2 * 2 * 5 * 5 * 12345678987667. Когда мы достигли currFactor = 3513642, мы знаем, что 12345678987667 простое число, и должны вернуть его в качестве ответа. Вместо этого этот код будет продолжать перечисление до самого 12345678987667. Это на 3,513,642x медленнее, чем необходимо.
Уилл Несс
4
    //this method skips unnecessary trial divisions and makes 
    //trial division more feasible for finding large primes

    public static void main(String[] args) 
    {
        long n= 1000000000039L; //this is a large prime number 
        long i = 2L;
        int test = 0;

        while (n > 1)
        {
            while (n % i == 0)
            {
                n /= i;     
            }

            i++;

            if(i*i > n && n > 1) 
            {
                System.out.println(n); //prints n if it's prime
                test = 1;
                break;
            }
        }

        if (test == 0)  
            System.out.println(i-1); //prints n if it's the largest prime factor
    }
the_prole
источник
1
Вы пробовали свой код с 1 000 000 000 039? это должно бежать в мгновение ока также. Является ли?
Уилл Несс
2
Вы можете знать это заранее, не пытаясь. 10 ^ 12 = (2 * 5) ^ 12 = 2 ^ 12 * 5 ^ 12. Таким образом, ваш whileцикл будет проходить через iзначения 2,2,2,2,2,2,2,2,2,2,2,2, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5. Всего 60 итераций. Но (10 ^ 12 + 39) будет (10 ^ 12 + 38) итераций, i=2,3,4,5,6,...,10^12+39. Даже если 10 ^ 10 операций займет одну секунду, 10 ^ 12 займет 100 секунд. Но только 10 ^ 6 итераций действительно необходимы, и если 10 ^ 10 операций займет секунду, 10 ^ 6 займет 1/10000-й секунды.
Уилл Несс
1
Потому что я не понимал (10 ^ 12 + 39) было простым числом, которое я делаю сейчас. Я понимаю, что вы говорите.
the_prole
1
Итак, вы можете изменить свой код так, чтобы не было такого большого замедления для простых чисел: если n = a b и a <= b, то a a <= b a = n, то есть a a <= n , И если мы достигли + 1, то n, безусловно, простое число. (Пинг мне, если вы редактируете свой ответ, чтобы включить это).
Уилл Несс
1
что происходит когда long n = 2*1000000000039L? Работает ли он так быстро, как должен? (также, можете ли вы упростить свой код с помощью return;оператора?). (если вы хотите, чтобы я перестала подталкивать вас, просто скажите так;))
Уилл Несс
4

Самое простое решение - это пара взаимно рекурсивных функций.

Первая функция генерирует все простые числа:

  1. Начните со списка всех натуральных чисел больше 1.
  2. Удалите все числа, которые не являются простыми. То есть числа, которые не имеют главных факторов (кроме самих себя). Увидеть ниже.

Вторая функция возвращает простые множители заданного числа nв порядке возрастания.

  1. Возьмите список всех простых чисел (см. Выше).
  2. Удалите все числа, которые не являются факторами n.

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

Этот алгоритм требует отложенного списка или языка (или структуры данных) с семантикой вызова по требованию .

Для пояснения, вот одна (неэффективная) реализация вышеперечисленного в Haskell:

import Control.Monad

-- All the primes
primes = 2 : filter (ap (<=) (head . primeFactors)) [3,5..]

-- Gives the prime factors of its argument
primeFactors = factor primes
  where factor [] n = []
        factor xs@(p:ps) n =
          if p*p > n then [n]
          else let (d,r) = divMod n p in
            if r == 0 then p : factor xs d
            else factor ps n

-- Gives the largest prime factor of its argument
largestFactor = last . primeFactors

Чтобы сделать это быстрее, просто нужно быть более умным в определении того, какие числа являются простыми и / или факторами n, но алгоритм остается тем же.

Apocalisp
источник
2
n = abs(number);
result = 1;
if (n mod 2 == 0) {
  result = 2;
  while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
  if (n mod i == 0) {
    result = i;
    while (n mod i = 0)  n /= i;
  }
}
return max(n,result)

Есть некоторые тесты по модулю, которые излишни, так как n никогда не может быть разделено на 6, если все факторы 2 и 3 были удалены. Вы можете разрешить только простые числа для i, что показано здесь в нескольких других ответах.

Вы могли бы на самом деле переплетать сито Эратосфена здесь:

  • Сначала создайте список целых чисел до sqrt (n).
  • В цикле for отметьте все кратные числа i до нового sqrt (n) как не простые и используйте вместо этого цикл while.
  • установите i на следующее простое число в списке.

Также смотрите этот вопрос .

Ральф М. Рикенбах
источник
2

Я знаю, что это не быстрое решение. Размещение, как мы надеемся, облегчает понимание медленного решения.

 public static long largestPrimeFactor(long n) {

        // largest composite factor must be smaller than sqrt
        long sqrt = (long)Math.ceil(Math.sqrt((double)n));

        long largest = -1;

        for(long i = 2; i <= sqrt; i++) {
            if(n % i == 0) {
                long test = largestPrimeFactor(n/i);
                if(test > largest) {
                    largest = test;
                }
            }
        }

        if(largest != -1) {
            return largest;
        }

        // number is prime
        return n;
    } 
thejosh
источник
1

Итеративный подход Python, удаляющий все простые множители из числа

def primef(n):
    if n <= 3:
        return n
    if n % 2 == 0:
        return primef(n/2)
    elif n % 3 ==0:
        return primef(n/3)
    else:
        for i in range(5, int((n)**0.5) + 1, 6):
            #print i
            if n % i == 0:
                return primef(n/i)
            if n % (i + 2) == 0:
                return primef(n/(i+2))
    return n
Джотир Адитья Сингх
источник
1

Я использую алгоритм, который продолжает делить число на текущий фактор фактора.

Мое решение в Python 3:

def PrimeFactor(n):
    m = n
    while n%2==0:
        n = n//2
    if n == 1:         # check if only 2 is largest Prime Factor 
        return 2
    i = 3
    sqrt = int(m**(0.5))  # loop till square root of number
    last = 0              # to store last prime Factor i.e. Largest Prime Factor
    while i <= sqrt :
        while n%i == 0:
            n = n//i       # reduce the number by dividing it by it's Prime Factor
            last = i
        i+=2
    if n> last:            # the remaining number(n) is also Factor of number 
        return n
    else:
        return last
print(PrimeFactor(int(input()))) 

Вход: 10 Выход:5

Вход: 600851475143 Выход:6857

Калпеш Душане
источник
0

Вот моя попытка в C #. Последняя распечатка является наибольшим основным фактором числа. Я проверил, и это работает.

namespace Problem_Prime
{
  class Program
  {
    static void Main(string[] args)
    {
      /*
       The prime factors of 13195 are 5, 7, 13 and 29.

      What is the largest prime factor of the number 600851475143 ?
       */
      long x = 600851475143;
      long y = 2;
      while (y < x)
      {
        if (x % y == 0)
        {
          // y is a factor of x, but is it prime
          if (IsPrime(y))
          {
            Console.WriteLine(y);
          }
          x /= y;
        }

        y++;

      }
      Console.WriteLine(y);
      Console.ReadLine();
    }
    static bool IsPrime(long number)
    {
      //check for evenness
      if (number % 2 == 0)
      {
        if (number == 2)
        {
          return true;
        }
        return false;
      }
      //don't need to check past the square root
      long max = (long)Math.Sqrt(number);
      for (int i = 3; i <= max; i += 2)
      {
        if ((number % i) == 0)
        {
          return false;
        }
      }
      return true;
    }

  }
}
Симус Барретт
источник
0
#python implementation
import math
n = 600851475143
i = 2
factors=set([])
while i<math.sqrt(n):
   while n%i==0:
       n=n/i
       factors.add(i)
   i+=1
factors.add(n)
largest=max(factors)
print factors
print largest
Ришабх Прасад
источник
1
25 является самым большим основным фактором 25?
Уилл Несс
0

Вычисляет наибольший простой множитель числа, используя рекурсию в C ++. Работа кода объясняется ниже:

int getLargestPrime(int number) {
    int factor = number; // assumes that the largest prime factor is the number itself
    for (int i = 2; (i*i) <= number; i++) { // iterates to the square root of the number till it finds the first(smallest) factor
        if (number % i == 0) { // checks if the current number(i) is a factor
            factor = max(i, number / i); // stores the larger number among the factors
            break; // breaks the loop on when a factor is found
        }
    }
    if (factor == number) // base case of recursion
        return number;
    return getLargestPrime(factor); // recursively calls itself
}
4aRk Kn1gh7
источник
0

Вот мой подход к быстрому вычислению наибольшего простого множителя. Он основан на том факте, что модифицированные xне содержат не простых факторов. Чтобы достичь этого, мы делим, xкак только фактор найден. Тогда остается только вернуть самый большой фактор. Это было бы уже премьер.

Код (Haskell):

f max' x i | i > x = max'
           | x `rem` i == 0 = f i (x `div` i) i  -- Divide x by its factor
           | otherwise = f max' x (i + 1)  -- Check for the next possible factor

g x = f 2 x 2
Пеньковский
источник
но разве это не попытается разделить все четные числа тоже?
Янус Троелсен
0

Следующий алгоритм C ++ не самый лучший, но он работает для чисел до миллиарда и довольно быстрый

#include <iostream>
using namespace std;

// ------ is_prime ------
// Determines if the integer accepted is prime or not
bool is_prime(int n){
    int i,count=0;
    if(n==1 || n==2)
      return true;
    if(n%2==0)
      return false;
    for(i=1;i<=n;i++){
    if(n%i==0)
        count++;
    }
    if(count==2)
      return true;
    else
      return false;
 }
 // ------ nextPrime -------
 // Finds and returns the next prime number
 int nextPrime(int prime){
     bool a = false;
     while (a == false){
         prime++;
         if (is_prime(prime))
            a = true;
     }
  return prime;
 }
 // ----- M A I N ------
 int main(){

      int value = 13195;
      int prime = 2;
      bool done = false;

      while (done == false){
          if (value%prime == 0){
             value = value/prime;
             if (is_prime(value)){
                 done = true;
             }
          } else {
             prime = nextPrime(prime);
          }
      }
        cout << "Largest prime factor: " << value << endl;
 }
зп
источник
0

Нашел это решение в сети "Джеймс Ван"

public static int getLargestPrime( int number) {

    if (number <= 1) return -1;

    for (int i = number - 1; i > 1; i--) {
        if (number % i == 0) {
            number = i;
        }
    }
    return number;
}
BabarBaig
источник
0

Главный фактор с использованием сита:

#include <bits/stdc++.h>
using namespace std;
#define N 10001  
typedef long long ll;
bool visit[N];
vector<int> prime;

void sieve()
{
            memset( visit , 0 , sizeof(visit));
            for( int i=2;i<N;i++ )
            {
                if( visit[i] == 0)
                {
                    prime.push_back(i);
                    for( int j=i*2; j<N; j=j+i )
                    {
                        visit[j] = 1;
                    }
                }
            }   
}
void sol(long long n, vector<int>&prime)
{
            ll ans = n;
            for(int i=0; i<prime.size() || prime[i]>n; i++)
            {
                while(n%prime[i]==0)
                {
                    n=n/prime[i];
                    ans = prime[i];
                }
            }
            ans = max(ans, n);
            cout<<ans<<endl;
}
int main() 
{
           ll tc, n;
           sieve();

           cin>>n;
           sol(n, prime);

           return 0;
}
rashedcs
источник
-1

Мне кажется, что шаг № 2 данного алгоритма не будет таким уж эффективным подходом. У вас нет разумных ожиданий, что оно простое.

Кроме того, предыдущий ответ, предполагающий сито Эратосфена, совершенно неверен. Я просто написал две программы с множителем 123456789. Одна была основана на сите, другая - на следующем:

1)  Test = 2 
2)  Current = Number to test 
3)  If Current Mod Test = 0 then  
3a)     Current = Current Div Test 
3b)     Largest = Test
3c)     Goto 3. 
4)  Inc(Test) 
5)  If Current < Test goto 4
6)  Return Largest

Эта версия была в 90 раз быстрее, чем сито.

Дело в том, что на современных процессорах тип операции имеет гораздо меньшее значение, чем количество операций, не говоря уже о том, что приведенный выше алгоритм может выполняться в кеше, а Sieve - нет. Сито использует много операций, вычеркивая все составные числа.

Также обратите внимание, что мои факторы разделения по мере их выявления уменьшают пространство, которое необходимо проверить.

Лорен Печтель
источник
это то, что я сказал, но получил отказ :( Я думаю, проблема в том, что если число имеет действительно большой простой фактор (такой как он сам), то этот метод должен пройти весь цикл до этого числа. Во многих случаях хотя этот метод довольно эффективен
Nickf
Чтение через ваше это то же самое, но первая часть вас сбивает с толку.
Лорен Печтел
Попробуйте это по этому номеру 143816789988504044536402352738195137863656439, дайте мне знать, насколько это эффективно ...
MichaelICE
-1

Сначала вычислите список, хранящий простые числа, например, 2 3 5 7 11 13 ...

Каждый раз, когда вы делите число на простые числа, используйте реализацию от Triptych, но итерируйте этот список простых чисел, а не натуральные целые числа.

guoger
источник
-1

С Java:

Для intзначений:

public static int[] primeFactors(int value) {
    int[] a = new int[31];
    int i = 0, j;
    int num = value;
    while (num % 2 == 0) {
        a[i++] = 2;
        num /= 2;
    }
    j = 3;
    while (j <= Math.sqrt(num) + 1) {
        if (num % j == 0) {
            a[i++] = j;
            num /= j;
        } else {
            j += 2;
        }
    }
    if (num > 1) {
        a[i++] = num;
    }
    int[] b = Arrays.copyOf(a, i);
    return b;
}

Для longзначений:

static long[] getFactors(long value) {
    long[] a = new long[63];
    int i = 0;
    long num = value;
    while (num % 2 == 0) {
        a[i++] = 2;
        num /= 2;
    }
    long j = 3;
    while (j <= Math.sqrt(num) + 1) {
        if (num % j == 0) {
            a[i++] = j;
            num /= j;
        } else {
            j += 2;
        }
    }
    if (num > 1) {
        a[i++] = num;
    }
    long[] b = Arrays.copyOf(a, i);
    return b;
}
Пол Варгас
источник
-2

Вероятно, это не всегда быстрее, но более оптимистично в отношении того, что вы найдете большой простой делитель:

  1. N твой номер
  2. Если это простое, то return(N)
  3. Рассчитать простые числа до Sqrt(N)
  4. Пройдите через простые числа в порядке убывания (сначала по величине)
    • Если N is divisible by PrimeтогдаReturn(Prime)

Редактировать: На шаге 3 вы можете использовать Сито Эратосфена или Сито Аткинса или все, что вам нравится, но само по себе сито не найдет вас самым большим главным фактором. (Вот почему я не выбрал бы пост SQLMenace в качестве официального ответа ...)

palotasb
источник
1
Вам не нужно выполнять пробный факторинг, чтобы определить, является ли оно простым числом (шаг 2)? Также рассмотрите возможность нахождения наибольшего простого множителя из 15. Простые числа до sqrt (15) равны 2 и 3; но самый большой главный фактор - 5, не так ли? Аналогично с 20.
Джонатан Леффлер
-3

Я думаю, что было бы хорошо хранить где-нибудь все возможные простые числа, меньшие, чем n, и просто перебирать их, чтобы найти самый большой делитель. Вы можете получить простые числа от prime-numbers.org .

Конечно, я предполагаю, что ваш номер не слишком большой :)

Klesk
источник
-3

Не самый быстрый, но это работает!

    static bool IsPrime(long num)
    {
        long checkUpTo = (long)Math.Ceiling(Math.Sqrt(num));
        for (long i = 2; i <= checkUpTo; i++)
        {
            if (num % i == 0)
                return false;
        }
        return true;
    }
Ник
источник
Это не ответ на вопрос. ;-) Вопрос был в том, чтобы найти наибольший простой фактор, а не проверять на простоту.
Ганс-Петер Стёрр
Гораздо эффективнее инициализировать ваш цикл следующим образом: (long i = 3; i <checkUpTo; i + = 2)
cjk
-3

Вот та же функция @ Triptych, что и генератор, которая также немного упрощена.

def primes(n):
    d = 2
    while (n > 1):
        while (n%d==0):
            yield d
            n /= d
        d += 1

максимальное простое число может быть найдено с помощью:

n= 373764623
max(primes(n))

и список факторов, найденных с использованием:

list(primes(n))
Педрам
источник
-6
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include <time.h>

factor(long int n)
{
long int i,j;
while(n>=4)
 {
if(n%2==0) {  n=n/2;   i=2;   }

 else
 { i=3;
j=0;
  while(j==0)
  {
   if(n%i==0)
   {j=1;
   n=n/i;
   }
   i=i+2;
  }
 i-=2;
 }
 }
return i;
 }

 void main()
 { 
  clock_t start = clock();
  long int n,sp;
  clrscr();
  printf("enter value of n");
  scanf("%ld",&n);
  sp=factor(n);
  printf("largest prime factor is %ld",sp);

  printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
  getch();
 }
Chitransh
источник