Algoritma untuk menemukan faktor prima terbesar dari sebuah angka

Apa pendekatan terbaik untuk menghitung faktor prima terbesar dari suatu angka?

Saya pikir yang paling efisien adalah sebagai berikut:

1. Temukan bilangan prima terendah yang membagi dengan bersih
2. Periksa apakah hasil pembagiannya prima
3. Jika tidak, cari yang terendah berikutnya
4. Pergi ke 2.

Saya mendasarkan asumsi ini pada hal itu menjadi lebih mudah untuk menghitung faktor prima kecil. Apakah ini benar? Pendekatan apa lagi yang harus saya perhatikan?

Sunting: Saya sekarang menyadari bahwa pendekatan saya sia-sia jika ada lebih dari 2 faktor utama dalam permainan, karena langkah 2 gagal ketika hasilnya adalah produk dari dua bilangan prima lainnya, oleh karena itu diperlukan algoritma rekursif.

Sunting lagi: Dan sekarang saya menyadari bahwa ini masih berfungsi, karena bilangan prima yang ditemukan terakhir harus menjadi bilangan tertinggi, oleh karena itu setiap pengujian lebih lanjut terhadap hasil non-prima dari langkah 2 akan menghasilkan bilangan prima yang lebih kecil.

Sebenarnya ada beberapa cara yang lebih efisien untuk menemukan faktor angka besar (untuk divisi percobaan yang lebih kecil berfungsi dengan baik).

Salah satu metode yang sangat cepat jika nomor input memiliki dua faktor yang sangat dekat dengan akar kuadratnya dikenal sebagai faktorisasi kulit . Itu memanfaatkan identitas N = (a + b) (a - b) = a ^ 2 - b ^ 2 dan mudah dimengerti dan diimplementasikan. Sayangnya itu tidak terlalu cepat secara umum.

Metode yang paling terkenal untuk menghitung angka hingga 100 digit adalah Saringan kuadratik . Sebagai bonus, bagian dari algoritma mudah dilakukan dengan pemrosesan paralel.

Algoritma lain yang pernah saya dengar adalah algoritma Rho Pollard . Ini tidak seefisien Saringan Quadratic secara umum tetapi tampaknya lebih mudah untuk diterapkan.

Setelah Anda memutuskan cara membagi angka menjadi dua faktor, berikut adalah algoritma tercepat yang dapat saya pikirkan untuk menemukan faktor prima terbesar dari sebuah angka:

Buat antrian prioritas yang awalnya menyimpan nomor itu sendiri. Setiap iterasi, Anda menghapus angka tertinggi dari antrian, dan mencoba untuk membaginya menjadi dua faktor (tentu saja 1 tidak menjadi salah satu faktor itu). Jika langkah ini gagal, angkanya prima dan Anda memiliki jawaban! Kalau tidak, Anda menambahkan dua faktor ke dalam antrian dan ulangi.

Inilah algoritma terbaik yang saya tahu (dengan 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

Metode di atas berjalan dalam O(n)kasus terburuk (ketika input adalah bilangan prima).

EDIT:
Di bawah ini adalah O(sqrt(n))versi, seperti yang disarankan dalam komentar. Ini kodenya, sekali lagi.

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

Jawaban saya didasarkan pada Triptych , tetapi meningkatkan banyak di atasnya. Ini didasarkan pada fakta bahwa di luar 2 dan 3, semua bilangan prima adalah dari bentuk 6n-1 atau 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;
}

Baru-baru ini saya menulis artikel blog menjelaskan cara kerja algoritma ini.

Saya berani memberanikan diri bahwa suatu metode di mana tidak perlu untuk tes primality (dan tidak ada konstruksi ayakan) akan berjalan lebih cepat daripada yang menggunakan itu. Jika itu masalahnya, ini mungkin merupakan algoritma tercepat di sini.

Kode 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;
}

Contoh Penggunaan:

let result = largestPrimeFactor(600851475143);

Berikut ini contoh kode :

Mirip dengan jawaban @ Triptych tetapi juga berbeda. Dalam contoh ini daftar atau kamus tidak digunakan. Kode ditulis dalam 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

Semua angka dapat dinyatakan sebagai produk bilangan prima, misalnya:

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

Anda dapat menemukan ini dengan hanya mulai dari 2 dan hanya melanjutkan untuk membagi sampai hasilnya bukan kelipatan dari nomor Anda:

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

menggunakan metode ini Anda tidak harus benar-benar menghitung bilangan prima: semuanya akan menjadi bilangan prima, berdasarkan fakta bahwa Anda telah memfaktorkan angka sebanyak mungkin dengan semua angka sebelumnya.

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
    }

Solusi paling sederhana adalah sepasang fungsi yang saling rekursif .

Fungsi pertama menghasilkan semua bilangan prima:

1. Mulailah dengan daftar semua bilangan asli yang lebih besar dari 1.
2. Hapus semua angka yang tidak prima. Artinya, angka yang tidak memiliki faktor prima (selain diri mereka sendiri). Lihat di bawah.

Fungsi kedua mengembalikan faktor prima dari angka yang diberikan ndalam urutan yang meningkat.

1. Ambil daftar semua bilangan prima (lihat di atas).
2. Hapus semua angka yang bukan merupakan faktor n.

Faktor prima terbesar nadalah angka terakhir yang diberikan oleh fungsi kedua.

Algoritma ini membutuhkan daftar malas atau bahasa (atau struktur data) dengan semantik panggilan-oleh-kebutuhan .

Untuk klarifikasi, berikut adalah salah satu (tidak efisien) implementasi di atas dalam 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

Membuat ini lebih cepat hanya masalah menjadi lebih pintar dalam mendeteksi nomor mana yang prima dan / atau faktor n, tetapi algoritma tetap sama.

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)

Ada beberapa tes modulo yang superflous, karena n tidak pernah dapat dibagi dengan 6 jika semua faktor 2 dan 3 telah dihapus. Anda hanya dapat mengizinkan bilangan prima untuk i, yang ditunjukkan dalam beberapa jawaban lain di sini.

Anda dapat benar-benar menjalin saringan Eratosthenes di sini:

• Pertama buat daftar bilangan bulat hingga sqrt (n).
• Dalam for loop tandai semua kelipatan i hingga sqrt baru (n) sebagai bukan prime, dan gunakan loop sementara sebagai gantinya.
• atur i ke nomor utama berikutnya dalam daftar.

Lihat juga pertanyaan ini .

Saya sadar ini bukan solusi cepat. Posting semoga mudah dipahami sebagai solusi lambat.

 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;
    } 

Pendekatan Python Iterative dengan menghapus semua faktor utama dari nomor tersebut

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

Saya menggunakan algoritma yang terus membagi angka dengan Prime Factor saat ini.

Solusi saya di 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()))) 

Input: 10 Keluaran:5

Input: 600851475143 Keluaran:6857

Ini adalah usaha saya di c #. Hasil cetak terakhir adalah faktor utama nomor tersebut. Saya memeriksa dan berfungsi.

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

Menghitung faktor prima terbesar dari angka menggunakan rekursi dalam C ++. Cara kerja kode dijelaskan di bawah ini:

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
}

Inilah pendekatan saya untuk dengan cepat menghitung faktor prima terbesar. Hal ini didasarkan pada fakta bahwa modifikasi xtidak mengandung faktor non-prima. Untuk mencapai itu, kami membagix segera setelah faktor ditemukan. Kemudian, satu-satunya yang tersisa adalah mengembalikan faktor terbesar. Itu sudah prima.

Kode (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

Algoritma C ++ berikut ini bukan yang terbaik, tetapi bekerja untuk angka di bawah satu miliar dan cukup cepat

#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;
 }

Menemukan solusi ini di web oleh "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;
}

Faktor utama menggunakan saringan:

#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;
}

Sepertinya saya bahwa langkah # 2 dari algoritma yang diberikan tidak akan menjadi semua pendekatan yang efisien. Anda tidak memiliki harapan yang masuk akal bahwa itu prima.

Juga, jawaban sebelumnya yang menyarankan Saringan Eratosthenes sama sekali salah. Saya baru saja menulis dua program ke faktor 123456789. Satu didasarkan pada Saringan, satu didasarkan pada yang berikut:

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

Versi ini 90x lebih cepat dari Saringan.

Masalahnya, pada prosesor modern jenis operasi lebih penting daripada jumlah operasi, belum lagi bahwa algoritma di atas dapat berjalan dalam cache, Saringan tidak bisa. Saringan menggunakan banyak operasi yang mencoret semua angka komposit.

Perhatikan juga, bahwa faktor-faktor pemisah saya sebagaimana mereka diidentifikasi mengurangi ruang yang harus diuji.

Hitunglah daftar yang menyimpan bilangan prima terlebih dahulu, misalnya 2 3 5 7 11 13 ...

Setiap kali Anda memfaktorkan angka, gunakan implementasi oleh Triptych tetapi iterasi daftar bilangan prima ini bukan bilangan bulat alami.

Dengan Java:

Untuk intnilai:

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;
}

Untuk longnilai:

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;
}

Ini mungkin tidak selalu lebih cepat tetapi lebih optimis bahwa Anda menemukan pembagi utama yang besar:

1. N adalah nomor kamu
2. Jika itu prima maka return(N)
3. Hitung bilangan prima hingga Sqrt(N)
4. Pergi melalui bilangan prima dalam urutan menurun (terbesar pertama)
   • Jika N is divisible by PrimedemikianReturn(Prime)

Sunting: Pada langkah 3 Anda dapat menggunakan Saringan Eratosthenes atau Saringan Atkins atau apa pun yang Anda suka, tetapi dengan sendirinya saringan tidak akan menemukan Anda faktor utama terbesar. (Itulah sebabnya saya tidak akan memilih posting SQLMenace sebagai jawaban resmi ...)

Saya pikir akan lebih baik untuk menyimpan di suatu tempat semua kemungkinan bilangan prima lebih kecil daripada n dan hanya beralih melalui mereka untuk menemukan divisior terbesar. Anda bisa mendapatkan bilangan prima dari prime-numbers.org .

Tentu saja saya berasumsi bahwa nomor Anda tidak terlalu besar :)

Bukan yang tercepat tetapi berhasil!

    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;
    }

Berikut adalah fungsi yang sama dengan @ Triptych yang disediakan sebagai generator, yang juga sedikit disederhanakan.

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

max prime kemudian dapat ditemukan menggunakan:

n= 373764623
max(primes(n))

dan daftar faktor yang ditemukan menggunakan:

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();
 }