Алгоритм нахождения наибольшего простого множителя числа
https://stackoverflow.com/questions/23287
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Каков наилучший подход к вычислению наибольшего простого множителя числа?
Я думаю, что наиболее эффективным было бы следующее:
- Найдите наименьшее простое число, которое делится чисто
- Проверьте, является ли результат деления простым
- Если нет, найдите следующий самый низкий
- Перейдите к пункту 2.
Я основываю это предположение на том, что проще вычислить малые простые множители.Правильно ли это?Какие еще подходы мне следует рассмотреть?
Редактировать:Теперь я понял, что мой подход бесполезен, если в игре задействовано более 2 простых множителей, поскольку шаг 2 завершается неудачей, когда результат является произведением двух других простых чисел, поэтому необходим рекурсивный алгоритм.
Отредактируйте еще раз:И теперь я понял, что это все еще работает, потому что последнее найденное простое число должно быть самым высоким, поэтому любое дальнейшее тестирование не простого результата с шага 2 приведет к меньшему простому числу.
Решение
На самом деле есть несколько более эффективных способов нахождения множителей с большими числами (для меньших пробное деление работает достаточно хорошо).
Один из методов, который выполняется очень быстро, если входное число имеет два множителя, очень близких к его квадратному корню, известен как Факторизация Ферма.Он использует тождество N = (a + b) (a - b) = a ^ 2 - b ^ 2 и прост в понимании и реализации.К сожалению, в целом это происходит не очень быстро.
Наиболее известным методом факторизации чисел длиной до 100 цифр является Квадратное сито.В качестве бонуса, часть алгоритма легко выполняется с помощью параллельной обработки.
Еще один алгоритм, о котором я слышал, это Алгоритм Rho Полларда.Это не так эффективно, как Квадратное сито в целом, но, кажется, проще в реализации.
После того, как вы определились с тем, как разделить число на два множителя, вот самый быстрый алгоритм, который я могу придумать, чтобы найти наибольший простой множитель числа:
Создайте приоритетную очередь, в которой изначально хранится сам номер.На каждой итерации вы удаляете наибольшее число из очереди и пытаетесь разделить его на два фактора (разумеется, не допуская, чтобы 1 был одним из этих факторов).Если этот шаг завершится неудачей, число будет простым, и вы получите свой ответ!В противном случае вы добавляете два фактора в очередь и повторяете.
Другие советы
Вот лучший алгоритм, который я знаю (на 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
Мой ответ основан на Триптих's, но значительно улучшает его.Он основан на том факте, что, кроме 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;
}
Недавно я написал статья в блоге объясняю, как работает этот алгоритм.
Я бы рискнул предположить, что метод, в котором нет необходимости в тестировании на простоту (и нет конструкции сита), будет работать быстрее, чем тот, который их использует.Если это так, то это, вероятно, самый быстрый алгоритм здесь.
Код 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);
Все числа могут быть выражены как произведение простых чисел, например:
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.
}
//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
}
Похоже на ответ @Triptych, но в то же время отличается.В этом примере список или словарь не используются.Код написан на Ruby
def largest_prime_factor(number)
i = 2
while number > 1
if number % i == 0
number /= i;
i -= 1
end
i += 1
end
return i
end
largest_prime_factor(600851475143)
# => 6857
Самым простым решением является пара взаимно рекурсивные функции.
Первая функция генерирует все простые числа:
- Начните со списка всех натуральных чисел, больших 1.
- Удалите все числа, которые не являются простыми.То есть числа, у которых нет простых множителей (кроме самих себя).Смотрите ниже.
Вторая функция возвращает простые множители заданного числа n в порядке возрастания.
- Возьмите список всех простых чисел (см. Выше).
- Удалите все числа, которые не являются множителями
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, но алгоритм остается прежним.
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) как not простые и используйте вместо этого цикл while.
- установите i в качестве следующего простого числа в списке.
Также смотрите этот вопрос.
Я знаю, что это не быстрое решение.Публикую как, надеюсь, более простое для понимания медленное решение.
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;
}
Итеративный подход 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
Я использую алгоритм, который продолжает делить число на его текущий простой множитель.
Мое решение на 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
Вот моя попытка на 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;
}
}
}
#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
Вычисляет наибольший простой множитель числа, используя рекурсию в 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
}
Вот мой подход к быстрому вычислению наибольшего простого множителя.Это основано на том факте, что модифицированный 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
Следующий алгоритм 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;
}
Нашел это решение в Интернете от "Джеймса Вана".
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;
}
Основной фактор с использованием сита :
#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;
}
Мне кажется, что шаг № 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 раз быстрее, чем предыдущая.
Дело в том, что на современных процессорах тип операции имеет гораздо меньшее значение, чем количество операций, не говоря уже о том, что приведенный выше алгоритм может выполняться в кэше, Сито - нет.Сито использует множество операций, вычеркивающих все составные числа.
Обратите также внимание, что мое разделение факторов по мере их идентификации уменьшает пространство, которое необходимо протестировать.
Сначала вычислите список, хранящий простые числа, например2 3 5 7 11 13 ...
Каждый раз, когда вы разлагаете число на простые множители, используйте реализацию с помощью Triptych, но повторяйте этот список простых чисел, а не натуральных целых.
С 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;
}
Вероятно, это не всегда быстрее, но более оптимистично в отношении того, что вы находите большой простой делитель:
Nэто ваш номер- Если оно простое, то
return(N) - Вычисляйте простые числа до тех пор, пока
Sqrt(N) - Пройдите по простым числам в порядке убывания (сначала самое большое).
- Если
N is divisible by PrimeтогдаReturn(Prime)
- Если
Редактировать:На шаге 3 вы можете использовать сито Эратосфена, или сито Аткинса, или что угодно еще, но само по себе сито не найдет для вас самого большого простого множителя.(Вот почему я бы не выбрал сообщение SQLMenace в качестве официального ответа ...)
Я думаю, было бы неплохо сохранить где-нибудь все возможные простые числа, меньшие n, и просто перебирать их, чтобы найти наибольшее деление.Вы можете получить простые числа из prime-numbers.org.
Конечно, я предполагаю, что ваше число не слишком велико :)
Не самый быстрый, но это работает!
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;
}
Вот та же функция @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))
#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();
}
