13
\$\begingroup\$

Inspired by this question

Given a positive integer \$n\$, your code must output the first \$n\$ composite numbers.

Input / Output

You may write a program or a function. Input is through STDIN or function argument and output is to STDOUT, or function return value.

Output can be a List, Array, or String.

Examples

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

Rules

  • As always standard loopholes are disallowed.

  • Built-ins that generate prime or composite numbers are not allowed.

  • Built-ins relating to prime or composite numbers are not allowed.

\$\endgroup\$
1

17 Answers 17

11
\$\begingroup\$

Pyth - 10 bytes

A valid answer. Uses Wilson's Theorem.

.f%h.!tZZQ

Try it online here.


Old answer

Pyth - 6 chars

Uses builtin for prime factorization, not prime checking.

.ftPZQ

Try it online here.

.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
\$\endgroup\$
5
  • \$\begingroup\$ Hm, should of thought about that :/ \$\endgroup\$
    – Downgoat
    Sep 8, 2015 at 3:44
  • 1
    \$\begingroup\$ The rules have changed and thus this answer is no longer valid. \$\endgroup\$
    – orlp
    Sep 8, 2015 at 4:18
  • \$\begingroup\$ @orlp updated answer. \$\endgroup\$
    – Maltysen
    Sep 8, 2015 at 5:10
  • \$\begingroup\$ @Maltysen Isn't this 10 bytes? \$\endgroup\$ Sep 8, 2015 at 18:35
  • \$\begingroup\$ @kirbyfan64sos :/ I apparently can't read the length counter. Fixing. \$\endgroup\$
    – Maltysen
    Sep 9, 2015 at 2:28
8
\$\begingroup\$

Pyth, 11 bytes

<S{*M^tSQ2Q

Generates overly large list of products of all combinations of [2, n] and truncates.

\$\endgroup\$
1
  • \$\begingroup\$ It does not work if the input is 1 or 2. \$\endgroup\$
    – Toothbrush
    Sep 10, 2015 at 20:52
7
\$\begingroup\$

TeX, 382 bytes

Because you can.

\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

The number in the last line is the number of composite numbers you want to have.

This is a simple divisor tester. \d checks if #2 divides #1. \i calls \d for all possible dividers (i.e. < #1). \l lists the first #2 numbers for which \i returns 0.

Ungolfed (well, half-golfed) 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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Programming Puzzles and Code Golf! Great first answer in a language nobody thought would be suitable for the challenge. Although it is pretty long, it is unique and neat answering in TeX and we certainly appreciate such answers. \$\endgroup\$
    – TanMath
    Jan 25, 2016 at 10:29
  • 1
    \$\begingroup\$ @TanMath thanks for the warm welcome, I realize this is too long to compete, but it was fun :) \$\endgroup\$
    – user42682
    Jan 25, 2016 at 10:29
6
\$\begingroup\$

Python, 57

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

Less golfed:

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

The idea is to generate the set of composite numbers by multiplying all pairs of natural numbers except 0 and 1. Then, sort this set, and take the first n elements. It suffices to take the Cartesian product of the set {2, 3, ..., n+2} with itself, which we can get by shifting range(n) up by 2.

To golf this, we do a classic golfing trick of storing two values (a,b) in range(n) as a single value k in range(n*n), and extract them as a=k/n, b=k%n.

\$\endgroup\$
4
\$\begingroup\$

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

Expanded, with 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)));
    }
}
\$\endgroup\$
4
\$\begingroup\$

R, 53 bytes

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

How it works

This is also based on Wilson's theorem and all it does is to run over a range of 1:n*n and extract the composite numbers according to the above mentioned theorem. I've added +3 because n*n isn't big enough range for n < 3 integers


The only problem with this solution is that (sadly) R loses precision for a big enough factorial, thus, this won't work properly for n > 19

\$\endgroup\$
3
\$\begingroup\$

CJam, 20 18 bytes

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

Try it online

Does not use any built in prime or factorization operators. Fairly brute force check for numbers being composite.

One observation that is used here is that we can easily calculate a safe upper bound for the numbers we have to test. Since every second number larger than 4 is composite, 4 + n * 2 is an upper bound for the n-th composite number.

Based on a suggestion by @Dennis, the latest implementation actually uses n * 5 as the upper limit, which is much less efficient, but 2 bytes shorter.

Explanation:

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.
\$\endgroup\$
0
3
\$\begingroup\$

Javascript ES6, 88 chars

n=>{r=[];for(q=2;r.length!=n;++q)if(/^(..+)\1+$/.test("-".repeat(q)))r.push(q);return r}
\$\endgroup\$
9
  • \$\begingroup\$ I believe removing the variable assignment f= is legal. \$\endgroup\$
    – DankMemes
    Sep 8, 2015 at 14:11
  • \$\begingroup\$ @DankMemes, seems yes. meta.codegolf.stackexchange.com/q/6915/32091 \$\endgroup\$
    – Qwertiy
    Sep 8, 2015 at 14:17
  • 1
    \$\begingroup\$ This is 83: n=>eval('for(r=[],q=2;r.length-n;/^(..+)\\1+$/.test("-".repeat(++q))&&r.push(q))r') \$\endgroup\$
    – DankMemes
    Sep 8, 2015 at 14:29
  • \$\begingroup\$ @DankMemes, cool :) \$\endgroup\$
    – Qwertiy
    Sep 8, 2015 at 14:32
  • 1
    \$\begingroup\$ @Qwertiy Sorry, I meant n&&!r[n-1] :'| It is the same length as r.length<n – one character shorter than r.length!=n – but this is supposed to be Code Golf, right? :-] \$\endgroup\$
    – Toothbrush
    Sep 10, 2015 at 19:59
2
\$\begingroup\$

Haskell, 49 46 bytes

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

Usage example:

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

How it works

  [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
\$\endgroup\$
2
\$\begingroup\$

F#, 78 bytes

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

Explained:

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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ This is a great answer, however it is a bit confusing that you use the variable i twice. I'm not too familiar with F#, but couldn't you perhaps use j? \$\endgroup\$
    – wizzwizz4
    Jan 25, 2016 at 19:10
  • \$\begingroup\$ Right, that does make it clearer. It did work due to shadowing, but I guess I forgot about readability while golfing the thing. ^_^' \$\endgroup\$
    – Roujo
    Jan 25, 2016 at 19:21
  • \$\begingroup\$ I don't ever make that sort of mistake. Probably why I'm not good at golfing d:-D \$\endgroup\$
    – wizzwizz4
    Jan 25, 2016 at 19:29
1
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • \$\begingroup\$ 1. Why not make a nice formatting for ungolfed version? 2. Seems like you have extra braces in both codes. 3. You can replace while by for. \$\endgroup\$
    – Qwertiy
    Sep 8, 2015 at 14:20
1
\$\begingroup\$

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

This uses Wilson's Theorem.

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
\$\endgroup\$
1
\$\begingroup\$

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

The function returns an array of the first n composite numbers.

~-n is a fancy way of writing n-1; same length, but much more fun, right?
The only reason I use eval is that the template n=>eval('...returnValue') is 1 character shorter than n=>{...return returnValue}.

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

Output

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

Haskell, 44 bytes

Heavily inspired by Nimi's earlier answer, replacing the predicate with a 2-byte shorter one based on any with a pointfree lambda instead of a nested list comprehension.

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

Try it online!
(thanks to Laikoni for the accurate TIO link)

Explanation:

[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
\$\endgroup\$
0
1
\$\begingroup\$

Husk, 14 12 bytes

↑fṠöV¬thM%ḣN

Try it online!

-2 bytes from Jo King.

Husk, 8 bytes

↑fȯ≠2LḊN

Try it online!

Uses the ivisors function, if that is okay.

\$\endgroup\$
0
\$\begingroup\$

Japt, 9 bytes

Èâ ʨ3}jU

Try it

\$\endgroup\$
0
\$\begingroup\$

Vyxal, 7 bytes

∞'KḢḢ;Ẏ

Try it Online!

∞       # The set of all positive integers
 '   ;  # Filtered by...
  K     # The list of factors of n
   ḢḢ   # Has length > 2
      Ẏ # Get first n

Using a isprime builtin doesn't actually save any bytes as 1 and 0 are considered nonprime.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.