Séquences de nombres composites

_{Inspiré par cette question}

Étant donné un entier positif n , votre code doit sortir les n premiers nombres composites.

Entrée sortie

Vous pouvez écrire un programme ou une fonction. L'entrée se fait via STDIN ou l'argument de fonction et la sortie est vers STDOUT, ou la valeur de retour de la fonction.

La sortie peut être une liste, un tableau ou une chaîne.

Exemples

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

Règles

• Comme toujours, les failles standard sont interdites.

• Les intégrées qui génèrent des nombres premiers ou composites ne sont pas autorisées.

• Les éléments intégrés relatifs aux nombres premiers ou composites ne sont pas autorisés.

Pyth - 10 octets

Une réponse valable. Utilise le théorème de Wilson .

.f%h.!tZZQ

Essayez-le en ligne ici .

Ancienne réponse

Pyth - 6 caractères

Utilisations pour builtin factorisation , pas de vérification de premier choix.

.ftPZQ

Essayez-le en ligne ici .

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

<S{*M^tSQ2Q

Génère une liste trop grande de produits de toutes les combinaisons de [2, n] et tronque.

TeX, 382 octets

Parce que vous pouvez.

\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

Le nombre dans la dernière ligne est le nombre de nombres composites que vous voulez avoir.

Il s'agit d'un simple testeur de diviseur. \dvérifie si #2divise #1. \iappelle \dtous les diviseurs possibles (c'est-à-dire < #1). \lrépertorie les premiers #2nombres pour lesquels \irenvoie 0.

Version non golfée (enfin, semi-golfée):

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

Moins golfé:

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

L'idée est de générer l'ensemble des nombres composites en multipliant toutes les paires de nombres naturels sauf 0 et 1. Ensuite, triez cet ensemble et prenez les premiers néléments. Il suffit de prendre avec lui le produit cartésien de l'ensemble {2, 3, ..., n+2}, que l'on peut obtenir en range(n)remontant de 2.

Pour jouer au golf, nous faisons un tour de golf classique consistant à stocker deux valeurs (a,b)dans range(n)une seule valeur kdans range(n*n), et à les extraire sous a=k/n, b=k%n.

Java 8, 98 97 octets

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

Expansé, avec passe-partout:

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 octets

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

Comment ça fonctionne

Ceci est également basé sur le théorème de Wilson et tout ce qu'il fait est de parcourir une plage de 1:n*net d'extraire les nombres composites selon le théorème mentionné ci-dessus. J'ai ajouté +3parce n*nque la plage n'est pas assez grande pour les n < 3entiers

Le seul problème avec cette solution est que (malheureusement) R perd de la précision pour une factorielle suffisamment grande, donc cela ne fonctionnera pas correctement pour n > 19

CJam, 20 18 octets

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

Essayez-le en ligne

N'utilise pas d'opérateurs principaux ou de factorisation intégrés. Vérification assez brutale pour les nombres composites.

Une observation qui est utilisée ici est que nous pouvons facilement calculer une limite supérieure sûre pour les nombres que nous devons tester. Étant donné que chaque deuxième nombre supérieur à 4 est composite, 4 + n * 2est une limite supérieure pour le n-ième nombre composite.

Sur la base d'une suggestion de @Dennis, la dernière implémentation utilise en fait n * 5comme limite supérieure, ce qui est beaucoup moins efficace, mais 2 octets plus court.

Explication:

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 caractères

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

Haskell, 49 46 octets

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

Exemple d'utilisation:

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

Comment ça fonctionne

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

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

Expliqué:

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

Non golfé

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 octets

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

Cela utilise le théorème de Wilson.

Non golfé:

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 octets

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

La fonction renvoie un tableau des premiers nnombres composites.

~-nest une façon élégante d'écrire n-1; même longueur, mais beaucoup plus amusant, non?
La seule raison pour laquelle j'utilise evalest que le modèle n=>eval('...returnValue')est 1 caractère plus court que n=>{...return returnValue}.

anciennes versions

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

Production

 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 octets

Fortement inspiré par la réponse précédente de Nimi , remplaçant le prédicat par un plus court de 2 octets basé sur anyun lambda sans point au lieu d'une compréhension de liste imbriquée.

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

Essayez-le en ligne!
( merci à Laikoni pour le lien TIO précis)

Explication:

[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