Mencari bilangan pembagi suatu bilangan bulat besar menggunakan faktorisasi prima/kuadrat (C#)

Saya mencoba mendapatkan jumlah pembagi bilangan bulat 64 bit (lebih besar dari 32 bit)

Cara pertama saya (untuk bilangan kecil) adalah dengan membagi bilangan tersebut hingga diperoleh bilangan 1, hitung banyaknya bilangan prima yang cocok dan gunakan rumus (1 + P1)(1+ P2)..* (1 + Pn) = Jumlah pembagi

Misalnya:

24 = 2*2*2*3 = 2^3 * 3^1

==> (3 + 1)*(1 + 1) = 4 * 2 = 8 pembagi

        public static long[] GetPrimeFactor(long number)
        {
            bool Found = false;
            long i = 2;
            List<long> Primes = new List<long>();
            while (number > 1)
            {
                if (number % i == 0)
                {
                    number /= i;
                    Primes.Add(i);
                    i = 1;
                }
                i++;
            }
            return Primes.ToArray();
        }

Namun untuk bilangan bulat besar, metode ini memerlukan banyak iterasi. Saya menemukan metode bernama Saringan kuadrat untuk membuat faktorisasi menggunakan angka persegi. Sekarang menggunakan skrip saya ini bisa lebih mudah karena jumlahnya jauh lebih kecil.

Pertanyaan saya adalah, bagaimana cara menerapkan Saringan Kuadrat ini?


quadratic factorization primes sieve
person Bartemis    schedule 22.03.2015    source sumber
comment
Anda harus menulis program besar, dan pertanyaan Anda terlalu luas.   -  person President James K. Polk    schedule 22.03.2015
comment
Pertanyaan saya adalah pseudocode untuk saringan kuadrat, itu bukan program yang besar bukan?   -  person Bartemis    schedule 22.03.2015

Jawaban (1)


arrow_upward
2
arrow_downward

Saringan kuadrat adalah metode mencari faktor besar dalam jumlah besar; pikirkan 10^75, bukan 2^64. Saringan kuadratik rumit bahkan dalam bentuk pseudocode sederhana, dan jauh lebih rumit jika Anda ingin efisien. Ini sangat berlebihan untuk bilangan bulat 64-bit, dan akan lebih lambat dibandingkan metode lain yang dikhususkan untuk bilangan kecil tersebut.

Jika pembagian percobaan terlalu lambat bagi Anda, langkah berikutnya dalam kompleksitas adalah metode rho John Pollard; untuk bilangan bulat 64-bit, Anda mungkin ingin membagi percobaan hingga batas kecil, mungkin bilangan prima kurang dari seribu, lalu beralih ke rho. Berikut pseudocode sederhana untuk menemukan faktor tunggal dari n; sebutkan berulang kali pada kofaktor komposit untuk menyelesaikan faktorisasi:

function factor(n, c=1)
    if n % 2 == 0 return 2
    h := 1; t := 1
    repeat
        h := (h*h+c) % n
        h := (h*h+c) % n
        t := (t*t+c) % n
        g := gcd(t-h, n)
    while g == 1
    if g is prime return g
    return factor(g, c+1)

Ada cara lain untuk memfaktorkan bilangan bulat 64-bit, tapi ini akan membantu Anda memulai, dan mungkin cukup untuk sebagian besar tujuan; Anda dapat mencari varian algoritma rho Richard Brent untuk mempercepatnya. Jika Anda ingin tahu lebih banyak, saya dengan rendah hati merekomendasikan esai Pemrograman dengan Bilangan Prima di blog saya.

person user448810    schedule 23.03.2015