Wat is de beste manier om de grootste priemfactor van een getal te berekenen?
Ik denk dat het volgende het meest efficiënt zou zijn:
- Zoek het laagste priemgetal dat netjes deelt
- Controleer of het resultaat van de deling een priemgetal is
- Zo niet, zoek de volgende laagste
- Ga naar 2.
Ik baseer deze veronderstelling op het feit dat het gemakkelijker is om de kleine priemfactoren te berekenen. Klopt dit ongeveer? Naar welke andere benaderingen moet ik kijken?
Bewerken: ik heb me nu gerealiseerd dat mijn aanpak zinloos is als er meer dan 2 priemfactoren in het spel zijn, aangezien stap 2 mislukt wanneer het resultaat een product is van twee andere priemgetallen, en daarom is een recursief algoritme nodig.
p>
Opnieuw bewerken: en nu realiseer ik me dat dit nog steeds werkt, omdat het laatst gevonden priemgetal het hoogste moet zijn, daarom zou elke verdere test van het niet-priemgetal uit stap 2 resulteren in een kleiner priemgetal .
Antwoord 1, autoriteit 100%
Eigenlijk zijn er verschillende efficiëntere manieren om factoren van grote getallen te vinden (voor kleinere werkt proefdeling redelijk goed).
Een methode die erg snel is als het invoergetal twee factoren heeft die heel dicht bij de vierkantswortel liggen, staat bekend als Fermat factorisatie. Het maakt gebruik van de identiteit N = (a + b)(a – b) = a^2 – b^2 en is gemakkelijk te begrijpen en te implementeren. Helaas is het over het algemeen niet erg snel.
De bekendste methode voor het ontbinden van getallen tot 100 cijfers is de Kwadratische zeef. Als bonus is een deel van het algoritme eenvoudig te doen met parallelle verwerking.
Nog een ander algoritme waar ik van gehoord heb, is Pollard’s Rho-algoritme. Het is niet zo efficiënt als de Quadratic Sieve in het algemeen, maar lijkt gemakkelijker te implementeren.
Als je eenmaal hebt besloten hoe je een getal in twee factoren wilt splitsen, is hier het snelste algoritme dat ik kan bedenken om de grootste priemfactor van een getal te vinden:
Maak een prioriteitswachtrij waarin het nummer in eerste instantie zelf wordt opgeslagen. Bij elke iteratie verwijdert u het hoogste getal uit de wachtrij en probeert u het in twee factoren te splitsen (uiteraard niet toestaand dat 1 een van die factoren is). Als deze stap mislukt, is het getal een priemgetal en heb je je antwoord! Anders voegt u de twee factoren toe aan de wachtrij en herhaalt u.
Antwoord 2, autoriteit 92%
Dit is het beste algoritme dat ik ken (in 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
De bovenstaande methode wordt in het ergste geval uitgevoerd in O(n)(wanneer de invoer een priemgetal is).
BEWERKEN:
Hieronder staat de O(sqrt(n))-versie, zoals gesuggereerd in de opmerking. Hier is de code, nog een keer.
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
Antwoord 3, Autoriteit 13%
Mijn antwoord is gebaseerd op triptych ‘s, maar verbetert er veel op. Het is gebaseerd op het feit dat na 2 en 3 alle prime-nummers van de vorm 6N-1 of 6N + 1 zijn.
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;
}
Ik heb onlangs een blog artikel uitleggen Hoe dit algoritme werkt.
Ik waagde dat een methode waarin er geen behoefte is aan een test voor Primaliteit (en geen zeefconstructie) zou sneller draaien dan een die dat doet. Als dat het geval is, is dit waarschijnlijk het snelste algoritme hier.
Antwoord 4, Autoriteit 6%
JavaScript-code:
'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;
}
Gebruiksvoorbeeld:
let result = largestPrimeFactor(600851475143);
Hier is een voorbeeld van de code:
Antwoord 5, autoriteit 5%
Vergelijkbaar met @Triptych, maar ook anders. In dit voorbeeld wordt geen lijst of woordenboek gebruikt. Code is geschreven in 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
Antwoord 6, autoriteit 3%
Alle getallen kunnen worden uitgedrukt als het product van priemgetallen, bijvoorbeeld:
102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89
Je kunt deze vinden door simpelweg bij 2 te beginnen en gewoon door te gaan met delen totdat het resultaat geen veelvoud is van jouw getal:
712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1
met deze methode hoef je eigenlijk geen priemgetallen te berekenen: het zijn allemaal priemgetallen, gebaseerd op het feit dat je het getal al zoveel mogelijk hebt ontbonden met alle voorgaande getallen.
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.
}
Antwoord 7, autoriteit 3%
//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
}
Antwoord 8, autoriteit 3%
De eenvoudigste oplossing is een paar wederzijds recursievefuncties.
De eerste functie genereert alle priemgetallen:
- Begin met een lijst van alle natuurlijke getallen groter dan 1.
- Verwijder alle getallen die geen priemgetal zijn. Dat wil zeggen, getallen die geen priemfactoren hebben (behalve zijzelf). Zie hieronder.
De tweede functie retourneert de priemfactoren van een gegeven getal Nin oplopende volgorde.
- Maak een lijst van alle priemgetallen (zie hierboven).
- Verwijder alle getallen die geen factoren zijn van
N.
De grootste priemfactor van Nis het laatste getal dat door de tweede functie wordt gegeven.
Dit algoritme vereist een luie lijstof een taal (of datastructuur) met call-by-need-semantiek.
Ter verduidelijking, hier is een (inefficiënte) implementatie van het bovenstaande in 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
Dit sneller maken is gewoon een kwestie van slimmer om te detecteren welke nummers prime en / of factoren zijn van N, maar het algoritme blijft hetzelfde.
Antwoord 9, Autoriteit 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)
Er zijn enkele modulo-tests die superfliek zijn, zoals n nooit kan worden gedeeld door 6 als alle factoren 2 en 3 zijn verwijderd. Je zou alleen Primes voor I kunnen toestaan, die hier in verschillende andere antwoorden wordt getoond.
Je zou de zeef van Eratosthenes hier kunnen verwiepen:
- Maak eerst de lijst met gehele getallen
naarSqrt(N). - in de Loop Markeer alle veelvouden
van I tot aan de nieuweSqrt(N)AS Dat niet
Prime, en gebruik een tijdje lus in plaats daarvan. - set i naar het volgende prime nummer in
de lijst.
Zie ook deze vraag .
Antwoord 10
Ik weet dat dit geen snelle oplossing is. Posting als hopelijk eenvoudiger te begrijpen slow-oplossing.
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;
}
Antwoord 11
Python-iteratieve aanpak door alle primaire factoren uit het nummer
te verwijderen
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
Antwoord 12
Ik gebruik algoritme dat doorgaan met het verdelen van het nummer door de huidige prime-factor.
Mijn oplossing in 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())))
Invoer: 10
OUTPUT: 5
Invoer: 600851475143
Uitgang: 6857
Antwoord 13
Hier is mijn poging in C #. De laatste afdruk is de grootste primaire factor van het aantal. Ik heb gecontroleerd en het werkt.
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;
}
}
}
Antwoord 14
#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
Antwoord 15
Berekent de grootste prime-factor van een getal met behulp van recursie in C++. De werking van de code wordt hieronder uitgelegd:
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
}
Antwoord 16
Hier is mijn aanpak om snel de grootste prime-factor te berekenen.
Het is gebaseerd op feit dat gewijzigd xgeen niet-prime-factoren bevat. Om dat te bereiken, delen we xzodra een factor wordt gevonden. Dan is het enige dat nog over is om de grootste factor terug te sturen. Het zou al prime zijn.
De code (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
Antwoord 17
Het volgende C++ -algoritme is niet de beste, maar het werkt voor cijfers onder een miljard en het is vrij snel
#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;
}
Antwoord 18
Deze oplossing op internet gevonden door “James Wang”
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;
}
Antwoord 19
Priemfactor met zeef:
#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;
}
Antwoord 20
Denk dat er geen directe andere manier is dan een factorisatie uit te voeren, zoals bovenstaande voorbeelden hebben gedaan, d.w.z.
in een iteratie identificeer je een “kleine” factor fvan een getal Nen ga dan verder met het gereduceerde probleem “vind grootste priemfactor van N’ :=N/fmet factorkandidaten >=f“.
Vanaf een bepaalde grootte van fis de verwachte zoektijd korter, als u een priemtest doet op gereduceerde N’, wat in het geval bevestigt dat uw N’is al de grootste priemfactor van de initiële N.
Antwoord 21
Hier is mijn poging in Clojure. Alleen het lopen van de kansen voor prime?en de priemgetallen voor priemfactoren dwz. sieve. Het gebruik van luie reeksen helpt bij het produceren van de waarden net voordat ze nodig zijn.
(defn prime?
([n]
(let [oddNums (iterate #(+ % 2) 3)]
(prime? n (cons 2 oddNums))))
([n [i & is]]
(let [q (quot n i)
r (mod n i)]
(cond (< n 2) false
(zero? r) false
(> (* i i) n) true
:else (recur n is)))))
(def primes
(let [oddNums (iterate #(+ % 2) 3)]
(lazy-seq (cons 2 (filter prime? oddNums)))))
;; Sieve of Eratosthenes
(defn sieve
([n]
(sieve primes n))
([[i & is :as ps] n]
(let [q (quot n i)
r (mod n i)]
(cond (< n 2) nil
(zero? r) (lazy-seq (cons i (sieve ps q)))
(> (* i i) n) (when (> n 1) (lazy-seq [n]))
:else (recur is n)))))
(defn max-prime-factor [n]
(last (sieve n)))
Antwoord 22
Het lijkt mij die stap # 2 van het gegeven algoritme niet alles wat een efficiënte aanpak zal zijn. Je hebt geen redelijke verwachting dat het prime is.
Ook het vorige antwoord suggereert de zeef van Eratosthenes is volkomen verkeerd. Ik heb net twee programma’s geschreven op factor 123456789. Eén was gebaseerd op de zeef, men was gebaseerd op het volgende:
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
Deze versie was 90x sneller dan de zeef.
Het ding is, op moderne processors Het type bediening is veel minder belangrijk dan het aantal operaties, om nog maar te zwijgen over dat het bovenstaande algoritme in de cache kan draaien, de zeef niet. De zeef gebruikt veel operaties die alle composietnummers opvallen.
Noteer, ook dat mijn scheidingsfactoren zoals ze worden geïdentificeerd vermindert de ruimte die moet worden getest.
Antwoord 23
Bereken een lijst opslaan Prime Numbers eerst, b.v. 2 3 5 7 11 13 …
Telkens wanneer u een getal factoreeft, gebruikt u de implementatie door Triptych, maar deze lijst met prime-nummers in plaats van natuurlijke gehele getallen.
Antwoord 24
Met Java:
voor intwaarden:
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;
}
Voor longwaarden:
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;
}
Antwoord 25
Dit is waarschijnlijk niet altijd sneller, maar het is optimistischer dat je een grote priemdeler vindt:
Nis je nummer- Als het een priemgetal is, dan
return(N) - Bereken priemgetallen tot
Sqrt(N) - Doorloop de priemgetallen in aflopende volgorde (grootste eerst)
- Als
N is divisible by PrimedanReturn(Prime)
- Als
Bewerken: in stap 3 kun je de zeef van Eratosthenes of de zeef van Atkins of wat je maar wilt gebruiken, maar de zeef zelf zal je niet de grootste priemfactor vinden. (Daarom zou ik de post van SQLMenace niet als officieel antwoord kiezen…)
Antwoord 26
Hier is dezelfde functie@Triptych als generator, die ook iets vereenvoudigd is.
def primes(n):
d = 2
while (n > 1):
while (n%d==0):
yield d
n /= d
d += 1
het maximale priemgetal kan dan worden gevonden met:
n= 373764623
max(primes(n))
en een lijst met gevonden factoren met:
list(primes(n))
Antwoord 27
Ik denk dat het goed zou zijn om alle mogelijke priemgetallen kleiner dan n ergens op te slaan en ze gewoon te doorlopen om de grootste deler te vinden. U kunt priemgetallen krijgen van prime-numbers.org.
Natuurlijk neem ik aan dat je nummer niet te groot is 🙂
Antwoord 28
#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();
}