Urutan Nomor Komposit

_{Terinspirasi oleh pertanyaan ini}

Diberikan bilangan bulat positif n , kode Anda harus menampilkan angka komposit n pertama .

Input output

Anda dapat menulis program atau fungsi. Input melalui STDIN atau argumen fungsi dan output ke STDOUT, atau nilai pengembalian fungsi.

Output dapat berupa Daftar, Array, atau String.

Contohnya

 0 -> 
 1 -> 4
 2 -> 4, 6
 3 -> 4, 6, 8
13 -> 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22

Aturan

• Seperti biasa, celah standar tidak diizinkan.

• Built-in yang menghasilkan bilangan prima atau gabungan tidak diizinkan.

• Built-in yang berkaitan dengan bilangan prima atau gabungan tidak diizinkan.

Pyth - 10 byte

Jawaban yang valid. Menggunakan Teorema Wilson .

.f%h.!tZZQ

Cobalah online di sini .

Jawaban lama

Pyth - 6 karakter

Menggunakan builtin untuk faktorisasi prima , bukan pengecekan prima.

.ftPZQ

Cobalah online di sini .

.f  Q         First n that passes filter of lambda Z, uses input for how many
 t            Tail. This makes all that have len-one prime factorization become empty list, and thus falsey.
  P           Prime factorization - primes have a len-one factorization.
   Z          Lambda var

Pyth, 11 byte

<S{*M^tSQ2Q

Menghasilkan daftar produk yang terlalu besar dari semua kombinasi [2, n] dan truncate.

TeX, 382 byte

Karena kamu bisa.

\newcount\a\newcount\b\newcount\c\newcount\n\newcount\p\newcount\q\let\v\advance\let\e\else\let\z\ifnum
\def\d#1:#2:#3:{\z#1>#2\v#1 by-#2\d#1:#2:#3:\e\z#1=#2#3=1\e#3=0\fi\fi}
\def\i#1:#2:#3:{#3=0\z#1>#2\a=#1\d\a:#2:\c:
\z\c=0\b=#2\v\b by 1\i#1:\the\b:#3:\e#1\par\fi\e#3=1\fi}
\def\l#1:#2:#3:#4:{\i\the#1:2:#4:
\z#4=0\v#2 by 1\fi\z#2<#3\v#1 by 1\l#1:#2:#3:#4:\fi}
\l\p:\n:10:\q:\end

Angka di baris terakhir adalah jumlah angka gabungan yang ingin Anda miliki.

Ini adalah tester pembagi sederhana. \dmemeriksa apakah #2membagi #1. \ipanggilan \duntuk semua pembagi yang mungkin (yaitu < #1). \ldaftar #2angka pertama yang \imengembalikan 0.

Versi tidak digolfkan (well, setengah golf):

\newcount\a
\newcount\b
\newcount\c
\newcount\n
\newcount\p
\newcount\q

\def\div#1:#2:#3:{%
  \ifnum#1>#2 %
    \advance#1 by-#2 %
    \div#1:#2:#3:%
  \else%
    \ifnum#1=#2 %
      #3=1%
    \else%
      #3=0%
    \fi%
  \fi%
}

\long\def\isprime#1:#2:#3:{%
  #3=0%
  \ifnum#1>#2 %
    \a=#1 %
    \div\a:#2:\c: %
    \ifnum\c=0 %
      \b=#2 %
      \advance\b by 1 %
      \isprime#1:\the\b:#3:%
    \else
      #1\par%
    \fi%
  \else%
    #3=1%
  \fi%
}

\def\listprimes#1:#2:#3:#4:{%
  \isprime\the#1:2:#4: %
  \ifnum#4=0 %
    \advance#2 by 1 %
  \fi
  \ifnum#2<#3 %
    \advance#1 by 1 %
    \listprimes#1:#2:#3:#4: %
  \fi
}

\listprimes\p:\n:11:\q:

\end

Python, 57

lambda n:sorted({(k/n+2)*(k%n+2)for k in range(n*n)})[:n]

Kurang golf:

def f(n):
 R=range(n)
 return sorted({(a+2)*(b+2)for a in R for b in R})[:n]

Idenya adalah untuk menghasilkan himpunan bilangan komposit dengan mengalikan semua pasangan bilangan alami kecuali 0 dan 1. Kemudian, sortir himpunan ini, dan ambil nelemen pertama . Cukup dengan mengambil produk Cartesian dari himpunan {2, 3, ..., n+2}itu sendiri, yang bisa kita dapatkan dengan menggeser ke range(n)atas dengan 2.

Untuk golf ini, kita melakukan trik golf klasik menyimpan dua nilai (a,b)di range(n)sebagai nilai tunggal kdalam range(n*n), dan ekstrak mereka sebagai a=k/n, b=k%n.

Java 8, 98 97 byte

i->{int a[]=new int[i],c=3,k=0,d;for(;k<i;c++)for(d=c;d-->2;)if(c%d<1){a[k++]=c;break;}return a;}

Diperluas, dengan boilerplate:

public class C {
    public static void main(String[] args) {
        Function<Integer, int[]> f = i -> {
            int a[] = new int[i], c = 3;
            for (int k = 0; k < i; c++) {
                for (int d = c; d --> 2;) {
                    if (c % d < 1) {
                        a[k++] = c;
                        break;
                    }
                }
            }
            return a;
        };
        System.out.println(Arrays.toString(f.apply(5)));
    }
}

R, 53 byte

n=scan();t=1:(n*n+3);t[factorial(t-1)%%t!=(t-1)][1:n]

Bagaimana itu bekerja

Ini juga didasarkan pada teorema Wilson dan yang dilakukannya hanyalah menjalankan rentang 1:n*ndan mengekstraksi bilangan komposit sesuai dengan teorema yang disebutkan di atas. Saya telah menambahkan +3karena n*nrentang n < 3bilangan bulat tidak cukup besar

Satu-satunya masalah dengan solusi ini adalah (sayangnya) R kehilangan presisi untuk faktorial yang cukup besar, sehingga, ini tidak akan berfungsi dengan baik untuk n > 19

CJam, 20 18 byte

li_5*{_,2>f%0&},<`

Cobalah online

Tidak menggunakan operator prima atau faktorisasi bawaan apa pun. Periksa kekuatan secara kasar untuk angka yang komposit.

Satu pengamatan yang digunakan di sini adalah bahwa kita dapat dengan mudah menghitung batas atas yang aman untuk angka yang harus kita uji. Karena setiap angka kedua yang lebih besar dari 4 adalah komposit, 4 + n * 2adalah batas atas untuk nomor komposit ke-n.

Berdasarkan saran dari @ Dennis, implementasi terbaru sebenarnya menggunakan n * 5sebagai batas atas, yang jauh lebih efisien, tetapi 2 byte lebih pendek.

Penjelasan:

li    Get and convert input.
_     Copy, will need the value to trim the list at the end.
5*    Calculate upper bound.
{     Start of filter.
  _     Copy value.
  ,     Create list [0 .. value-1].
  2>    Slice off the first two, leaving candidate factors [2 .. value-1].
  f%    Apply modulo with all candidate factors to value.
  0&    Check if one of the modulo results is 0.
},    End of filter.
<     Trim output to n values.
`     Convert list to string.

Javascript ES6, 88 karakter

n=>{r=[];for(q=2;r.length!=n;++q)if(/^(..+)\1+$/.test("-".repeat(q)))r.push(q);return r}

Haskell, 49 46 byte

(`take`[x|x<-[4..],or[mod x y<1|y<-[2..x-1]]])

Contoh penggunaan:

*Main> (`take`[x|x<-[4..],or[mod x y<1|y<-[2..x-1]]]) 13
[4,6,8,9,10,12,14,15,16,18,20,21,22]

Bagaimana itu bekerja

  [x|x<-[4..]    ]           -- keep all x from the integers starting with 4 where
      ,or                    -- where at least one element of the following list is "True"
    [mod x y<1|y<-[2..x-1]]  -- "x mod y < 1" for all y from [2,3,...x-1]
(`take`[   ])                -- take the first n elements from the xes
                             -- where n is the parameter supplied when calling the function

F #, 78 byte

fun n->(Array.filter(fun i->Seq.exists((%)i>>(=)0)[2..i-1])[|2..n*n|]).[..n-1]

Dijelaskan:

fun n->                                                                      
                                                           [|2..n*n|]          // Generate an array of integers from 2 to n * n
        Array.filter(fun i->                              )                    // Filter it using the following function on each element
                                                  [2..i-1]                        // Generate a list of possible divisors (from 2 to i-1)
                            Seq.exists(          )                                // Check if at least one of the divisors is valid, that is
                                       (%)i>>(=)0                                    // That i % it is equal to 0. This is equivalent to (fun d -> i % d = 0)
       (                                                             ).[..n-1] // Take the n first elements of the resulting, filtered array

C ++ 109

int main(){int n,i,x=4;cin>>n;while(n){for(i=2;i<x-1;i++){if(x%i==0){cout<<x<<' ';n--;break;}}x++;}return 0;}

Tidak disatukan

int main(){
int n,i,x=4;cin>>n;
while(n)
{
for(i=2;i<x-1;i++)
{
if(x%i==0){cout<<x<<' ';n--;break;}
}
x++;
}
return 0;
}

Julia, 103 byte

n->(n>0&&println(4);n>1&&(i=0;c=big(6);while i<n-1 mod(factorial(c-1),c)<1&&(i+=1;println(c));c+=1end))

Ini menggunakan Teorema Wilson.

Tidak Disatukan:

function f(n::Int)
    # Always start with 4
    n > 0 && println(4)

    # Loop until we encounter n composites
    if n > 1
        i = 0
        c = big(6)
        while i < n-1
            if mod(factorial(c-1), c) == 0
                i += 1
                println(c)
            end
            c += 1
        end
    end
end

ECMAScript 6 - 107 91 84 byte

n=>eval('for(a=[],x=4;n&&!a[~-n];x++)for(y=2;y*2<=x;)if(x%y++<1){a.push(x);break}a')

Fungsi mengembalikan array nangka komposit pertama .

~-nadalah cara penulisan yang mewah n-1; panjang yang sama, tetapi jauh lebih menyenangkan, bukan?
Satu-satunya alasan yang saya gunakan evaladalah bahwa templatnya n=>eval('...returnValue')1 karakter lebih pendek dari n=>{...return returnValue}.

versi lama

n=>eval('for(a=[],x=4;n&&!a[~-n];x++){for(z=0,y=2;y*2<=x;)if(x%y++<1)z=1;if(z)a.push(x)}a')

n=>eval('for(a=[],i=4;a.length<n;i++)if((x=>{for(y=2,z=1;y*2<=x;)if(x%y++<1)z=0;return!z})(i))a.push(i);a')

Keluaran

 0 -> []
 1 -> [4]
 2 -> [4, 6]
 3 -> [4, 6, 8]
13 -> [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22]

Haskell , 44 byte

Sangat terilhami oleh jawaban Nimi sebelumnya , menggantikan predikat dengan yang lebih pendek 2-byte berdasarkan pada anylambda pointfree bukannya pemahaman daftar bersarang.

(`take`[x|x<-[4..],any((<)1.gcd x)[2..x-1]])

Cobalah online!
( terima kasih kepada Laikoni untuk tautan TIO yang akurat)

Penjelasan:

[x|x<-[4..],       -- consider all integers x >=4
[2..x-1]           -- consider all integers smaller than x
any((<)1.gcd x)    -- if for any of them 
    (<)1           -- 1 is smaller than
        .gcd x     -- the gcd of x and the lambda input
                   -- then we found a non-trivial factor and thus the number is composite
(`take`[  ])       -- take the first <argument> entries