خوارزمية للعثور على أكبر عامل أولي لرقم
https://stackoverflow.com/questions/23287
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
ما هي أفضل طريقة لحساب أكبر عامل أولي لعدد ما؟
أعتقد أن الأكثر فعالية هو ما يلي:
- ابحث عن أقل عدد أولي يقبل القسمة بشكل صحيح
- تحقق مما إذا كانت نتيجة القسمة أولية
- إذا لم يكن الأمر كذلك، فابحث عن الأدنى التالي
- اذهب إلى 2.
أنا أبني هذا الافتراض على أنه من الأسهل حساب العوامل الأولية الصغيرة.هل هذا عن الحق؟ما هي الأساليب الأخرى التي يجب علي النظر فيها؟
يحرر:لقد أدركت الآن أن نهجي غير مجدي إذا كان هناك أكثر من عاملين أوليين في اللعب، نظرًا لأن الخطوة 2 تفشل عندما تكون النتيجة حاصل ضرب عددين أوليين آخرين، وبالتالي هناك حاجة إلى خوارزمية متكررة.
تحرير مرة أخرى:والآن أدركت أن هذا لا يزال يعمل، لأن آخر رقم أولي تم العثور عليه يجب أن يكون الأعلى، وبالتالي فإن أي اختبار إضافي للنتيجة غير الأولية من الخطوة 2 سيؤدي إلى عدد أولي أصغر.
المحلول
في الواقع، هناك عدة طرق أكثر فعالية للعثور على عوامل الأعداد الكبيرة (بالنسبة للأصغر، يعمل قسم التجربة بشكل جيد إلى حد معقول).
تُعرف إحدى الطرق السريعة جدًا إذا كان لرقم الإدخال عاملين قريبين جدًا من جذره التربيعي باسم تحليل الفرما.إنها تستخدم الهوية N = (a + b)(a - b) = a^2 - b^2 وهي سهلة الفهم والتنفيذ.لسوء الحظ أنها ليست سريعة جدًا بشكل عام.
أفضل طريقة معروفة لتحليل الأعداد التي يصل طولها إلى 100 رقم هي غربال تربيعي.كمكافأة، يتم تنفيذ جزء من الخوارزمية بسهولة من خلال المعالجة المتوازية.
خوارزمية أخرى سمعت عنها هي خوارزمية رو بولارد.إنها ليست فعالة مثل المنخل التربيعي بشكل عام ولكن يبدو أنها أسهل في التنفيذ.
بمجرد أن تقرر كيفية تقسيم رقم إلى عاملين، فإليك أسرع خوارزمية يمكنني التفكير فيها للعثور على أكبر عامل أولي لرقم ما:
قم بإنشاء قائمة انتظار ذات أولوية تقوم في البداية بتخزين الرقم نفسه.في كل تكرار، تقوم بإزالة أعلى رقم من قائمة الانتظار، وتحاول تقسيمه إلى عاملين (لا تسمح للرقم 1 بأن يكون أحد هذه العوامل بالطبع).إذا فشلت هذه الخطوة، فإن العدد أولي ولديك إجابتك!وإلا فإنك تضيف العاملين إلى قائمة الانتظار وتكرر الأمر.
نصائح أخرى
إليك أفضل خوارزمية أعرفها (في بايثون)
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;
}
لقد كتبت مؤخرًا أ مقالة مدونة وشرح كيفية عمل هذه الخوارزمية.
وأجرؤ على أن الطريقة التي لا توجد فيها حاجة لاختبار البدائية (ولا يوجد بناء غربال) ستعمل بشكل أسرع من الطريقة التي تستخدم تلك.إذا كان الأمر كذلك، فمن المحتمل أن تكون هذه هي الخوارزمية الأسرع هنا.
كود جافا سكريبت:
'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 ولكنها مختلفة أيضًا.في هذا المثال، لم يتم استخدام القائمة أو القاموس.الكود مكتوب بلغة روبي
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 هو الرقم الأخير الذي تعطيه الدالة الثانية.
تتطلب هذه الخوارزمية أ قائمة كسول أو لغة (أو بنية بيانات) مع دعوة حسب الحاجة دلالات.
للتوضيح، إليك تطبيق (غير فعال) لما ورد أعلاه في هاسكل:
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).
- في حلقة علامة ، جميع مضاعفات I حتى SQRT الجديدة (N) ليست Prime ، واستخدم حلقة الوقت بدلاً من ذلك.
- قم بتعيين 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
أنا أستخدم الخوارزمية التي تستمر في تقسيم الرقم على العامل الرئيسي الحالي.
الحل الخاص بي في بيثون 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 بمجرد العثور على عامل.ومن ثم، الشيء الوحيد المتبقي هو إرجاع العامل الأكبر.سيكون رئيسًا بالفعل.
الكود (هاسكل):
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 ولكن قم بتكرار قائمة الأعداد الأولية هذه بدلاً من الأعداد الصحيحة الطبيعية.
مع جافا:
ل 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();
}
