Sequenzen zusammengesetzter Zahlen

_{Inspiriert von dieser Frage}

Bei einer positiven Ganzzahl n muss Ihr Code die erste ausgeben n zusammengesetzten Zahlen .

Input-Output

Sie können ein Programm oder eine Funktion schreiben. Die Eingabe erfolgt über STDIN oder ein Funktionsargument und die Ausgabe erfolgt über STDOUT oder einen Funktionsrückgabewert.

Die Ausgabe kann eine Liste, ein Array oder eine Zeichenfolge sein.

Beispiele

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

Regeln

• Standardlücken sind wie immer verboten.

• Built-Ins, die Primzahlen oder zusammengesetzte Zahlen erzeugen, sind nicht zulässig.

• Eingebaute Zahlen in Bezug auf Primzahlen oder zusammengesetzte Zahlen sind nicht zulässig.

Pyth - 10 Bytes

Eine gültige Antwort. Verwendet den Satz von Wilson .

.f%h.!tZZQ

Probieren Sie es hier online aus .

Alte Antwort

Pyth - 6 Zeichen

Verwendet die eingebaute Primfaktorisierung , nicht die Primprüfung .

.ftPZQ

Probieren Sie es hier online aus .

.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 Bytes

<S{*M^tSQ2Q

Erzeugt eine zu große Liste von Produkten aller Kombinationen von [2, n] und Kürzungen.

TeX, 382 Bytes

Weil du es kannst.

\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

Die Zahl in der letzten Zeile ist die Anzahl der zusammengesetzten Zahlen, die Sie haben möchten.

Dies ist ein einfacher Divisor-Tester. \dprüft ob sich #2teilt #1. \ifordert \dalle möglichen Teiler (dh < #1). \llistet die ersten #2Zahlen auf, für die \i0 zurückgegeben wird.

Ungolfed-Version:

\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]

Weniger golfen:

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

Die Idee ist, die Menge der zusammengesetzten Zahlen zu generieren, indem alle Paare natürlicher Zahlen mit Ausnahme von 0 und 1 multipliziert werden. Sortieren Sie dann diese Menge und nehmen Sie die ersten nElemente. Es genügt, das kartesische Produkt der Menge mitzunehmen {2, 3, ..., n+2}, das wir durch Verschiebung erhalten könnenrange(n) um 2 erhalten können.

Golf dies tun wir einen klassischen Golf - Trick von Speichern von zwei Werten (a,b)in range(n)als Einzelwert kin range(n*n)und extrahieren sie als a=k/n, b=k%n.

Java 8, 98 97 Bytes

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

Erweitert, mit 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 Bytes

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

Wie es funktioniert

Dies basiert auch auf Wilsons Theorem und alles, was es tut, ist, einen Bereich von 1:n*nzusammengesetzten Zahlen nach dem oben erwähnten Theorem zu durchlaufen und zu extrahieren. Ich habe hinzugefügt, +3weil der n*nBereich für n < 3ganze Zahlen nicht groß genug ist

Das einzige Problem bei dieser Lösung ist, dass (leider) R die Genauigkeit für eine ausreichend große Fakultät verliert, daher funktioniert dies nicht richtig für n > 19

CJam, 20 18 Bytes

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

Probieren Sie es online aus

Verwendet keine eingebauten Prim- oder Faktorisierungsoperatoren. Recht brachiale Kraftprüfung für Zahlen, die zusammengesetzt sind.

Eine Beobachtung, die hier verwendet wird, ist, dass wir leicht eine sichere Obergrenze für die Zahlen berechnen können, die wir testen müssen. Da jede zweite Zahl größer als 4 zusammengesetzt ist, 4 + n * 2handelt es sich um eine Obergrenze für die n-te zusammengesetzte Zahl.

Basierend auf einem Vorschlag von @Dennis verwendet die neueste Implementierung tatsächlich n * 5die Obergrenze, die viel weniger effizient ist, aber 2 Byte kürzer.

Erläuterung:

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 Zeichen

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

Haskell, 49 46 Bytes

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

Anwendungsbeispiel:

*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]

Wie es funktioniert

  [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 Bytes

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

Erklärt:

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

Ungolfed

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 Bytes

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))

Dies verwendet den Satz von Wilson.

Ungolfed:

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 Bytes

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')

Die Funktion gibt ein Array der ersten nzusammengesetzten Zahlen zurück.

~-nist eine ausgefallene Schreibweise n-1; Gleiche Länge, aber viel mehr Spaß, oder?
Der einzige Grund, den ich benutze, evalist, dass die Vorlage n=>eval('...returnValue')1 Zeichen kürzer ist als n=>{...return returnValue}.

alte Versionen

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')

Ausgabe

 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 Bytes

Stark inspiriert von Nimis früherer Antwort , bei der das Prädikat durch ein um 2 Byte kürzeres Prädikat ersetzt wird, das auf anyeinem punktfreien Lambda anstelle eines verschachtelten Listenverständnisses basiert .

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

Probieren Sie es online!
( Danke an Laikoni für den genauen TIO-Link)

Erläuterung:

[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