Apa yang akan menjadi algoritma paling optimal (kinerja-bijaksana) untuk menghitung jumlah pembagi nomor yang diberikan?

Akan sangat bagus jika Anda bisa memberikan pseudocode atau tautan ke beberapa contoh.

EDIT: Semua jawaban sangat membantu, terima kasih. Saya menerapkan Saringan Atkin dan kemudian saya akan menggunakan sesuatu yang mirip dengan apa yang ditunjukkan Jonathan Leffler. Tautan yang diposting oleh Justin Bozonier memiliki informasi lebih lanjut tentang apa yang saya inginkan.

Dmitriy benar bahwa Anda ingin Saringan Atkin untuk menghasilkan daftar utama tetapi saya tidak percaya bahwa mengurus seluruh masalah. Sekarang Anda memiliki daftar bilangan prima, Anda perlu melihat berapa banyak bilangan prima yang bertindak sebagai pembagi (dan seberapa sering).

Inilah beberapa python untuk algo. Lihat di sini dan cari "Subjek: matematika - perlu pembagi algoritma". Hanya menghitung jumlah item dalam daftar alih-alih mengembalikannya.

Ini adalah Dr. Math yang menjelaskan apa sebenarnya yang perlu Anda lakukan secara matematis.

Intinya nadalah angka jika angka Anda adalah:
n = a^x * b^y * c^z
(di mana a, b, dan c adalah pembagi utama n dan x, y, dan z adalah berapa kali pembagi diulang) maka jumlah total untuk semua pembagi adalah:
(x + 1) * (y + 1) * (z + 1).

Sunting: BTW, untuk menemukan a, b, c, dll. Anda akan ingin melakukan apa yang menjadi jumlah algo serakah jika saya memahami ini dengan benar. Mulailah dengan pembagi utama terbesar Anda dan kalikan dengan sendirinya sampai perkalian lebih lanjut akan melebihi angka n. Kemudian pindah ke faktor terendah berikutnya dan kalikan bilangan prima sebelumnya ^ kali dikalikan dengan bilangan prima saat ini dan teruskan mengalikan dengan bilangan prima sampai yang berikutnya akan melebihi n ... dll. Lacak berapa kali Anda mengalikan pembagi bersama dan menerapkan angka-angka itu ke dalam rumus di atas.

Tidak 100% yakin tentang deskripsi algo saya tetapi jika itu bukan sesuatu yang mirip.

Ada lebih banyak teknik untuk memfaktorkan daripada saringan Atkin. Sebagai contoh misalkan kita ingin memfaktorkan 5893. Yah, sqrt-nya adalah 76,76 ... Sekarang kita akan mencoba menulis 5893 sebagai produk kotak. Nah (77 * 77 - 5893) = 36 yang 6 kuadrat, jadi 5893 = 77 * 77 - 6 * 6 = (77 + 6) (77-6) = 83 * 71. Jika itu tidak berhasil, kita akan melihat apakah 78 * 78 - 5893 kotak yang sempurna. Dan seterusnya. Dengan teknik ini Anda dapat dengan cepat menguji faktor-faktor di dekat akar kuadrat dari n jauh lebih cepat daripada dengan menguji masing-masing bilangan prima. Jika Anda menggabungkan teknik ini untuk mengesampingkan bilangan prima besar dengan ayakan, Anda akan memiliki metode anjak jauh lebih baik daripada dengan ayakan saja.

Dan ini hanyalah salah satu dari sejumlah besar teknik yang telah dikembangkan. Ini cukup sederhana. Butuh waktu lama untuk belajar, katakanlah, cukup banyak teori untuk memahami teknik anjak piutang berdasarkan kurva eliptik. (Saya tahu mereka ada. Saya tidak mengerti mereka.)

Karena itu, kecuali jika Anda berurusan dengan bilangan bulat kecil, saya tidak akan mencoba menyelesaikan masalah itu sendiri. Sebaliknya saya akan mencoba mencari cara untuk menggunakan sesuatu seperti perpustakaan PARI yang sudah memiliki solusi yang sangat efisien diimplementasikan. Dengan itu saya dapat memasukkan 40 angka acak seperti 124321342332143213122323434312213424231341 dalam sekitar 0,05 detik. (Faktorisasi, jika Anda bertanya-tanya, adalah 29 * 439 * 1321 * 157907 * 284749 * 33843676813 * 4857795469949. Saya cukup yakin bahwa itu tidak mengetahui hal ini menggunakan saringan Atkin ...)

@Yasky

Fungsi pembagi Anda memiliki bug karena tidak berfungsi dengan benar untuk kuadrat sempurna.

Mencoba:

int divisors(int x) {
    int limit = x;
    int numberOfDivisors = 0;

    if (x == 1) return 1;

    for (int i = 1; i < limit; ++i) {
        if (x % i == 0) {
            limit = x / i;
            if (limit != i) {
                numberOfDivisors++;
            }
            numberOfDivisors++;
        }
    }

    return numberOfDivisors;
}

Saya tidak setuju bahwa ayakan Atkin adalah jalan yang harus ditempuh, karena bisa dengan mudah membutuhkan waktu lebih lama untuk memeriksa setiap angka di [1, n] untuk mengetahui keaslian daripada mengurangi jumlah berdasarkan divisi.

Berikut beberapa kode yang, meskipun sedikit peretasan, umumnya jauh lebih cepat:

import operator
# A slightly efficient superset of primes.
def PrimesPlus():
  yield 2
  yield 3
  i = 5
  while True:
    yield i
    if i % 6 == 1:
      i += 2
    i += 2
# Returns a dict d with n = product p ^ d[p]
def GetPrimeDecomp(n):
  d = {}
  primes = PrimesPlus()
  for p in primes:
    while n % p == 0:
      n /= p
      d[p] = d.setdefault(p, 0) + 1
    if n == 1:
      return d
def NumberOfDivisors(n):
  d = GetPrimeDecomp(n)
  powers_plus = map(lambda x: x+1, d.values())
  return reduce(operator.mul, powers_plus, 1)

ps Itu kode python yang berfungsi untuk memecahkan masalah ini.

Berikut ini adalah algoritma O ke depan (sqrt (n)). Saya menggunakan ini untuk memecahkan proyek euler

def divisors(n):
    count = 2  # accounts for 'n' and '1'
    i = 2
    while i ** 2 < n:
        if n % i == 0:
            count += 2
        i += 1
    if i ** 2 == n:
        count += 1
    return count

Pertanyaan yang menarik ini jauh lebih sulit daripada yang terlihat, dan belum dijawab. Pertanyaan tersebut dapat diperhitungkan menjadi 2 pertanyaan yang sangat berbeda.

1 diberikan N, temukan daftar L faktor prima N

2 diberikan L, hitung jumlah kombinasi unik

Semua jawaban yang saya lihat sejauh ini merujuk ke # 1 dan gagal menyebutkannya tidak dapat ditelusuri untuk jumlah yang sangat besar. Untuk N berukuran sedang, bahkan angka 64-bit, itu mudah; untuk N yang sangat besar, masalah anjak piutang bisa memakan waktu "selamanya". Enkripsi kunci publik tergantung pada ini.

Pertanyaan # 2 perlu diskusi lebih lanjut. Jika L hanya berisi angka unik, ini adalah perhitungan sederhana menggunakan rumus kombinasi untuk memilih objek k dari n item. Sebenarnya, Anda perlu menjumlahkan hasil dari menerapkan formula sambil memvariasikan k dari 1 hingga sizeof (L). Namun, L biasanya akan berisi banyak kejadian beberapa bilangan prima. Sebagai contoh, L = {2,2,2,3,3,5} adalah faktorisasi dari N = 360. Sekarang masalah ini cukup sulit!

Menyatakan ulang 2, diberikan koleksi C yang mengandung k item, sehingga item a memiliki 'duplikat, dan item b memiliki duplikat b, dll. Berapa banyak kombinasi unik dari item 1 hingga k-1 yang ada? Misalnya, {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} masing-masing harus terjadi sekali dan hanya sekali jika L = {2,2 , 2,3,3,5}. Setiap sub-koleksi unik tersebut adalah pembagi unik N dengan mengalikan item dalam sub-koleksi.

Jawaban atas pertanyaan Anda sangat tergantung pada ukuran bilangan bulat. Metode untuk angka kecil, misalnya kurang dari 100 bit, dan untuk angka ~ 1000 bit (seperti yang digunakan dalam kriptografi) sangat berbeda.

• gambaran umum: http://en.wikipedia.org/wiki/Divisor_function

• nilai untuk nreferensi kecil dan bermanfaat: A000005: d (n) (juga disebut tau (n) atau sigma_0 (n)), jumlah pembagi n.

• contoh dunia nyata: faktorisasi bilangan bulat

HANYA satu baris
Saya telah memikirkan dengan sangat hati-hati tentang pertanyaan Anda dan saya telah mencoba untuk menulis sepotong kode yang sangat efisien dan berkinerja tinggi. Untuk mencetak semua pembagi nomor yang diberikan pada layar, kita hanya perlu satu baris kode! (gunakan opsi -std = c99 saat kompilasi melalui gcc)

for(int i=1,n=9;((!(n%i)) && printf("%d is a divisor of %d\n",i,n)) || i<=(n/2);i++);//n is your number

untuk menemukan jumlah pembagi, Anda dapat menggunakan fungsi sangat sangat cepat berikut (berfungsi dengan benar untuk semua bilangan bulat kecuali 1 dan 2)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return counter;
}

atau jika Anda memperlakukan nomor yang diberikan sebagai pembagi (berfungsi dengan benar untuk semua nomor bilangan bulat kecuali 1 dan 2)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

CATATAN: dua fungsi di atas bekerja dengan benar untuk semua angka bilangan bulat positif kecuali angka 1 dan 2 sehingga berfungsi untuk semua angka yang lebih besar dari 2 tetapi jika Anda harus mencakup 1 dan 2, Anda dapat menggunakan salah satu fungsi berikut (sedikit lebih lambat)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    if (n==2 || n==1)
    {
    return counter;
    }
    return ++counter;
}

ATAU

int number_of_divisors(int n)
{
    int counter,i;
for(counter=0,i=1;(!(i==n) && !(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

kecil itu indah :)

Saringan Atkin adalah versi yang dioptimalkan dari saringan Eratosthenes yang memberikan semua bilangan prima hingga bilangan bulat yang diberikan. Anda harus dapat google ini untuk lebih detail.

Setelah Anda memiliki daftar itu, adalah masalah sederhana untuk membagi nomor Anda dengan setiap perdana untuk melihat apakah itu pembagi yang tepat (yaitu, sisanya adalah nol).

Langkah-langkah dasar menghitung pembagi untuk angka (n) adalah [ini adalah pseudocode yang dikonversi dari kode asli jadi saya harap saya belum memperkenalkan kesalahan]:

for z in 1..n:
    prime[z] = false
prime[2] = true;
prime[3] = true;

for x in 1..sqrt(n):
    xx = x * x

    for y in 1..sqrt(n):
        yy = y * y

        z = 4*xx+yy
        if (z <= n) and ((z mod 12 == 1) or (z mod 12 == 5)):
            prime[z] = not prime[z]

        z = z-xx
        if (z <= n) and (z mod 12 == 7):
            prime[z] = not prime[z]

        z = z-yy-yy
        if (z <= n) and (x > y) and (z mod 12 == 11):
            prime[z] = not prime[z]

for z in 5..sqrt(n):
    if prime[z]:
        zz = z*z
        x = zz
        while x <= limit:
            prime[x] = false
            x = x + zz

for z in 2,3,5..n:
    if prime[z]:
        if n modulo z == 0 then print z

Anda dapat mencoba yang ini. Agak sedikit retas, tapi cukup cepat.

def factors(n):
    for x in xrange(2,n):
        if n%x == 0:
            return (x,) + factors(n/x)
    return (n,1)

Setelah Anda memiliki faktorisasi utama, ada cara untuk menemukan jumlah pembagi. Tambahkan satu ke masing-masing eksponen pada masing-masing faktor dan kemudian gandakan eksponen bersama.

Misalnya: 36 Faktorisasi Utama: 2 ^ 2 * 3 ^ 2 Pembagi: 1, 2, 3, 4, 6, 9, 12, 18, 36 Jumlah Pembagi: 9

Tambahkan satu ke setiap eksponen 2 ^ 3 * 3 ^ 3 Eksponen gandakan: 3 * 3 = 9

Sebelum Anda berkomitmen pada solusi, pertimbangkan bahwa pendekatan Saringan mungkin bukan jawaban yang baik dalam kasus biasa.

Beberapa waktu lalu ada pertanyaan utama dan saya melakukan tes waktu - untuk bilangan bulat 32-bit setidaknya menentukan apakah bilangan prima lebih lambat daripada kekuatan kasar. Ada dua faktor yang terjadi:

1) Sementara seorang manusia membutuhkan waktu untuk melakukan pembagian, mereka sangat cepat di komputer - mirip dengan biaya mencari jawabannya.

2) Jika Anda tidak memiliki tabel utama, Anda dapat membuat loop yang sepenuhnya berjalan di cache L1. Ini membuatnya lebih cepat.

Ini adalah solusi yang efisien:

#include <iostream>
int main() {
  int num = 20; 
  int numberOfDivisors = 1;

  for (int i = 2; i <= num; i++)
  {
    int exponent = 0;
    while (num % i == 0) {
        exponent++; 
        num /= i;
    }   
    numberOfDivisors *= (exponent+1);
  }

  std::cout << numberOfDivisors << std::endl;
  return 0;
}

Pembagi melakukan sesuatu yang spektakuler: mereka membelah sepenuhnya. Jika Anda ingin memeriksa jumlah pembagi untuk suatu bilangan n, itu jelas berlebihan untuk menjangkau seluruh spektrum 1...n,. Saya belum melakukan penelitian mendalam untuk ini, tetapi saya memecahkan masalah Project Euler 12 pada Nomor Segitiga . Solusi saya untuk tes pembagi 500 yang lebih besar berlari selama 309504 mikrodetik (~ 0,3 detik). Saya menulis fungsi pembagi ini untuk solusinya.

int divisors (int x) {
    int limit = x;
    int numberOfDivisors = 1;

    for (int i(0); i < limit; ++i) {
        if (x % i == 0) {
            limit = x / i;
            numberOfDivisors++;
        }
    }

    return numberOfDivisors * 2;
}

Untuk setiap algoritma, ada titik lemahnya. Saya pikir ini lemah terhadap bilangan prima. Tetapi karena angka segitiga tidak dicetak, ia melayani tujuannya dengan sempurna. Dari profil saya, saya pikir itu cukup baik.

Selamat berlibur.

Anda ingin Saringan Atkin, dijelaskan di sini: http://en.wikipedia.org/wiki/Sieve_of_Atkin

metode bilangan prima sangat jelas di sini. P [] adalah daftar bilangan prima kurang dari atau sama dengan sq = sqrt (n);

for (int i = 0 ; i < size && P[i]<=sq ; i++){
          nd = 1;
          while(n%P[i]==0){
               n/=P[i];
               nd++;
               }
          count*=nd;
          if (n==1)break;
          }
      if (n!=1)count*=2;//the confusing line :D :P .

     i will lift the understanding for the reader  .
     i now look forward to a method more optimized  .

Buku teks teori angka menyebut fungsi penghitung-pembagi tau. Fakta menarik pertama adalah bahwa itu multiplikatif, yaitu. τ (ab) = τ (a) τ (b), ketika a dan b tidak memiliki faktor umum. (Bukti: setiap pasangan pembagi a dan b memberikan pembagi ab yang berbeda).

Sekarang perhatikan bahwa untuk pa prime, τ (p ** k) = k + 1 (kekuatan p). Dengan demikian Anda dapat dengan mudah menghitung τ (n) dari factorisation-nya.

Namun memfaktorkan jumlah besar bisa lambat (keamanan cryptraphy RSA tergantung pada produk dari dua bilangan prima besar yang sulit untuk difaktorkan). Itu menunjukkan algoritma yang dioptimalkan ini

1. Uji apakah jumlahnya prima (cepat)
2. Jika demikian, kembalikan 2
3. Kalau tidak, faktorkan nomornya (lambat jika banyak faktor prima besar)
4. Hitung τ (n) dari factorisation

Berikut ini adalah program C untuk menemukan jumlah pembagi nomor yang diberikan.

Kompleksitas dari algoritma di atas adalah O (sqrt (n)).

Algoritma ini akan bekerja dengan benar untuk angka yang kuadrat sempurna serta angka yang bukan kuadrat sempurna.

Perhatikan bahwa batas atas dari loop diatur ke akar kuadrat angka untuk memiliki algoritma yang paling efisien.

Perhatikan bahwa menyimpan batas atas dalam variabel terpisah juga menghemat waktu, Anda tidak boleh memanggil fungsi sqrt di bagian kondisi loop for, ini juga menghemat waktu komputasi Anda.

#include<stdio.h>
#include<math.h>
int main()
{
    int i,n,limit,numberOfDivisors=1;
    printf("Enter the number : ");
    scanf("%d",&n);
    limit=(int)sqrt((double)n);
    for(i=2;i<=limit;i++)
        if(n%i==0)
        {
            if(i!=n/i)
                numberOfDivisors+=2;
            else
                numberOfDivisors++;
        }
    printf("%d\n",numberOfDivisors);
    return 0;
}

Alih-alih di atas untuk loop Anda juga dapat menggunakan loop berikut yang bahkan lebih efisien karena ini menghilangkan kebutuhan untuk menemukan akar kuadrat dari angka tersebut.

for(i=2;i*i<=n;i++)
{
    ...
}

Berikut adalah fungsi yang saya tulis. kompleksitas waktu terburuknya adalah O (sqrt (n)), waktu terbaik di sisi lain adalah O (log (n)). Ini memberi Anda semua pembagi utama bersama dengan jumlah kemunculannya.

public static List<Integer> divisors(n) {   
    ArrayList<Integer> aList = new ArrayList();
    int top_count = (int) Math.round(Math.sqrt(n));
    int new_n = n;

    for (int i = 2; i <= top_count; i++) {
        if (new_n == (new_n / i) * i) {
            aList.add(i);
            new_n = new_n / i;
            top_count = (int) Math.round(Math.sqrt(new_n));
            i = 1;
        }
    }
    aList.add(new_n);
    return aList;
}

Ini adalah cara paling dasar untuk menghitung jumlah divisi:

class PrintDivisors
{
    public static void main(String args[])
    {

    System.out.println("Enter the number");

    // Create Scanner object for taking input
    Scanner s=new Scanner(System.in);

    // Read an int
    int n=s.nextInt();

        // Loop from 1 to 'n'
        for(int i=1;i<=n;i++)
        {

            // If remainder is 0 when 'n' is divided by 'i',
            if(n%i==0)
            {
            System.out.print(i+", ");
            }
        }

    // Print [not necessary]    
    System.out.print("are divisors of "+n);

    }
}

@ Kendall

Saya menguji kode Anda dan membuat beberapa perbaikan, sekarang bahkan lebih cepat. Saya juga diuji dengan kode @ هومن جاویدپور, ini juga lebih cepat daripada kodenya.

long long int FindDivisors(long long int n) {
  long long int count = 0;
  long long int i, m = (long long int)sqrt(n);
  for(i = 1;i <= m;i++) {
    if(n % i == 0)
      count += 2;
  }
  if(n / m == m && n % m == 0)
    count--;
  return count;
}

Bukankah ini hanya pertanyaan tentang memfaktorkan angka - menentukan semua faktor angka? Anda kemudian dapat memutuskan apakah Anda memerlukan semua kombinasi dari satu faktor atau lebih.

Jadi, satu algoritma yang mungkin adalah:

factor(N)
    divisor = first_prime
    list_of_factors = { 1 }
    while (N > 1)
        while (N % divisor == 0)
            add divisor to list_of_factors
            N /= divisor
        divisor = next_prime
    return list_of_factors

Terserah Anda untuk menggabungkan faktor-faktor untuk menentukan sisa jawaban.

Ini adalah sesuatu yang saya buat berdasarkan jawaban Justin. Mungkin perlu beberapa optimasi.

n=int(input())

a=[]
b=[]

def sieve(n):
    np = n + 1
    s = list(range(np)) 
    s[1] = 0
    sqrtn = int(n**0.5)
    for i in range(2, sqrtn + 1): 
        if s[i]:
            s[i*i: np: i] = [0] * len(range(i*i, np, i))
    return filter(None, s)

k=list(sieve(n))

for i in range(len(k)):
        if n%k[i]==0:
                a.append(k[i])

a.sort()

for i in range(len(a)):
        j=1
        while n%(a[i]**j)==0: 
                j=j+1
        b.append(j-1)

nod=1

for i in range(len(b)):
        nod=nod*(b[i]+1)

print('no.of divisors of {} = {}'.format(n,nod))

Saya pikir inilah yang Anda cari. Saya melakukan persis seperti yang Anda minta. Salin dan tempel di Notepad. Simpan sebagai * .bat.Jalankan. Masukkan Nomor. Gandakan proses dengan 2 dan itulah jumlah pembagi. Saya sengaja membuatnya sehingga menentukan pembagi pembagi lebih cepat:

Harap dicatat bahwa varriable CMD tidak dapat mendukung nilai lebih dari 999999999

@echo off

modecon:cols=100 lines=100

:start
title Enter the Number to Determine 
cls
echo Determine a number as a product of 2 numbers
echo.
echo Ex1 : C = A * B
echo Ex2 : 8 = 4 * 2
echo.
echo Max Number length is 9
echo.
echo If there is only 1 proces done  it
echo means the number is a prime number
echo.
echo Prime numbers take time to determine
echo Number not prime are determined fast
echo.

set /p number=Enter Number : 
if %number% GTR 999999999 goto start

echo.
set proces=0
set mindet=0
set procent=0
set B=%Number%

:Determining

set /a mindet=%mindet%+1

if %mindet% GTR %B% goto Results

set /a solution=%number% %%% %mindet%

if %solution% NEQ 0 goto Determining
if %solution% EQU 0 set /a proces=%proces%+1

set /a B=%number% / %mindet%

set /a procent=%mindet%*100/%B%

if %procent% EQU 100 set procent=%procent:~0,3%
if %procent% LSS 100 set procent=%procent:~0,2%
if %procent% LSS 10 set procent=%procent:~0,1%

title Progress : %procent% %%%



if %solution% EQU 0 echo %proces%. %mindet% * %B% = %number%
goto Determining

:Results

title %proces% Results Found
echo.
@pause
goto start

Saya kira yang satu ini akan berguna dan juga tepat

script.pyton

>>>factors=[ x for x in range (1,n+1) if n%x==0] print len(factors)

Cobalah sesuatu seperti ini:

int divisors(int myNum) {
    int limit = myNum;
    int divisorCount = 0;
    if (x == 1) 
        return 1;
    for (int i = 1; i < limit; ++i) {
        if (myNum % i == 0) {
            limit = myNum / i;
            if (limit != i)
                divisorCount++;
            divisorCount++;
        }
    }
    return divisorCount;
}

Saya tidak tahu metode paling efisien, tetapi saya akan melakukan hal berikut:

• Buat tabel bilangan prima untuk menemukan semua bilangan prima kurang dari atau sama dengan akar kuadrat dari angka (Secara pribadi, saya akan menggunakan Saringan Atkin)
• Hitung semua bilangan prima kurang dari atau sama dengan akar kuadrat dari angka dan kalikan dengan dua. Jika akar kuadrat dari angka tersebut adalah bilangan bulat, maka kurangi satu dari variabel jumlah.

Harus bekerja \ o /

Jika Anda perlu, saya dapat membuat kode besok di C untuk menunjukkan.