Secuencias de números compuestos

_{Inspirado por esta pregunta}

Dado un entero positivo n , su código debe generar los primeros n números compuestos.

De entrada y salida

Puedes escribir un programa o una función. La entrada es a través de STDIN o argumento de función y la salida es a STDOUT, o valor de retorno de función.

La salida puede ser una lista, una matriz o una cadena.

Ejemplos

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

Reglas

• Como siempre, las lagunas estándar no están permitidas.

• No se permiten los elementos integrados que generan números primos o compuestos.

• Las incorporaciones relacionadas con números primos o compuestos no están permitidas.

Pyth - 10 bytes

Una respuesta valida Utiliza el teorema de Wilson .

.f%h.!tZZQ

Pruébelo en línea aquí .

Vieja respuesta

Pyth - 6 caracteres

Utiliza incorporado para la factorización prima , no para la verificación principal.

.ftPZQ

Pruébelo en línea aquí .

.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

Genera una lista demasiado grande de productos de todas las combinaciones de [2, n] y trunca.

TeX, 382 bytes

Porque tú puedes.

\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

El número en la última línea es el número de números compuestos que desea tener.

Este es un simple probador de divisores. \dcomprueba si se #2divide #1. \irequiere \dtodos los divisores posibles (es decir, < #1). \lenumera los primeros #2números para los cuales \idevuelve 0.

Versión sin golf (bueno, medio 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]

Menos golfizado:

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

La idea es generar el conjunto de números compuestos multiplicando todos los pares de números naturales excepto 0 y 1. Luego, clasifique este conjunto y tome los primeros nelementos. Es suficiente tomar el producto cartesiano del conjunto {2, 3, ..., n+2}consigo mismo, que podemos obtener cambiandorange(n) a 2.

Al golf esto, hacer un truco clásico de golf de almacenar dos valores (a,b)en range(n)un solo valor ken range(n*n), y extraer de ellos como 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;}

Ampliado, con repetitivo:

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]

Cómo funciona

Esto también se basa en el teorema de Wilson y todo lo que hace es ejecutar un rango 1:n*ny extraer los números compuestos de acuerdo con el teorema mencionado anteriormente. He agregado +3porque n*nno es un rango lo suficientemente grande para n < 3enteros

El único problema con esta solución es que (lamentablemente) R pierde precisión para un factorial lo suficientemente grande, por lo tanto, esto no funcionará correctamente para n > 19

CJam, 20 18 bytes

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

Pruébalo en línea

No utiliza ningún operador de primo o factorización incorporado. Comprobación de fuerza bruta para los números compuestos.

Una observación que se usa aquí es que podemos calcular fácilmente un límite superior seguro para los números que tenemos que probar. Como cada segundo número mayor que 4 es compuesto, 4 + n * 2es un límite superior para el enésimo número compuesto.

Según una sugerencia de @Dennis, la última implementación en realidad usa n * 5como límite superior, que es mucho menos eficiente, pero 2 bytes más corto.

Explicación:

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 caracteres

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

Ejemplo de uso:

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

Cómo funciona

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

Explicado:

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

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

Esto usa el teorema de Wilson.

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

La función devuelve una matriz de los primeros nnúmeros compuestos.

~-nes una forma elegante de escribir n-1; misma longitud, pero mucho más divertido, ¿verdad?
La única razón por la que uso evales que la plantilla n=>eval('...returnValue')es 1 carácter más corta que n=>{...return returnValue}.

versiones antiguas

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

Salida

 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

Muy inspirado por la respuesta anterior de Nimi , reemplazando el predicado por uno de 2 bytes más corto basado en anyuna lambda sin puntos en lugar de una comprensión de lista anidada.

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

Pruébalo en línea!
( gracias a Laikoni por el enlace TIO preciso)

Explicación:

[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