nomor ke-n yang memiliki jumlah faktor prima yang berbeda

10

Buat terpendek fungsi, program, atau ekspresi yang menghitung A073329 , yaitu, a(n)adalah n jumlah memiliki n faktor prima yang berbeda. Input adalah jumlah elemen dalam urutan untuk kembali. 0 < n. Saya tidak peduli dengan presisi integer. Saya hanya ingin algoritme. Untuk bahasa yang tidak mendukung bilangan bulat besar yang sewenang-wenang, kami hanya akan berpura-pura bahwa itu bilangan bulat.

Anda dapat menemukan kasus uji dengan mengikuti tautan ke OEIS yang diberikan di atas.

MEMPERBARUI:

Biarkan saya memperjelas bahwa Anda perlu mengembalikan urutan integer dari program, fungsi, atau ekspresi Anda. Dengan kata lain, f(x)harus menghitung a(n)semua ndari 1 hingga x. Diberikan xdari 8, fungsi Anda harus kembali 2, 10, 60, 420, 4290, 53130, 903210, 17687670sebagai array atau beberapa struktur data lain yang sesuai.

code-golf math Gregory Higley
sumber
Batas / batas ??
st0le
Saya tidak terlalu peduli dengan batasan dan batasan, tetapi jika ini penting bagi Anda, lakukan algoritma dengan asumsi input tidak lebih dari 8, dan kami akan berpura-pura itu bekerja untuk angka yang lebih tinggi. Seperti yang saya katakan, saya tertarik pada algoritma matematika abstrak, bukan rincian batasan integer bahasa tertentu.
Gregory Higley
1
Mungkin lebih terbuka, ketika kita mengatakan: output a(1), ... a(n)alih-alih mengembalikan sesuatu, seperti array ...
pengguna tidak dikenal

Jawaban:

2

Python, 144 karakter

R=range
P=[x for x in R(2,99)if all(x%i for i in R(2,x))]
for a in R(input()):
 x=n=0
 while n<=a:n+=sum(x%p==0for p in P)==a+1;x+=1
 print x-1

Dibutuhkan sekitar 2 menit untuk menjalankan sampai selesai untuk x = 8.

Keith Randall
sumber
2

Java, 170 karakter dalam satu baris

int a(int n) {
    int a = 2, t = a, m = 1, i = 1;
    Set s = new HashSet();
    while (i++ > 0) {
        if (t % i == 0) {
            s.add(i);
            t /= i;
            if (t == 1) {
                if (s.size() == n) {
                    if (n == m) {
                        break;
                    }
                    m++;
                }
                t = ++a;
                s.clear();
            }
            i = 1;
        }
    }
    return a;
}

Perbarui, +77 karakter IOL

int[] f(int n) {
    int[] f = new int[n];
    for (int i = 0; i < n; i++) {
        f[i] = a(i+1);
    }
    return f;
}
Kuba
sumber
Ini sebenarnya salah, tapi dekat, meskipun saya pikir saya mungkin harus membuat pertanyaan saya lebih jelas. Anda harus mengembalikan urutan bilangan bulat. Misalnya, jika input 8, Anda harus mengembalikan 8 elemen pertama dalam urutan A073329.
Gregory Higley
@Gregory lihat pembaruan
cubanacan
Maaf - saya menolak Anda, berdasarkan kesalahpahaman saya tentang tugas ini, yang diklarifikasi setelah membaca tautan OEIS. Jika Anda melakukan sedikit pengeditan pada posting Anda, saya dapat dan akan mencabut downvote saya.
pengguna tidak dikenal
@ pengguna karena kesalahpahaman saya sendiri tentang komentar Anda, mohon klarifikasi permintaan Anda
cubanacan
Saya salah mengerti pertanyaan, dan berpikir, semua faktor pastilah bilangan prima yang berbeda, jadi 2 * 3 * 5 * 2 akan menjadi jawaban yang salah. Jadi saya memilih jawaban Anda karena salah. Kemudian saya menemukan, bagaimana 'bilangan prima' adalah untuk memahami, dan ingin memperbaiki pemilihan saya, tetapi saya tidak diizinkan untuk mengubah suara saya - itu hanya mungkin dalam beberapa menit pertama. Tetapi jika Anda mengedit jawaban Anda, saya dapat mengubah suara saya. Jadi saya meminta Anda untuk mengedit sedikit saja.
pengguna tidak dikenal
2

Jawa (Tidak Digabungkan)

public class M {

    public static void main(String[] a) {
        final int N = 100000000;
        int[] p = new int[N];
        for(int f = 2; f * f < N; f++) {
            if(p[f] == 0)
                for(int k = f; k < N; k += f)
                    p[k]++;
        }
        for(int i = 1; i <= 8; i++) {
            int c = 0, j;
            for(j = 1; j < N && c < i; j++)
                if(p[j] == i)
                    c++;
            if(c == i)
                System.out.println(i + " = " + --j);
        }
    }
}

Menggunakan algoritma ayakan. Cukup cepat. (6 Detik) Akan bekerja secara akurat untuk upto 8, mungkin akan gagal untuk hal yang lebih tinggi.

st0le
sumber
1

JavaScript, 149 karakter

function(n){function f(x){for(r=[],o=x,z=2;z<=o;x%z?++z:(x/=z,r.indexOf(z)+1?0:r.push(z)));return r}for(c=0,i=1;c<n;)f(++i).length==n?c++:0;return i}

Terasa tidak responsif untuk n> = 6 jadi saya belum menguji berapa lama (browser saya muncul pemberitahuan skrip yang digantung setiap 10 detik atau lebih karena itu saya tidak dapat menghitungnya secara akurat dan saya tidak ingin sepenuhnya menggantung jika saya centang "jangan perlihatkan ini lagi" ...)

Sunting: Untuk mengembalikan array adalah 200 karakter (+51) :

function(n){function F(){function f(x){for(r=[],o=x,z=2;z<=o;x%z?++z:(x/=z,r.indexOf(z)+1?0:r.push(z)));return r}for(c=0,i=1;c<n;)F(++i).length==n?c++:0;return i}for(a=[];n>0;n--)a.push(f());return a}
Ry-
sumber
0

J, 32 byte

({"0 1~i.@#)(]/.~#@~.@q:)

Tetapi karena saya menjawab pertanyaan saya sendiri sangat terlambat, kami hanya akan meninggalkan jawaban ini sebagai rasa ingin tahu.

Gregory Higley
sumber