text:
List of first n prime numbers most efficiently and in shortest code
Rules are simple:

First n primes (not primes below n), should be printed to standard output separated by newlines (primes should be generated within the code)
primes cannot be generated by an inbuilt function or through a library, i.e. use of a inbuilt or library function such as, prime = get_nth_prime(n), is_a_prime(number), or factorlist = list_all_factors(number) won't be very creative.
Scoring - Say, we define Score = f([number of chars in the code]), O(f(n)) being the complexity of your algorithm where n is the number of primes it finds. So for example, if you have a 300 char code with O(n^2) complexity, score is 300^2 = 90000, for 300 chars with O(n*ln(n)), score becomes 300*5.7 = 1711.13 (let's assume all logs to be natural logs for simplicity)
Use any existing programming language, lowest score wins

Edit: Problem has been changed from finding 'first 1000000 primes' to 'first n primes' because of a confusion about what 'n' in O(f(n)) is, n is the number of primes you find (finding primes is the problem here and so complexity of the problem depends on the number of primes found)
Note: to clarify some confusions on complexity, if 'n' is the number of primes you find and 'N' is the nth prime found, complexity in terms of n is and N are not equivalent i.e. O(f(n)) != O(f(N)) as , f(N) != constant * f(n) and N != constant * n, because we know that nth prime function is not linear, I though since we were finding 'n' primes complexity should be easily expressible in terms of 'n'.
As pointed out by Kibbee, you can visit this site to verify your solutions (here, is the old google docs list)
Please Include these in your solution -

what complexity your program has (include basic analysis if not trivial)
character length of code
the final calculated score

This is my first CodeGolf Question so, if there is a mistake or loophole in above rules please do point them out.

This is very similar to http://codegolf.stackexchange.com/questions/5977/list-of-primes-under-a-million .

Nope I think it is very different this says to find first million primes not primes under million, the two problems are very different.

also scoring criterion here accounts for how efficiently you do it. I didn't find any ingrained judgement of efficiency there

My answer for that one was 1[\p:i.78498 my answer for this would be 1[\p:i.1000000. Even assuming that J's internal prime algorithm is O(n^2) my score would still only be 196.

Is it a direct function in J that gives primes? if that is so, use of such functions as one that gives you a prime or checks if the number is prime is unfair, and I will modify problem statement to incorporate that

@Optimus: You could do a md5sum of the primes file and print the handful of bytes, instead of uploading 8M.

I assume with complexity f(n) you mean n the number of primes to be calculated. In your question the number is fixed, so every solution would be O(1) and thus have the same score, namely 1. Also basis of the logarithm log2(n) in the complexity is not well-specified - but has influence on the proposed scoring.

@Gareth as I said "prime numbers should be generated within the code" using a direct function really makes it a moot point to ask this in the first place

@Howard I am a little weak on concepts, I fixed the number to be a million so that I could ask people to write shortest code to give out a specific output, but that shouldn't change the complexity of their algorithms for any other general case

It is not specified but basis of log is still determinable, say in a binary search analysis determines that the base of log is 2 since the depth of a binary tree is log2(n) (and not ln(n) or log10n), but I do know, log2(n), ln(n) and other bases are obtainable multiplying by a common constant factor), so for this problem we'll just say O(logx(n))==O(log2(n))==O(log10(n)) which is the way it is normally assumed anyway

@userunknown I think an md5sum would rarely be useful, there are many reasons that would cause the sum to be different for valid answers (one being windows \r\n vs linux \n, another being trailing spaces and endlines, encoding issues and many others)

Google docs version keeps crashing my browser.  Both Firefox and Chrome. Probably best to check out this version. http://primes.utm.edu/lists/small/millions/

@Optimus: If we have one line per prime, we surely have p\n and not \np, so there should be no problem with endlines. I don't see where spaces should occur from - they are out of spec. Encoding issues for decimal numbers? You're kidding! The only argument is MS-LFs, which can be clarified by 2 words like this: "\n EOLs" or healed with 2 md5sums. Another Idea would be a tail of the last 10, but this would simplify the job of finding the upper bound on calculation - depending on the way you do it. Instead of many words: d21960bf14feb65190e5540c2996d0df with Unix EOLs. Last ends in ...85863.

Nobody seems to manage to calculates their complexity properly. There's confusion about whether n is the number of primes or the maximum prime, and everyone ignores the fact that addition of numbers in the range 0..n is O(logn), and multiplication and division are even more expensive. I suggest that you give some example algorithms along with their correct complexity.

I was thinking about that right now, should I change the problem statement to say 'find first n primes' instead of a million, That would make thing clearer in terms of complexity

@ugoren I do plan to manage the scores and complexity myself, any help from anyone else is also welcome. I think after these edits, it should now be less ambiguous.

The current best known primality test for a k-bit number is O-tilde(k^6). This leads to the implication that anyone who claims a running time better than O-tilde(n ln n (ln(n ln n))^6) has misunderstood some part of the problem; and to the question as to how O-tilde complexities should be handled in the scoring.

Nobody has pointed out, that O(n) is equivalent to O(kn) (for constant k) in complexity terms, but not in score terms. For example, suppose my complexity is O(n^10). That is equivalent to O(n^10 * 1E-308), and I may still win the challenge with a huge program with terrible complexity.

I am voting to close this challenge as "unclear what you're asking", the issue is pointed out by JDL above, and so far there has been an exploit attempt.

Python (129 chars, O(n*log log n), score of 203.948)
I'd say the Sieve of Eratosthenes is the way to go. Very simple and relatively fast.
N=15485864
a=[1]*N
x=xrange
for i in x(2,3936):
 if a[i]:
  for j in x(i*i,N,i):a[j]=0
print [i for i in x(len(a))if a[i]==1][2:]

Improved code from before.
Python (191 156 152 chars, O(n*log log n)(?), score of 252.620(?))
I cannot at all calculate complexity, this is the best approximation I can give.
from math import log as l
n=input()
N=n*int(l(n)+l(l(n)))
a=range(2,N)
for i in range(int(n**.5)+1):
 a=filter(lambda x:x%a[i] or x==a[i],a)
print a[:n]

n*int(l(n)+l(l(n))) is the top boundary of the nth prime number.

The complexity (and thus score) calculation is based on the upper bound n but not on the number of primes. Thus, I assume the score has to be higher. See my comment above.

Upper bound n? What's that?

The upper bound here is N=15485864. For complexity calculations based on n=1000000, you can say N=n*log(n) (because of the density of primes).

If my score needs to be fixed, please fix it for me, I still don't have a good understanding of the scoring system.

@beary605 would it be ok if I modified the problems to finding first n primes? that would solve a lot of confusion on complexity and what n is in O(f(n))

Yes, it would be fine.

@Optimus, the outer loop executes O(n ln n) times. This is equivalent to trial division by primes only, so O((n ln n)^1.5 / ln(n ln n)) divisions, not taking into account the cost of a division. I believe Python has unbounded integers, but I don't know what division algorithm it uses for them.

@PeterTaylor Can we assume for sanity that each division takes same O(k**1.5) time in every programming language without creating a big exploitable loophole? If so, we could say that, O[(nln(n))**1.5 / ln(nln(n))] will be the complexity of beary605's solution and hence score becomes 3178.93.. also then, walpen's solution's complexity can be appropriately determined

@Optimus, not really. That creates a fixed size limit which allows an argument to be made for a O(1) solution with a large constant.

I have updated my algorithm, what is it now?

@PeterTaylor As I naively did not expect before floating this problem, the complexity analysis for all of solutions are pretty complicated. I had initially thought that I would personally verify each analysis and score, but my knowledge of computational complexity being very basic, it just seems that someone would then have to verify my verifications. If it's not too much trouble, could you help with this process. (I mean you're already helping a lot, But I don't know what to reply beary605 about his last comment for example.)

152*loglog152~=152*3~=450 how did you get 203?

The upper bound of n*int(l(n)+l(l(n))) is incorrect for the general case (e.g. for n in [6-9,12-18,31-40,…,251762-262020,…]) as you're taking a rather tight upper bound and lowering it by replacing the log term by its floored value, you'd have to use int(n*(l(n)+l(l(n)))) or n*(int(l(n)+l(l(n)))+1) instead.

Haskell, n^1.1 empirical growth rate, 89 chars, score 139 (?)
The following works at GHCi prompt when the general library that it uses have been previously loaded. Print n-th prime, 1-based:
let s=3:minus[5,7..](unionAll[[p*p,p*p+2*p..]|p<-s])in getLine>>=(print.((0:2:s)!!).read)
This is unbounded sieve of Eratosthenes, using a general-use library for ordered lists. Empirical complexity between 100,000 and 200,000 primes O(n^1.1). Fits to  O(n*log(n)*log(log n)).
About complexity estimation
I measured run time for 100k and 200k primes, then calculated logBase 2 (t2/t1), which produced n^1.09. Defining g n = n*log n*log(log n), calculating logBase 2 (g 200000 / g 100000) gives n^1.12.
Then, 89**1.1 = 139, although g(89) = 600.        --- (?)
It seems that for scoring the estimated growth rate should be used instead of complexity function itself. For example, g2 n = n*((log n)**2)*log(log n) is much better than n**1.5, but for 100 chars the two produce score of 3239 and 1000, respectively. This can't be right. Estimation on 200k/100k range gives logBase 2 (g2 200000 / g2 100000) = 1.2 and thus score of 100**1.2 = 251.
Also, I don't attempt to print out all primes, just the n-th prime instead.
No imports, 240 chars. n^1.15 empirical growth rate, score 546.
main=getLine>>=(print.s.read)
s n=let s=3:g 5(a[[p*p,p*p+2*p..]|p<-s])in(0:2:s)!!n
a((x:s):t)=x:u s(a$p t)
p((x:s):r:t)=(x:u s r):p t
g k s@(x:t)|k<x=k:g(k+2)s|True=g(k+2)t
u a@(x:r)b@(y:t)=case(compare x y)of LT->x:u r b;EQ->x:u r t;GT->y:u a t

the aforementioned library is module Data.List.Ordered, from package data-ordlist. for "empirical orders of growth" see this.

This is so easy even my text editor can do this!
Vim: 143 keystrokes (115 actions): O(n^2*log(n)): Score: 101485.21
Submission:
qpqqdqA^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"ddmpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qqpmp"aywgg@dqgg@p

Input: N should be on the first line of a blank document. After this is finished, each prime from 2 to N will be a separate line.
Running the Commands:
First, note that any commands with a caret in front of them mean you need to hold Ctrl and type the next letter (e.g. ^V is Ctrl-v and ^R is Ctrl-r).
This will overwrite anything in your @a, @b, @d, and @p registers.
Because this uses q commands, it can't just be placed in a macro. However, here are some tips for running it.

qpqqdq just clears registers
A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"dd will create a list of numbers 2 to N+1. This is a break between the two main parts, so once this is done, you shouldn't need to do it again
mpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qqpmp"aywgg@dqgg@p does need to be typed in one go. Try to avoid backspace as it may screw something up.

If you make a mistake, type qdqqpq then try this line again.

For large N, this is very slow. It took around 27 minutes to run N=5000; consider yourself warned.
Algorithm:
This uses a basic recursive algorithm for finding primes. Given a list of all primes between 1 and A, A+1 is prime if it not divisible by any of the numbers in the list of primes. Start at A = 2 and add primes to the list as they are found. After N recursions, the list will contain all the primes up to N.
Complexity
This algorithm has a complexity of O(nN), where N is the input number and n is the number of primes up to N. Each recursion tests n numbers, and N recursions are performed, giving O(nN).
However, N ~ n*log(n), giving the final complexity as O(n2*log(n))(https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number)
Explanation
It's not easy to discern the program flow from the vim commands, so I rewrote it in Python following the same flow. Like the Vim code, the python code will error out when it reaches the end. Python doesn't like too much recursion; if you try this code with N > 150 or so, it will reach the max recursion depth
N = 20
primes = range(2, N+1)

# Python needs these defined.
mark_p = b = a = -1

# Check new number for factors.
# This macro could be wrapped up in @d, but it saves space to leave it separate.
def p():
    global mark_d, mark_p, primes, a
    mark_d = 0
    print(primes)
    a = primes[mark_p]
    d()

# Checks factor and determine what to do next
def d():
    global mark_d, mark_p, a, b, primes
    b = primes[mark_d]
    if(a == b): # Number is prime, check the next number
        mark_p += 1
        p()
    else:
        if(a%b == 0): # Number is not prime, delete it and check next number
            del(primes[mark_p])
            p()
        else: # Number might be prime, try next possible factor
            mark_d += 1
            d()

mark_p = 0 #Start at first number
p()

Now, to break down the actual keystrokes!

qpqqdq Clears out the @d and @p registers. This will ensure nothing runs when setting up these recursive macros.
A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"dd Turns the input into a list of numbers from 2 to N+1. The N+1 entry is deleted as a side effect of setting up the @d macro.

Specifically, writes a macro that increments a number, then copies it on the next line, then it writes a 1 and executes this macro N times.

mpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0q writes the @d macro, which implements the d() function above. "If" statements are interesting to implement in Vim. By using the search operator *, it's possible to choose a certain path to follow. Breaking the command down further we get

mpqd Set the p mark here and start recording the @d macro. The p mark needs to be set so there is a known point to jump to as this runs
o^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc> Writes the if/else statement text
0*w*wyiWdd@0 actually executes the if statement.
Before executing this command, the line will contain @a @b 0 0 `pj@p @a 0 (@a%@b) `pdd@p 0 `dj@d
0 moves the cursor to the beginning of the line
*w*w Moves the cursor to the code to execute next

if @a == @b, that is `pj@p, which moves to the next number for @a and runs @p on it.
if @a != @b and @a%@b == 0, that is `pdd@p, which deletes the current number @a, then runs @p on the next one.
if @a != @b and @a%%b != 0, that is `dj@d, which checks the next number for @b to see if it is a factor of @a

yiWdd@0 yanks the command into the 0 register, deletes the line and runs the command
q ends the recording of the @d macro

When this is first run, the `pdd@p command is run, deleting the N+1 line.
qpmp"aywgg@dq writes the @p macro, which saves the number under the cursor, then goes to the first entry and runs @d on that.
gg@p actually executes @p so that it will iterate over the whole file.

Haskell, 72 89 chars, O(n^2), Score 7921
Highest score per char count wins right? Modified for first N. Also I apparently can't use a calculator, so my score is not as abysmally bad as I thought. (using the complexity for basic trial division as found in the source below).
As per Will Ness the below is not a full Haskell program (it actually relies on the REPL). The following is a more complete program with a pseudo-sieve (the imports actually save a char, but I dislike imports in code golf).
main=getLine>>= \x->print.take(read x).(let s(x:y)=x:s(filter((>0).(`mod`x))y)in s)$[2..]

This version is undoubtedly (n^2). The algorithm is just a golf version of the naive ``sieve'', as seen here
Old ghci 1 liner
getLine>>= \x->print.take(read x)$Data.List.nubBy(\x y->x`mod`y==0)[2..]

Leaving up the old, cheating answer because the library it links to is pretty nice.
print$take(10^6)Data.Numbers.Primes.primes

See here for an implementation and the links for the time complexity. Unfortunately wheels have a log(n) lookup time, slowing us down by a factor.

•primes cannot be generated by an inbuilt functon or through a library

@walpen I'am sorry I modified the rules without notification, please make the changes as you see fit

Wouldn't the complexity be something like O((n ln n)^1.5 ln (n ln n)^0.585)? (Or O((n ln n)^1.5 ln (n ln n)) if Haskell uses naive division rather than, as I've assumed, Karatsuba)

No, because that gives me a horrendous score :/. But I'm sure you're right. It just looked like trial division, and that's the time complexity of trial division (maybe, according to my poor reading comprehension of a possibly wrong source) so I picked that. For now I'll call my score NaN, that seems safe.

I'm assuming (my Haskell is negligible, but I know how it would be natural to do it in SML...) that you're only doing trial division by smaller primes, in which case trial division on a P does O(P^0.5 / ln P) divisions. But if P has k bits, a division takes O(k^1.585) (Karatsuba) or O(k^2) (naïve) time, and you need to run through O(n lg n) numbers of length O(ln(n lg n)) bits.

BTW at 72 chars, if you're on the absolute cutting edge of primality testing, you'd have a score just short of 11 million. The rest of the current answers would be far far worse.

Oh, so now that makes sense. I tend to pretend that all math takes constant time out of laziness (I program in Haskell after all).

Hi, I think we can leave out the imports... let's say we use :m +Module, how this translates into code? It doesn't. In the mean time I followed your lead and posted something w/out main= ;) will add that now to my post.

I think the whole import thing, and whether an answer can just run in the REPL is a question for meta. Most of the Haskell answers I've seen are self standing, compiled programs, but I do not know if they have to be.

one char less: from http://www.haskell.org/haskellwiki/Blow_your_mind by BMeph, March 2008: nubBy(((>1).).gcd)[2..]!

The following is interesting in that it entirely avoids the use of numbers. So instead it outputs an infinite string of '.' and 'p' characters:  let f='.';o c(x:y)=x:c y;z c(x:y)=f:c y;p n='p':ap fix p(o.n)in f:f:p z

C#, 447 Characters, Bytes 452,  Score ?
using System;namespace PrimeNumbers{class C{static void GN(ulong n){ulong primes=0;for (ulong i=0;i<(n*3);i++){if(IP(i)==true){primes++;if(primes==n){Console.WriteLine(i);}}}}static bool IP(ulong n){if(n<=3){return n>1;}else if (n%2==0||n%3==0){return false;}for(ulong i=5;i*i<=n;i+=6){if(n%i==0||n%(i+2)==0){return false;}}return true;}static void Main(string[] args){ulong n=Convert.ToUInt64(Console.ReadLine());for(ulong i=0;i<n;i++){GN(i);}}}}

scriptcs Variant, 381 Characters, 385 Bytes, Score ?
using System;static void GetN(ulong n){ulong primes=0;for (ulong i=0;i<(n*500);i++){if(IsPrime(i)==true){primes++;if(primes==n){Console.WriteLine(i);}}}}public static bool IsPrime(ulong n){if(n<=3){return n>1;}else if (n%2==0||n%3==0){return false;}for(ulong i=5;i*i<=n;i+=6){if(n%i==0||n%(i+2)==0){return false;}}return true;}ulong n=Convert.ToUInt64(Console.ReadLine());for(ulong i=0;i<n;i++){GetN(i);}

If you install scriptcs then you can run it.
P.S. I wrote this in Vim :D

You can save some characters by removing some unnecessary whitespace. For example, it's not necessary to put whitespace around an = and < sign. Also, I don't think there's a difference in bytes and characters for this code -- it's 548 characters and 548 bytes.

Oh thanks, this is my first CodeGolf!

Scala 263 characters
Updated to fit to the new requirements. 25% of the code deal with finding a reasonable upper bound to calculate primes below.
object P extends App{
def c(M:Int)={
val p=collection.mutable.BitSet(M+1)
p(2)=true
(3 to M+1 by 2).map(p(_)=true)
for(i<-p){
var j=2*i;
while(j<M){
if(p(j))p(j)=false
j+=i}
}
p
}
val i=args(0).toInt
println(c(((math.log(i)*i*1.3)toInt)).take(i).mkString("\n"))
}

I got a sieve too.
Here is an empirical test of the calculation costs, ungolfed for analysis:
object PrimesTo extends App{
    var cnt=0
    def c(M:Int)={
        val p=(false::false::true::List.range(3,M+1).map(_%2!=0)).toArray
        for (i <- List.range (3, M, 2)
            if (p (i))) {
                var j=2*i;
                while (j < M) {
                    cnt+=1
                    if (p (j))
                        p(j)=false
                    j+=i}
            }
        (1 to M).filter (x => p (x))
    }
    val i = args(0).toInt
    /*
        To get the number x with i primes below, it is nearly ln(x)*x. For small numbers
        we need a correction factor 1.13, and to avoid a bigger factor for very small
        numbers we add 666 as an upper bound.
    */
    val x = (math.log(i)*i*1.13).toInt+666
    println (c(x).take (i).mkString("\n"))
    System.err.println (x + "\tcount: " + cnt)
}
for n in {1..5} ; do i=$((10**$n)); scala -J-Xmx768M P $i ; done

leads to following counts:
List (960, 1766, 15127, 217099, 2988966)

I'm not sure how to calculate the score. Is it worth to write 5 more characters?
scala> List(4, 25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534).map(x=>(math.log(x)*x*1.13).toInt+666)
res42: List[Int] = List(672, 756, 1638, 10545, 100045, 1000419, 10068909, 101346800, 1019549994)

scala> List(4, 25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534).map(x=>(math.log(x)*x*1.3)toInt)
res43: List[Int] = List(7, 104, 1119, 11365, 114329, 1150158, 11582935, 116592898, 1172932855)

For bigger n it reduces the calculations by about 16% in that range, but afaik for the score formula, we don't consider constant factors?
new Big-O considerations:
To find 1 000, 10 000, 100 000 primes and so on, I use a formula about the density of primes x=>(math.log(x)*x*1.3 which determines the outer loop I'm running.
So for values i in 1 to 6=> NPrimes (10^i) runs 9399, 133768 ... times the outer loop.
I found this O-function iteratively with help from the comment of Peter Taylor, who suggested a much higher value for exponentiation, instead of 1.01 he suggested 1.5:
def O(n:Int) = (math.pow((n * math.log (n)), 1.01)).toLong

O: (n: Int)Long
val ns = List(10, 100, 1000, 10000, 100000, 1000*1000).map(x=>(math.log(x)*x*1.3)toInt).map(O)

ns: List[Long] = List(102, 4152, 91532, 1612894, 25192460, 364664351)
 That's the list of upper values, to find primes below (since my algorithm has to know this value before it has to estimate it), send through the O-function, to find similar quotients for moving from 100 to 1000 to 10000 primes and so on:

(ns.head /: ns.tail)((a, b) => {println (b*1.0/a); b})
40.705882352941174
22.045279383429673
17.62109426211598
15.619414543051187
14.47513863274964
13.73425213148954

This are the quotients, if I use 1.01 as exponent. Here is what the counter finds empirically:
ns: Array[Int] = Array(1628, 2929, 23583, 321898, 4291625, 54289190, 660847317)

(ns.head /: ns.tail)((a, b) => {println (b*1.0/a); b})
1.799140049140049
8.051553431205189
13.649578085909342
13.332251210010625
12.65003116535112
12.172723833234572

The first two values are outliers, because I have make a constant correction for my estimation formular for small values (up to 1000).
With Peter Taylors suggestion of 1.5 it would look like:
245.2396265560166
98.8566987153728
70.8831374743478
59.26104390040363
52.92941829568069
48.956394784317816

Now with my value I get to:
O(263)
res85: Long = 1576

But I'm unsure, how close I can come with my O-function to the observed values.

Sorry I made some changes to the problem statement to reduce some ambiguity related to complexity, (I am sure your solution wouldn't change much)

This is effectively trial division by primes. The number of times through the inner loop is O(M^1.5 / ln M), and each time through you do O(ln M) work (addition), so overall it's O(M^1.5) = O((n ln n)^1.5).

With ^1.02 instead of ^1.5 def O(n:Int) = (math.pow((n * math.log (n)), 1.02)).toLong I get much closer to the values, empirically found with my counter. I insert my findings in my post.

GolfScript (45 chars, score claimed ~7708)
~[]2{..3${1$\%!}?={.@\+\}{;}if)1$,3$<}do;\;n*

This does simple trial division by primes. If near the cutting edge of Ruby (i.e. using 1.9.3.0) the arithmetic uses Toom-Cook 3 multiplication, so a trial division is O(n^1.465) and the overall cost of the divisions is O((n ln n)^1.5 ln (n ln n)^0.465) = O(n^1.5 (ln n)^1.965)†. However, in GolfScript adding an element to an array requires copying the array. I've optimised this to copy the list of primes only when it finds a new prime, so only n times in total. Each copy operation is O(n) items of size O(ln(n ln n)) = O(ln n)†, giving O(n^2 ln n).
And this, boys and girls, is why GolfScript is used for golfing rather than for serious programming.
† O(ln (n ln n)) = O(ln n + ln ln n) = O(ln n). I should have spotted this before commenting on various posts...

QBASIC, 98 Chars, Complexity N Sqrt(N), Score 970
I=1
A:I=I+2
FOR J=2 TO I^.5
    IF I MOD J=0 THEN GOTO A
NEXT
?I
K=K+1
IF K=1e6 THEN GOTO B
GOTO A
B:

I've modified the problem statement a bit, its now find first 'n' primes, I am sorry for no notification

I suppose we can assume "in-source" input for this program; i.e., the input is the numeral right after the IF K= (so the program length would not include the numeral). As it stands, the program prints the first n primes not including 2, which can be fixed by adding ?2 at the beginning, and changing K=... to K=...-1. The program can also be golfed a bit by taking the spaces out of J=2 TO, J=0 THEN, K=...-1 THEN, and by removing the indenting. I believe this results in a 96-character program.

Ruby 66 chars, O(n^2) Score - 4356
lazy is available since Ruby 2.0, and 1.0/0 is a cool trick to get an infinite range:
(2..(1.0/0)).lazy.select{|i|!(2...i).any?{|j|i%j==0}}.take(n).to_a

You can shave one char off by changing it to (2..(1.0/0)).lazy.select{|i|!(2...i).any?{|j|i%j<1}}.take(n).to_a

Or even: (This makes the solution less efficient, but it does not change the upper O(n²) bound) (2..(1.0/0)).lazy.select{|i|(2..i).one?{|j|i%j<1}}.take(n).to_a. This shaves off two more characters.

Well changing it to (2..(1.0/0)).lazy.select{|i|!(2...i).any?{|j|i%j<1}}.first(n) will result in  61 chars.

Ruby, 84 chars, 84 bytes, score?
This one is probably a little too novice for these parts, but I had a fun time doing it. It simply loops until f (primes found) is equal to n, the desired number of primes to be found.
The fun part is that for each loop it creates an array from 2 to one less than the number being inspected. Then it maps each element in the array to be the modulus of the original number and the element, and checks to see if any of the results are zero.
Also, I have no idea how to score it.
Update
Code compacted and included a (totally arbitrary) value for n
n,f,i=5**5,0,2
until f==n;f+=1;p i if !(2...i).to_a.map{|j|i%j}.include?(0);i+=1;end

Original
f, i = 0, 2
until f == n
  (f += 1; p i) if !(2...i).to_a.map{|j| i % j}.include?(0)
  i += 1
end

The i += 1 bit and until loop are sort of jumping out at me as areas for improvement, but on this track I'm sort of stuck. Anyway, it was fun to think about.

Perl - 94 characters, O(n log(n)) - Score: 427
perl -wle '$n=1;$t=1;while($n<$ARGV[0]){$t++;if((1x$t)!~/^1?$|^(11+?)\1+$/){print $t;$n++;}}'

Python - 113 characters
import re
z = int(input())
n=1
t=1
while n<z:
    t+=1
    if not re.match(r'^1?$|^(11+?)\1+$',"1"*t):
        print t
        n+=1

Scala, 124 characters
object Q extends App{Stream.from(2).filter(p=>(2 to p)takeWhile(i=>i*i<=p)forall{p%_!= 0})take(args(0)toInt)foreach println}

Simple trial division up to square root. Complexity therefore should be
    O(n^(1.5+epsilon))
124^1.5 < 1381, so that would be my score i guess?

AWK, 96 86 bytes
Subtitle: Look Mom! Only adding and some bookkeeping!
File fsoe3.awk:
{for(n=2;l<$1;){if(n in L)p=L[n]
else{print p=n;l++}
for(N=p+n++;N in L;)N+=p
L[N]=p}}

Run:
$ awk -f fsoe3.awk <<< 5
2
3
5
7
11
$ awk -f fsoe3.awk <<< 1000 | wc -l
1000

BASH, 133 bytes
File x.bash:
a=2
while((l<$1));do if((b[a]))
then((c=b[a]));else((c=a,l++));echo $a;fi;((d=a+c))
while((b[d]));do((d+=c));done
((b[d]=c,a++));done

Run:
$ bash x.bash 5
2
3
5
7
11
$ bash x.bash 1000 | wc -l
1000

Primes get calculated by letting the already found primes jump on the "tape of positive integers". Basically it is a serialised Sieve Of Eratosthenes.
from time import time as t

L = {}
n = 2
l = 0

t0=t()

while l<1000000:

        if n in L:
                P = L[n]
        else:
                P = n
                l += 1
                print t()-t0

        m = n+P
        while m in L:
                m += P
        L[m] = P

        n += 1

...is the same algorithm in Python and prints out the time when the l-th prime was found instead of the prime itself.
The output plotted with gnuplot yields the following:

The jumps probably have something to do with file i/o delays due to writing buffered data to disk...
Using much larger numbers of primes to find, will bring additional system dependent delays into the game, e.g. the array representing the "tape of positive integers" grows continuously and sooner or later will make every computer cry for more RAM (or later swap).
...so getting an idea of the complexity by looking at the experimental data does not really help a lot... :-(

Now counting the additions needed to find n primes:
cells = {}
current = 2
found = 0

additons = 0

while found < 10000000:

        if current in cells:
                candidate = cells[current]
                del cells[current] # the seen part is irrelevant
        else:
                candidate = current
                found += 1 ; additons += 1
                print additons

        destination = current + candidate ; additons += 1
        while destination in cells:
                destination += candidate ; additons += 1
        cells[destination] = candidate

        current += 1 ; additons += 1

How'd you make those graphs?

Gnuplot with set term xterm and then screenshot of xterm's graphics-window (probably a near to forgotten feature). ;-)

awk 45 (complexity N^2)
another awk, for primes up to 100 use like this
awk '{for(i=2;i<=sqrt(NR);i++) if(!(NR%i)) next} NR>1' <(seq 100)

code golf counted part is
{for(i=2;i<=sqrt(NR);i++)if(!(NR%i))next}NR>1

which can be put in a script file and run as awk -f prime.awk <(seq 100)

Scala 121 (99 without the Main class boilerplate)
object Q extends App{Stream.from(2).filter{a=>Range(2,a).filter(a%_==0).isEmpty}.take(readLine().toInt).foreach(println)}

Haskell (52²=2704)
52`take`Data.List.nubBy(((1<).).gcd)[2..]`forM_`print

Perl 6, 152 bytes, O(n log n log (n log n) log (log (n log n))) (?), 9594.79 points
According to this page, the bit complexity of finding all primes up to n is O(n log n log log n); the complexity above uses the fact that the nth prime is proportional to n log n.
my \N=+slurp;my \P=N*(N.log+N.log.log);my @a=1 xx P;for 2..P.sqrt ->$i {if @a[$i] {@a[$_*$i]=0 for $i..P/$i}};say $_[1] for (@a Z ^P).grep(*[0])[2..N+1]

does not qualify, do it in Wentel to qualify

Pardon, but what do you mean?

for the bounty (fiiiiiiiiilerrrrr)

Python 3, 117 106 bytes
This solution is slightly trivial, as it outputs 0 where a number is not prime, but I'll post it anyway:
r=range
for i in[2]+[i*(not 0 in[i%j for j in r(3,int(i**0.5)+1,2)])for i in r(3,int(input()),2)]:print(i)

Also, I'm not sure how to work out the complexity of an algorithm. Please don't downvote because of this. Instead, be nice and comment how I could work it out. Also, tell me how I could shorten this.

I think you can put the print(i) on the same line as the for loop and remove the spaces at in [2], 0 if, 0 in [i%j and +1,2)] else.

@daHugLenny Wow, thanks so much! I'll edit my post in a sec. :-D

@daHugLenny Would you know how to calculate efficiency by any chance?

No, sorry. (Comments have to be at least 15 chars long)

Thanks anyway. You've made my program the shortest one here!

Groovy (50 Bytes) - O(n*sqrt(n)) - Score 353.553390593
{[1,2]+(1..it).findAll{x->(2..x**0.5).every{x%it}}}

Takes in n and outputs all numbers from 1 to n which are prime.
The algorithm I chose only outputs primes n > 2, so adding 1,2 at the beginning is required.
Breakdown
x%it - Implicit truthy if it is not divisible, falsy if it is.
(2..x**0.5).every{...} - For all the values between 2 and sqrt(x) ensure that they are not divisible, for this to return true, must return true for every.
(1..it).findAll{x->...} - For all values between 1 and n, find all that fit the criteria of being non-divisible between 2 and sqrt(n).
{[1,2]+...} - Add 1 and 2, because they are always prime and never covered by algorithm.

Racket 155 bytes
(let p((o'(2))(c 3))(cond[(>=(length o)n)(reverse o)][(ormap(λ(x)(= 0(modulo c x)))
(filter(λ(x)(<= x(sqrt c)))o))(p o(add1 c))][(p(cons c o)(add1 c))]))

It keeps a list of prime numbers found and checks divisibility of each next number by primes already found. Moreover, it checks only upto the square root of number being tested since that is enough.
Ungolfed:
(define(nprimes n)
  (let loop ((outl '(2))                   ; outlist having primes being created
             (current 3))                  ; current number being tested
  (cond
    [(>= (length outl) n) (reverse outl)]  ; if n primes found, print outlist.
    [(ormap (λ(x) (= 0 (modulo current x))) ; test if divisible by any previously found prime
            (filter                         ; filter outlist till sqrt of current number
             (λ(x) (<= x (sqrt current)))
             outl))
     (loop outl (add1 current)) ]           ; goto next number without adding to prime list
    [else (loop (cons current outl) (add1 current))] ; add to prime list and go to next number
    )))

Testing:
(nprimes 35)

Output:
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149)

Javascript, 61 chars
f=(n,p=2,i=2)=>p%i?f(n,p,++i):i==p&&n--&alert(p)||n&&f(n,++p)

A bit worse than O(n^2), will run out of stack space for large n.


text:
Range of numbers
Came over a similar problem in a project I'm working on and found it quite hard to solve it without excesive use of if. I'm eager to see if anyone can come up with more elegant solutions to this, with the aribitary numbers I have given to the line segments.
The problem
You are given two integers that act like the end points of a line segment. Determine what existing line segments this line will overlap with.
Intervals / line segments
The other lines, named Q, W, E, R and T, are as following:
Q:   0 -   7
W:   8 -  18
E:  19 -  32
R:  33 - 135
T: 136 -

The last one, T, starts at 136 and has no end point.
Example
Given the numbers 5 and 27, the line will overlapp with Q, W and E. This can be roughly illustrated like this:
    Q  W   E       R           T
---+--+---+-------+-----------+-----
   0  7   18      32         135

     +---------+
     5         27

  (somewhat arbitrary scale)

Input
Two integers from stdin.
Output
A String containing the names of the lines that our new line overlap with, for instance in the example above QWE.
Rules
Shortest code.

The numbers 18 and 32 should give WE right?

Do we hard-code the line segments, then?

@grc: yes. Peter: yes.

GolfScript (43 32 30 chars)
Contains escape characters. As a hex dump:
00000000  7e 29 27 51 08 57 0b 45  0e 52 67 27 32 2f 7b 29  |~)'Q.W.E.Rg'2/{)|
00000010  2a 7d 25 27 54 27 32 24  2a 2b 3c 3e 2e 26        |*}%'T'2$*+<>.&|

Base-64 encoded:
fiknUQhXC0UOUmcnMi97KSp9JSdUJzIkKis8Pi4m

Using bold to indicate escape characters:
~)'Q^HW^KE^NRg'2/{)*}%'T'2$*+<>.&
Thanks to Howard for the suggestion to use escape characters.

I was just trying this out in the online golfscript tester to see how it worked and kept getting a 'negative argument' error at the {~*}% bit. I preceded the code with 5 27. What am I doing wrong?

@Gareth, the tester starts with the empty string on the stack from stdin; you need to pop that with ; and then add the string which you're simulating as coming from stdin. So you need to precede with ;'5 27' rather than just 5 27.

Maybe you can use 'Q\x8W\x0bE\xeRgT\x1c'2/{)*}% to generate your string? It is -5 chars if you use escapes and even less if you directly encode the values.

@Howard correct, but the string should be enclosed in double quotes

@Howard, not quite: the 9$ after 'T' was to ensure that the string is long enough not to be truncated to the empty string by <, so that still needs some special treatment. But otherwise, yes, that works and is useful.

Great solution! Proof it works: http://golfscript.apphb.com/?c=Oyc1IDI1JwoKfiknUQhXC0UOUmcnMi97KSp9JSdUJzIkKis8Pi4m

APL (39)
'QWERT'/⍨1↓⊃≠/1 0⌽¨0,¨0 7 18 32 135∘<¨⎕

Takes input as two whitespace-separated numbers.
Explanation:

0 7 18 32 135∘<¨⎕: For each number in the input, see if 0, 7, 18, 32, and/or 135 is smaller than the number. If the input was 5 27 we now have (1 0 0 0 0) (1 1 1 0 0). (The first one is taken to be the start of the line and the second one the end).
1 0⌽¨0,¨: Prefix a zero to each of those lists and rotate the first one left by 1. (We now have (1 0 0 0 0 0) (0 1 1 1 0 0)).
≠/: Gives a list where the individual items of the two input lists were not equal. (We now have 1 1 1 1 0 0).
1↓⊃: Remove the first item from this list. The other five stand for whether or not to display a Q, W, E, R or T.
'QWERT'/⍨: For each letter, output N of those letters, where N is the corresponding value in the list on the right. Since the list was 1 1 1 0 0 the answer is QWE.

Nice soution and very nice explanation!

Python 82 84
There you are. Edit: Fixed for inputs like -1 10 and -10 -1 for 2 chars
z=lambda a:(a>7)+(a>18)+(a>32)+(a>135)+1
a,b=input()
print"QWERT"[z(a)-1:z(b)*(b>0)]

J, 58 54 characters
'QWERT '#~0 8 19 33 136 _(([<1{])*(1|.[>:0{]))".1!:1[1

Reads one line of input from the keyboard.

Aargh! Hacky ugly code! ;)

Python, 79
x,y=input()
print"".join(set(("Q"*8+"W"*11+"E"*14+"R"*103)[x:y+1]))+"T"*(y>135)

It could be a lot shorter if it's allowed to leave duplicates in the output, but I figured that would be bending the rules a bit.

How does that handle test case 500 510?

Not very well. I've fixed it now.

Try -10 1. It's a pretty box clever answer though.

K, 68 58

{$[y>135;`T,;]`Q`W`E`R@&max'(x+!1+y-x)in/:(!8;8+!11;19+!15;33+!104)}

{$[y>135;"T",;]"QWER"@&(=).'(y>'0,-1_a),'x<'a:8 19 33 136}

.
k){$[y>135;"T",;]"QWER"@&(=).'(y>'0,-1_a),'x<'a:8 19 33 136}[5;27]
"QWE"
k){$[y>135;"T",;]"QWER"@&(=).'(y>'0,-1_a),'x<'a:8 19 33 136}[0;139]
"TQWER"
k){$[y>135;"T",;]"QWER"@&(=).'(y>'0,-1_a),'x<'a:8 19 33 136}[20;135]
"ER"
k){$[y>135;"T",;]"QWER"@&(=).'(y>'0,-1_a),'x<'a:8 19 33 136}[32;135]
"ER"

PHP, 159 characters
<?$b=array(0=>"Q",8=>"W",19=>"E",33=>"R",136=>"T",1e9=>"");$a=split(" ",fgets(STDIN));foreach($b as $k=>$v){if($a[0]<$k&&$a[1]>=$j)$o.=$p;$p=$v;$j=$k;}echo $o;

With line breaks:
<?
$b=array(0=>"Q",8=>"W",19=>"E",33=>"R",136=>"T",1e9=>"");
$a=split(" ",fgets(STDIN));
foreach($b as $k=>$v)
{
    if($a[0]<$k&&$a[1]>=$j)
        $o.=$p;
    $p=$v;
    $j=$k;
}
echo $o;

Assumes that the line segments are contiguous and non-overlapping as in the given example.
Working version at ideone.com.

http://ideone.com/DANYq should output T, outputs nothing.

@PeterTaylor Bugger. I'll have a look.

@PeterTaylor Added an ugly hacky fix for an extra 8 characters. Maybe I'll stick to J - at least then not many people can understand how hacky and ugly my code is. :-)

I think $a[1]>$j should be $a[1]>=$j (i.e. greater OR EQUAL) to correctly hit the edges of each range. e.g. 135 136 should output RT but just outputs R.

Scala 113
val i=Seq(0,8,19,33,136,(1<<31)-1)
i.zip(i.tail)zip("qwert")filter(x=>x._1._2>readInt&&x._1._1<=readInt)map(_._2)

Handles test cases 5-27(QWE), 400-500(T), 40-40(R), 33-33(R).

400-500 should be T. 40-40 and 33-33 should be R.

@marinus: You're right. For the R-cases, it was a sloppy testing, but I have to rework the solution to get the case of (400-500) right.

M (Micronetics System MUMPS 4.4) - 82 Chars
f i=1:1:2 r a s x=(a>0)+(a>7)+(a>18)+(a>32)+(a>135) w:$d(y) $e("QWERT",y,x) s y=x

5-27(QWE), 400-500(T), 40-40(R), 33-33(R).

PHP 119
<?fscanf(STDIN,'%d%d',$a,$b);foreach(array('Q'=>7,'W'=>18,'E'=>32,'R'=>135,'T'=>136)as$x=>$y)echo$y>=$a&&$y<=$b?$x:'';

Getting Input from command-line reduces the size, but, I don't think it is applicable here, but still:
PHP 111
<?list(,$a,$b)=$argv;foreach(array('Q'=>7,'W'=>18,'E'=>32,'R'=>135,'T'=>136)as$x=>$y)echo$y>=$a&&$y<=$b?$x:'';

Mathematica
Cases[{{q, 0, 7}, {w, 8, 18}, {e, 19, 32}, {r, 33, 135}, {t, 136, \[Infinity]}},
  {a_, b_, c_} /; Length@IntervalIntersection[Interval[{b, c}], Interval[{5, 27}]] !=0
   :> a]

Jelly, 27 bytes (improvements wanted!)
®Ṁṭ“®¿Çg‘
ØQFḣ5ż¢Œṙ
Ɠ©r/ị¢Q

Try it online!
®Ṁṭ“®¿Çg‘    actual runlengths here
®Ṁ           recall the input numbers, and get the maximum of them
  ṭ          append that max (to be used as runlength for 'T') to...
   “®¿Çg‘    [ 8, 11, 14, 103 ] (listed as base-250 numbers on jelly's codepage)

ØQFḣ5ż¢Œṙ    run-length encoding function:
ØQF          get "QWERTYUIOPASDF..."
   ḣ5        get the first 5 characters of that to yield "QWERT"
     ż¢      zip it with the above link (RLE values)...
       Œṙ    and then apply RLE decode to produce the uncompressed string

Ɠ©r/ị¢Q      main function:
Ɠ©           take two integers from stdin, evaluate them and save them to a register
  r/         take the range between them (technically a fold)
    ị¢       for each element in the range, get the value at its index in the link above...
      Q      and return all the unique values (remove duplicates).

I think that I'm doing something wrong / non-optimally with the register save / recall to get the max value. If I just make that value 250, the program goes down to just 22 bytes:
ØQFḣ5ż“®¿Çgż‘Œṙ
Ɠr/ị¢Q

Try it online!

Maybe you can do something like >“©×þ⁶‘S‘, i.e. 1+sum(x>i for i in [7,18,32,135]), and then ịndex into ØQF¤. That's 21 bytes. But then inlining the whole thing gets you 20 bytes: Ɠr/>€“©×þ⁶‘ḅ1‘ịØQF¤Q using the ḅ1 trick

Err, I guess that trick isn't strictly necessary here because it's just as long as S€ :) but it's good to know about!

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Implementing Binary Arithmetic
Given two binary numbers (strings containing 0s and 1s), perform operations on them, with one problem: You must keep them in binary. That means no going binary(integer(n1)+integer(n2)) or anything like that.
Input: Two binary numbers, n1 and n2, and a number between 0 and 3, o, defining the operator. The two binary numbers will be the same length.
Output:
If o is 0, return n1+n2 as a binary number.
If o is 1, return n1-n2 as a binary number.
If o is 2, return n1*n2 as a binary number.
If o is 3, return n1/n2 as a binary number, using floor division.
The output will not be the same length as the input. Please truncate all leading zeros.
If you implement Two's Complement, subtract 10% off your character count, up to a limit of 50. Truncate to length(n1)+length(n2) digits.
Test Cases:
n1=01010, n2=10101, o=0: 11111
n1=11110, n2=01010, o=1: 10100
n1=0010, n2=1000, o=2: 10000
n1=1011010, n2=0010001, o=3: 101
Shortest code wins. Good luck!

I think you should rethink the "subtract 50" thing. I can see it being implemented in much less characters than that. Perhaps "10% up to 50" would be a better choice.

When you say "binary numbers" you don't actually mean "binary numbers", do you? If you mean "strings containing only characters '0' and '1'" then say that.

The binary numbers will be the same length, but can we assume that there will be no overflow, so the result is the same length? (Is "n1=11111, n2=11111, o=0" possible?)

How do we represent negative numbers (i.e. what is the basis 2^n/how do we write -1)?

@schnaader The third example (multiply) shows otherwise.

Thank you for all your input. I have fixed the question, or at least I think I did. Keep it coming!

@Howard: Two's Complement

@beary605 In two's complement the most significant bit being set indicates a negative number - what is the word size we're working with here?

Do we need to truncate leading zeros?

@Gareth: Let's say a reasonable amount. Kieth Randall: Yes.

@beary605 That's not very helpful, unfortunately. Let me ask it another way: if the input is n1=0000, n2=0001, o=1 should the output be 11111111, 1111111111111111, or something else?

I see what you mean now. In that case, truncate the 1s to the length(n1)+length(n2).

@beary605 Do we use this word size also for the input? That would mean that input numbers are always non-negative?

No, the input will be a random number of digits.

Truncating doesn't help in identifying negative numbers. I still think we need to know whether they're 8 digits long, 16, 32, 64 or something else. And btw.: My computer always calculates in binary. P.S.: The operator should be given as 0, 01, 10 or 11 respectively, just for aesthetic reasons.

A negative number has a turned-on bit in the front; both inputs are the same length. To me, that should be sufficient enough information.

I've never seen a datatype with 5 bits like in the examples 1 and 2. In example 3 you multiply 2 * -8, according to your last explanation. -16 is the decimal result, but it doesn't fit a 4 bit Int. Now you show a 5-bit Int as result, but in a 5 bit data type 1000 wouldn't be -8, but 8. So we have to assume an autowidening datatype? I'm fine with that, but it isn't evident from the examples alone. And, something else: You have to annotate an answer with @Name to make the system inform somebody, that you answered his comment. Tab completion works thereby.

Python, 429 chars - 10% bonus = 386.1
Numbers are kept in little endian order, which is stretching the rules a bit but makes for easier processing.  Maximum number size is 32 bits.  Addition is standard, subtraction is implemented by x-y = x+~y+1 (throwing away the carry out of the 32 bits), multiplication is done using the Russian Peasant algorithm, and division is done with repeated subtraction.
z,i='01'
P=z*32
def A(x,y):
 r='';c=z
 for a,b in zip(x+P,y+P):k=(a+b+c).count(i);r+='0101'[k];c='0011'[k]
 return r[:32]
S=lambda x,y:A(A(x,''.join(chr(ord(c)^1)for c in y+P)),i)
def M(x,y):
 r=''
 while y:
  if y[0]==i:r=A(r,x)
  x=z+x;y=y[1:]
 return r
def D(x,y):
 x=(x+P)[:32];y=(y+P)[:32];r=''
 while x[::-1]>=y[::-1]:r=A(r,i);x=S(x,y)
 return r
def B(x,y,o):r=[A,S,M,D][o](x,y).rstrip(z)[:len(x)+len(y)];return[r,z][r=='']

B is the function of interest, here is its result on the test cases:
print B('01010','10101',0)
11111
print B('01111','01010',1)
00101
print B('0100','0001',2)
00001
print B('0101101','1000100',3)
101

lol, only answer, so answer to you! You can replace [A,S,M,D][o] with chr(65+o) in function B if you rename your operator functions A, B, C,and D, respectively.

@beary605: I think you'd have to use eval(chr(65+o)), which doesn't help.

Ah yeah. :X lol

Scala 785:
Let's start with a famous quote of Bjarne Stroustrup, the inventor of C++, which in his great wisdom told us:

Don't divide without necessity!

To make a submission to this fine question, we not only have to perform division - we have to implement it! Well - let's not talk about that.
object B{
val(l,o)=('1',"0")
type S=String
def n(v:S,c:S)=o*(c.size-v.size)+v
def g(n:S,m:S)=((n zip m)find(a=>a._1!=a._2)).getOrElse((l,'0'))._1==l
def a(x:S,y:S)=(((x zip y):\o)((n,m)=>{val s=Seq(m(0),n._1,n._2).filter(_==l).size
Seq("00","01","10","11")(s)}+m.tail))
def P(x:S,y:S)=t(a(n(x,y),n(y,x)))
def m(a:S,b:S)=(o/:a.zipWithIndex.filter(_._1==l).map(x=>b+o*(a.size-x._2-1)))(P)
def x(x:S,y:S)=t(s(x,y))
def s(x:S,y:S)=((x zip y):\o)((n,m)=>{val s=Seq(if(n._1==l)'0'else l,m(0),n._2).filter(_==l).size
Seq("01","00","11","10")(s)}+m.tail)
def M(a:S,b:S)=if(b==o)a else t(x(n(a,b),n(b,a)))
def d(n:S,m:S):S=if(g(n,m))P(D(M(n,m),m),"1")else o
def D(a:S,b:S)=t(d(n(a,b),n(b,a)))
def t(s:S)={val r=(s.substring(s.size-math.min(s.size,32))).replaceAll("^0*","")
if(r=="")o else r}
}

As usual, I have a less golfed version too, to explain 1 or 2 points (and this thread has much space left):
object BinArithmetic {
  def normalize (v: String, cmp: String) = "0" * (cmp.size - v.size) + v
  def ge(n:String, m:String)=((n zip m)find(a=>a._1!=a._2)).getOrElse(('1','0'))._1=='1'
  def greaterEqual (a:String, b:String): Boolean = ge (normalize (a, b), normalize (b, a))
  def i(s:String)=if(s=="0")"0"else trim32(j(s))
  def j(s:String):String=if(s.size==0)""else{if(s(0)=='1')'0'else'1'}+j(s.tail)
  def add (x:String, y: String): String =
   (((x zip y) :\ "0")((b, a) => {
       List (a(0), b._1, b._2).filter (_ == '1').size match {
        case 0 => "00"
        case 1 => "01"
        case 2 => "10"
        case 3 => "11"
        }
    }+a.tail))
  def plus (a:String, b:String): String = {
    trim32 (add (normalize (a, b), normalize (b, a)))
  }
  def mul (a:String, b: String): String =("0" /: a.zipWithIndex.filter (_._1 == '1').map (x=> b+ "0" * (a.size - x._2 - 1)))(plus)
  def sub(x:String, y: String): String = trim32(s(x,y))
  def s(x:String, y: String): String =
   ((x zip y) :\ "0")((b, ü) => {
       List (if(b._1=='1')'0' else '1', ü(0), b._2).filter (_ == '1').size match {
        case 0 => "01"
        case 1 => "00"
        case 2 => "11"
        case 3 => "10"
        }
    }+ü.tail)
  def minus (a:String, b:String): String = if (b=="0") a else {
    trim32 (sub (normalize (a, b), normalize (b, a)))
  }
  def d(n:String,m:String):String=if(ge(n,m))plus(div(minus(n,m),m),"1")else "0"
  def div (a:String, b:String): String = {
    trim32 (d (normalize (a, b), normalize (b, a)))
  }
  def trim32 (s: String): String = {
    val res = (s.substring (s.length - math.min (s.length, 32))).replaceAll ("^0*", "")
    if (res == "") "0" else res
  }
}

Half way through golfing and obfuscating the code I changed the methods add and s(ub) a bit. Later I recognized that I didn't used the methods i(nv) and j which handled inversing numbers - my research showed that you can inverse a number as binary string, you can add "1" and so sub (a, b) should theoretically be the same as add (add (a, inv(b)), "1") but in practice, it isn't. :)
There are 4 sorts of Methods:

preparation (normalize (a,b)) for example, which takes tow numbers, and makes them equal long
core calculation methods (add, sub, mul, div)
wrapping methods, which usually take (a,b) and normalize the call to the calculation methods with similar names (plus, minus)
finishing methods, which post process the result (trim32)

The root is the add method.
def a(x:S, y: S) = (((x zip y) :\ "0")((n, m) => {
  val s=List (m(0), n._1, n._2).filter (_ == '1').size
  List ("00", "01", "10", "11") (s)
  }+m.tail))

:\ is the right-fold operator. x zip y produces the list of pairs (10), (01), (11) from "101", "011", combines it with the overrun of the last operation, starting with no such overrun 0, counts the 1s in the result and produces a micro String like "10" from it. The 0 gets the growing part of the output, while 1 is the new overrun. You learned that at elementary school, didn't you? Now you remember!
The mul - method is interesting:
def mul (a:String, b: String): String =
  ("0" /: a.zipWithIndex.filter (_._1 == '1').map (x=> b+ "0" * (a.size - x._2 - 1)))(plus)

From mul ("1010", "0110"), it takes a and zips with index ("1010"->0123 => 10, 01, 12, 03) filters those which are 1 in a: (10, 12) takes the b and adds (a.size=4 - (x._2=[0,2]) - 1) times a literal "0". 4-0-1 = 3, 4-2-1=1 => "0110"+"000", "0110"+"0". The result is put into the already defined plus operation, which is a normalized add.
div is just subtraction combined with addition:
def d (n:String, m:String):String=
  if (greaterEqual (n,m)) plus (div (minus (n, m), m),"1") else "0"

if (n > m) then n/m = (n-m)/m + 1 else 0
if (8 > 3)      8/3 = (8-3)/3 + 1
if (5 > 3)      8/3 = (5-3)/3 + 1 + 1
since ! (2 > 3) 8/3 =       0 + 1 + 1

Sub is just similar implemented like add. Thanks to cyclic nature of ints, it doesn't really matter if the result is positive or negative.
Maybe I try the 2s-complement part later again.
Invocation
val ba = B
ba.plus  (  "01010",   "10101") // 11111
res412: String = 11111
ba.minus (  "11110",   "01010") // 10100
res413: String = 10100
ba.mul   (   "0010",    "1000") // 10000
res414: String = 10000
ba.div   ("1011010", "0010001") // 101
res415: String = 101

Smalltalk Squeak 4.x flavour, 570 bytes
First Try: define an operator in Object to evaluate any Object:
`x^self cull:x

We refine the eval message in Character to get the value:
`x^value

Then define bit ops with binary messages in Character:
&x^self class value:(x`1bitAnd:value)

|x^self class value:(x`1bitOr:value)

/x^self class value:((x`1bitXor:value)bitXor:$0`1)

/ is xor operator, because it looks like the truth table
01
10

Then add two more messages in Character for repeating in a String and concatanating
*n^String new:n withAll:self

,s^(String with:self),s

Or my favourite hack to gain 2 chars:
,s^'',(self`1+#[0]),s

Now create a new notation for accessing Array elements because (x at:i) costs two much. The operator @ could be used for at: and <@ would then means that it starts from the right (0-based) because our bit-Strings are big-endian.
That would be
Object subclass:#At instanceVariableNames:'a i'classVariableNames:''poolDictionaries:''category:''

In At, we would define two methods for initializing and accessing:
a:b i:j a:=b.i:=j

`x^(a atWrap:0-i)`x

Since this costs to much, we will replace this nice thing by using Association. So we define the accessor message in String (or in SequenceableCollection)
<@i^self->i

And just define ` to retrieve the At value in Association:
`x^(key atWrap:0-value)`x

Now we are ready to implement the operations in String first, strip the $0 left:
\~c |x|(x:=self)size>1or:[^x].c=(x at:1)or:[^x].^x allButFirst\~c

Then the awfull bit sum +| (just a naive xor with carry)
+|y|x z c m n|(m:=(x:=self)size)<=(n:=y size)or:[^y+|x].c:=$0.z:=''.0to:m-1do:[:i|z:=c/(x<@i)/(y<@i),z.c:=c|(y<@i)&(x<@i)|(c&(y<@i))].m to:n-1do:[:i|z:=c/(y<@i),z.c:=c&(y<@i)].c=$0or:[^c,z].^z

Then the bit multiply *| :
*|y|x z|x:=self.z:='0'.0to:y size-1do:[:i|$0/(y<@i)=$0or:[z:=z+|x].x:=x,$0].^z

Then the bit subtraction -| is using two complement. Result is truncated to receiver length, so it must not be negative:
-|y|n x|n:=(x:=self\~$0)size.^(x+|'1'+|($1*n,(y collect:[:c|c/$1])))last:n

Then a test <| for bit less than:
<|y|m n|m:=self size.n:=y size.^m<n or:[m=n and:[self<y]]

Then the bit division /| (by subtraction) - this will also raise a zero divide exception when appropriate:
/|z| x y q t n|y:=z\~$0.x:=self\~$0.y='0'and:[1/0].n:=0max:x size-y size.q:=''.[n>=0]whileTrue:[t:=y,($0*n).n:=n-1.q:=q,(x<|t ifTrue:[$0]ifFalse:[x:=x-|t\~$0.$1])].^q

And finally the operation encoding - we reuse <@ to access right to left 0-based:
y:y o:o|x|x:=self.^({[x/|y].[x*|y].[x-|y].[x+|y]}<@o)`1\~$0

The small test suite:
self assert: ('01010' y:'10101' o:0) = '11111'.
self assert:('11110' y:'01010' o:1) = '10100'.
self assert:('0010' y:'1000' o:2) = '10000'.
self assert:('1011010' y:'0010001' o:3) = '101'.

The longer test suite:
| n |
n := 100.
0 to: n do: [:i|0 to:n do:[:j |
    self assert:  (i printStringBase:2)+|(j printStringBase:2)\~$0=(i+j printStringBase:2)]].
0 to: n do: [:i|0 to:n do:[:j |
    self assert:  (i printStringBase:2)*|(j printStringBase:2)\~$0=(i*j printStringBase:2)]].
0 to: n do: [:i|0 to:i do:[:j |
    self assert:  (i printStringBase:2)-|(j printStringBase:2)\~$0=(i-j printStringBase:2)]].
0 to: n do: [:i|1 to:n do:[:j |
    self assert:  (i printStringBase:2)/|(j printStringBase:2)\~$0=(i//j printStringBase:2)]].

And the score is given by:
{Object>>#`. SequenceableCollection>>#<@. Association>>#`}
    , ({#`. #*. #&. #|. #/. #,} collect:[:selector | Character>>selector])
    , ({#\~. #+|. #-|. #*|. #/|. #<|. #y:o:} collect:[:selector | String>>selector])
    detectSum: [:method | method getSource size].

Which is 921 chars...

We can do much better if we use Boolean instead of Integer. They can be easily transformed in character:
Implement in True:
c^$1

And in False:
c^$0

Now transform a binary Character in Boolean, implement in Character:
b^self=$1

Now logical operations are expressed much simply in Character:
&x^(x b&self b)c

|x^(x b|self b)c

/x^(x b xor:self b)c

Plus the two operations to repeat and concatenate:
*n^String new:n withAll:self

,s^self*1,s

Now, the message size is long, let's create a shorter binary message in String:
\n^self size-n

We shorten the message for stripping leading chars in String:
~c|x|(x:=self)\1<1or:[c~=(x at:1)or:[^(x last:x\1)~c]]

Now we'd better implement binary >= rather than < for division, let's call it >~ in String:
>~y^self\0>(y\0)or:[self\0=(y\0)and:[self>=y]]

Now back to the operations, we will call them + - * / even if we have to override existing methods in String (they are presumably not used):
y:y o:o|x|x:=self.^({[x/y].[x*y].[x-y].[x+y]}<@o)value~$0

+y|x z c m n|(m:=(x:=self)\1)<=(n:=y\1)or:[^y+x].c:=$0.z:=''.0to:m do:[:i|z:=c/(x<@i)/(y<@i),z.c:=c|(y<@i)&(x<@i)|(c&(y<@i))].m+1to:n do:[:i|z:=c/(y<@i),z.c:=c&(y<@i)].c=$0or:[^c,z].^z

-y|n x|n:=(x:=self~$0)\0.^(x+'1'+($1*n,(y collect:[:c|c/$1])))last:n

*y|z|z:='0'.0to:y\1do:[:i|(y<@i)b and:[z:=self,($0*i)+z]].^z

/z| x y q t|y:=z~$0.x:=self~$0.y='0'and:[1/0].q:=''.(0max:x\0-(y\0))to:0by:-1do:[:n|t:=y,($0*n).q:=q,(x>~t and:[x:=x-t~$0.$1b])c].^q

The score is now
methods := {SequenceableCollection>>#<@. True>>#c. False>>#c}
    , ({#b. #*. #&. #|. #/. #,} collect:[:selector | Character>>selector])
    , ({#\. #~. #+. #-. #*. #/. #>~. #y:o:} collect:[:selector | String>>selector]).
methods detectSum: [:method | method getSource size].

That is 742 chars
Another snippet to browse our code alltogether:
methods do: [:e | e methodClass organization classify: e selector under: '*CodeGolfBinaryArithmetic'].
SystemNavigation default
    browseMessageList:
        (methods collect: [:e | MethodReference class: e methodClass selector: e selector])
    name: 'CodeGolfBinaryArithmetic'

We can further reduce the division to repeated subtraction (slower):
/z|x y|y:=z~$0.x:=self~$0.y='0'and:[1/0].x>~y or:[^'0'].^x-y/y+'1'

We can also omit 1/0 for ZeroDivide exception, anyway the result will be infinite on a computer with infinite memory after an infinite time:
/z|x y|y:=z~$0.x:=self~$0.x>~y or:[^'0'].^x-y/y+'1'

We can also reduce addition to a recursive form:
+y|x|(x:=self)\0>0or:[^y].y\0>0or:[^x].^x<@0&(y<@0)*1+(x first:x\1)+(y first:y\1),(x<@0/(y<@0))

And we now are at 570 chars... Not bad for Smalltalk.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Generating Binary shapes
How could we generate shapes or images using binary?
I got to messing around trying to create something that looked matrix like and got to thinking, wouldn't a great CodeGolf be to see who can make the best shortest code to generate a binary image?
Please advise me of any rules I should add.
Rules:

Create a binary image art of a Meme using 40 chars wide by 20 chars tall.
Shortest code out of top 3 voted images wins.

Example Output:
00000000000000000000000000000000000000000
00000000000000000000000000000000000000000
00000000000000000000000000000000000000000
00000000000000000000000000000000000000000
00000000000000000000000000000000000000000
00000000000000000000000000000000000000000
00000000000000000000000000000000000000000
00000000000000000000000000000000000000000
00000000001111000000000000011110000000000
00000000111111110000000001111111100000000
00000011110000111100001111000001111000000
00000011110000111100001111000001111000000
00000011110000111100001111000001111000000
00000011110000001111111100000001111000000
00000011110000000011110000000001111000000
00000011110000000000000000000001111000000
00000011110000000000000000000001111000000
00001111000000000000000000000000011110000
00111100000000000000000000000000000111100
11110000000000000000000000000000000001111

Any specifics? Otherwise, I could post an answer like '\n'.join(['0'*20]*40]) in Python and be done.

As per the FAQ, a challenge should have an objective winning criterion. "Most upvotes" isn't really on the right side of the line, in the sense that when you're writing the program you can't measure it. However, I can't see an easy fix short of specifying an image and turning this into another [:kolmogorov-complexity] question.

@PeterTaylor I made the image more specific, shortest code with most upvoted image that matches a meme wins. If you think it should be even more specific than that I'm willing to take suggestions.

What is a meme?

@agent-j knowyourmeme.com etc

YO DAWG, I HERD YOU LIKE ... (Python - 151)
a,b,c,d,e=9663681096,78383190025,559419527177,9663713289,628289966664
print'%040o\n'*20%tuple(map(lambda x:(x|x<<48|x<<96)>>21,[0,a,b,c]+[d]*5+[e])*2)

Output:
0000000000000000000000000000000000000000
0001100000111100000110000011110000011000
0011100001100110001110000110011000111000
0101100001100110010110000110011001011000
0001100001100110000110000110011000011000
0001100001100110000110000110011000011000
0001100001100110000110000110011000011000
0001100001100110000110000110011000011000
0001100001100110000110000110011000011000
0111111000111100011111100011110001111110
0000000000000000000000000000000000000000
0001100000111100000110000011110000011000
0011100001100110001110000110011000111000
0101100001100110010110000110011001011000
0001100001100110000110000110011000011000
0001100001100110000110000110011000011000
0001100001100110000110000110011000011000
0001100001100110000110000110011000011000
0001100001100110000110000110011000011000
0111111000111100011111100011110001111110

QBASIC - 1157 Characters
Ok, this one isn't that short, but definitely qualifies for the meme factor.
CLS
l$="1"
FOR i=1 TO 20
s$=""
FOR j=1 TO 40
s$=s$+"0"
NEXT
?s$
NEXT
A=20
C=16
D=12
E=27
FOR i=2 TO 6
        b=ABS(4-i)
        LOCATE i,8-i:?1$
        LOCATE i,4+i:?1$
        LOCATE 4,b+5:?1$
        LOCATE i,22:?1$
        LOCATE i,13:?1$
        LOCATE 6,11+i:?1$
        LOCATE 6,A+i:?1$
        LOCATE 10-b,3+i:?1$
        LOCATE D-b,7:?1$
        LOCATE 6+i,13:?1$
        LOCATE 8,11+i:?1$
        LOCATE 6+i,17:?1$
        LOCATE D,11+i:?1$
        LOCATE 6+i,22:?1$
        LOCATE 6+i,26:?1$
        LOCATE D,A+i:?1$
        LOCATE 6+i,29:?1$
        LOCATE 8,E+i:?1$
        LOCATE 10,E+i:?1$
        LOCATE 9,34:?1$
        LOCATE 6+i,E+i:?1$
        LOCATE D+i,5:?1$
        LOCATE 14,b+6:?1$
        LOCATE C,b+6:?1$
        LOCATE 18,b+6:?1$
        LOCATE 15+b,9:?1$
        LOCATE D+i,17-i:?1$
        LOCATE D+i,13+i:?1$
        LOCATE C,b+14:?1$
        LOCATE 14,A+i:?1$
        LOCATE C,A+i:?1$
        LOCATE 18,A+i:?1$
        LOCATE C-b,22:?1$
        LOCATE C+b,26:?1$
        LOCATE 14,E+i:?1$
        LOCATE C,30+b:?1$
        LOCATE 18,E+i:?1$
        LOCATE D+i,29:?1$
NEXT

Here's a screen shot for the odd person who doesn't have QBasic installed.

New*** Can't Triforce (Perl, 85 chars)
map{$j=$_<10;$_=sprintf"%010d",1x($_%10+1);s/1(.*)/$&$1$`0/;say$_.($j?0 x20:$_)}0..19

output:
0000000001000000000000000000000000000000
0000000011100000000000000000000000000000
0000000111110000000000000000000000000000
0000001111111000000000000000000000000000
0000011111111100000000000000000000000000
0000111111111110000000000000000000000000
0001111111111111000000000000000000000000
0011111111111111100000000000000000000000
0111111111111111110000000000000000000000
1111111111111111111000000000000000000000
0000000001000000000000000000010000000000
0000000011100000000000000000111000000000
0000000111110000000000000001111100000000
0000001111111000000000000011111110000000
0000011111111100000000000111111111000000
0000111111111110000000001111111111100000
0001111111111111000000011111111111110000
0011111111111111100000111111111111111000
0111111111111111110001111111111111111100
1111111111111111111011111111111111111110

The Weight Lifter or The Keyboard Player or ... (188 characters)
Not really too sure if this fits the meme requirement, but it is not too long I hope...
from math import*;r=range;q=r(20)
s=[["1"for x in q*2]for x in q];s[14][2:38]=["0"]*36
for j in r(18,21):
 for i in q:v=int(j+7*sin(i/7.0*pi));s[i][v]=s[i][40-v]="0"
for l in s:print''.join(l)

Output:

The Mandelbrot set written in 194 characters of coffeescript on node.js:

m=(x,y)->
 a=x
 b=y
 z=0
 for i in [0..9]
  return 0 if z > 4
  l=y*y
  z=x*x+l
  y=2*x*y+b
  x=x*x-l+a
 1
console.log (m x,y for x in [-1.5..0.5] by 2/39).join '' for y in [-1.3..1.3] by 2.6/19

I could make no sense out of that knowyourmeme site. So here's a riff on your first reference: something matrix like.
Postscript (287) (310)
Edit: Better output (more 'ones', less apparent waves).
Run with gs -dNODISPLAY -q -- matrix.ps 60. Replace 60 with the number of columns to generate.
%!
<<
0{(1)print}
1{(0)print}
10{()=}
/#{load exec}
/rho ARGUMENTS 0 get cvi
/enn 0
/set{[rho{rand rand 30 mod 2 idiv 3 mul neg bitshift}repeat]}
/lin{[exch{dup 2 idiv exch 2 mod #}forall]10 #}
/zer{/enn enn 1 add def enn 6 mod 0 eq{dup 0 exch{add}forall rho 1.1 exp lt{pop set}if}if}
>>begin
set{lin zer}loop

It generates infinite output like this, mostly ones with vertical zero "signals":
011001110110110001100101111110011111001101101111110111011101
010011111101100011110110110111010101001101111111111110011101
111111110111110001111100010110110011011101111111110110011101
110110111111110011111011110110111110111111101111110111111101
010101111111110101101100011100100110001101101111111110011101
110101111111101101101010011110101111001101111111110111111111
011111111111101001100111011100000011111101101111110111011011
010111111111111101101100111110100001101111111111111110011101
010100111111101001111011011111011001111111111111111110111001
011111111111101011110100011101001101101111111111110110111111
111100111111111101111100011111110001101111101111111111011011
111100111111101011110001011101111101101111111111111111111101
111101111111111001111001011111010101111101101111111110111111
011110111111111001100101011111011101111111101111111111111101
011101111111111101110001111111011101111111111111111111011101
111101111111111111110111111111111111111111111111110110011111
011101111111101011100111011111110101111111101111111111111111
011100111111111101111011111111111111111101101111110111011101
011111111111101111110111111111010111111111111111111111111111
011100111111111011110101111111111101111111111111111111011111
011101111111111111110101111111110111111111111111111111011111
111111111111111101111111111111111111111111111111111111011111
111111111111101101111101111111111111111111111111111111011111
111111111111101111111111111111111111111111111111111111011111
111111111111101111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111011111
010011010111011111001101111111011001011011011011111010111111
110011011111001111001111011100111011111011110011111101100110
110101111111111011111011111000110101110011011010111111110110
010111111111001111111001111000110001111111011111111110101110
010001111111111111110001011100110001100011110111101010111101
011011111011001011111001011100111111110111110110111011100110
011001011111101111110111011100110111100111111110111111111100
011101111011101111110001111110111111111111110111111010111111
011101111011101011111101111110110011011111010111101110101111
111101111011111011110001011101110001111011011111111000111100
111101011111011111111011111110111001101111111111111101111111
111101111111001111111111111110110011000011111111111100100111
11010101111110^C
Command terminated

05AB1E, 354 bytes
•4¤Q}qV¸dí¼ÔÁpoEW"Eáãø>jÎ®\å¢»kq;Çl:&»"6*²h†z¬e™/[Î§Ä…èRÝ\iåÚˆ2-dŠX‹öäùœUqBÍ¸©Ùì)z«×íP÷»éuøêB9hŽÒ>·Ä.ãò‰Z‡*…4:W&.½ñÝm·›mìQ[Š,í5(/øé‡”¿ô¿®P4^eã$–…l÷¿6?z·RˆN¥eWIãÀ}áÎåÇ)PÍ2ž?cLnfýµ‚áIípÐ¿ÖÝYp~FüÇ@jÉZßÝÓóÜåÀÑ=EôÿwµŽk`"ÍÝ8*$ˆœ¢7œÄÕw(A®?®h:rGPO¯7¥‘Å)UôÛ€¦—“ÇÙ(áÖ©£ŠÂ”áÊ¡õZ‘]½Æ¬„Š½Mâ$¾)Yé:â#æ»«Z=hõ¹‚.ðË7_Î#@¹OH—?9PyÆIð¼S%³zëJïzGÍä\{g…Ë;nEwÀ@É³_ˆ92ŽÚ@C’•b81ô}»

Try it online!
111111111111111110001111111111111111100000000000111111111111100000001111111111111
111111111111111111001111111111111111110000000111111111111111100001111111111111111
111111111111111111101111111111111111111000011111111111111111100111111111111111111
111111110000011111111111111100000111111100111111111111111111101111111111111111111
001111110000011111110011111100000111111101111111000000011111111111110000000111111
001111110000011111110011111100000111111111111110000000000000111111100000000000000
001111111111111111100011111111111111111011111110000000000000111111100000000000000
001111111111111111000011111111111111110011111110000000000000111111100001111111111
001111111111111100000011111111111111000011111110000000000000111111100001111111111
001111110000000000000011111100000000000011111110000000000000111111100001111111111
001111110000000000000011111100000000000011111110000000000000111111100000000111111
001111110000000000000011111100000000000001111111000000011111111111110000000111111
111111111100000000001111111111000000000000111111111111111111101111111111111111111
111111111100000000001111111111000000000000011111111111111111100111111111111111111
111111111100000000001111111111000000000000000111111111111111100001111111111111111
111111111100000000001111111111000000000000000000111111111111100000001111110001111
000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000111111111111111000000000111111111111111111111100000000000000000
000000000000000011111111111111111100000000111111111111111111111100000000000000000
000000000000000111111111111111111100000000111111111111111111111100000000000000000
000000000000000111111100000111111100000000111111111111111111111100000000000000000
000000000000000111111100000000000000000000001111111000000011111100000000000000000
000000000000000111111100000000000000000000001111111000000000000000000000000000000
000000000000000011111111100000000000000000001111111111111111100000000000000000000
000000000000000001111111111111000000000000001111111111111111100000000000000000000
000000000000000000011111111111110000000000001111111111111111100000000000000000000
000000000000000000000011111111111000000000001111111111111111100000000000000000000
000000000000000000000000000111111100000000001111111000000000000000000000000000000
000000000000000000000000000111111100000000001111111000000011111100000000000000000
000000000000000111111100000111111100000000111111111111111111111100000000000000000
000000000000000111111111111111111101111110111111111111111111111101111110000000000
000000000000000111111111111111111001111110111111111111111111111101111110000000000
000000000000000011111111111111100001111110111111111111111111111101111110000000000


text:
Shortest code to dump a file into workable memory
This is a slightly different code golf from the usual problems.  I'm forced to work with Java at my workplace and I'm increasingly annoyed at what I must do to read a file into memory to a String so I can operate on it in a normal way.
The golf is this: What is the shortest possible function to dump a file into your language's smallest data structure of characters?
Java would be char[], C++ would be char*,  Haskell would be a [Char], etc.  I don't care about complete programs or main() functions, but you do have to open and close the file.

inb4 Unix's >

inb4 Unix's > ?

Why wouldn't be byte[] in java?

I guess it would, but I had string manipulation in my head when I wrote this. So just go with chars because that's what I'm really interested in.

You should specify that this is about text files and not any kind of data, since many high-level languages like Haskell or Java see chars as actual characters (or rather, Unicode codepoints) rather than bytes. Also, what do you mean by smallest structure? If you're talking about memory usage [Char] is definately not Haskell's smallest structure to store Strings.

Can't you just mmap the file?

Java would be char[], C++ would be char* this makes no sense at all - char in java is 16bit, char in C is 8bit. The easiest is just mmap in C.

My 125-byte Java answer is the shortest I know of in Java (version 7+) for a File -> String. Unless you are willing to use Apache Commons.

Java: new String(Files.readAllBytes(file)) if you want a nice short method... (I think this is 8 only, don't remember when Files was added)

C#
var a = System.IO.File.ReadAllText("filename.txt");

a is a string that will contain the contents of filename.txt

PHP
$a=file('foo.txt');

$a now contains an array of strings of the lines of foo.txt.
Similarly:
$a=file_get_contents('foo.txt');

$a now contains a single string of the contents of foo.txt.

implode('',file('foo.txt')) is a bit shorter than file_get_contents('foo.txt').  Even shorter still if you use the alias join instead of implode.

Python
a=open('filename.txt').read()

The garbage collector will close the file.

C (for unixoid systems)
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <fcntl.h>

/* inside a function */
struct stat fd_stat;
int fd;
void *buffer;

int fd = open("my.file",O_RDONLY);
if (fd<0) exit(EXIT_FAILURE);
fstat(fd,fd_stat);
buffer = mmap(NULL,fd_stat->st_size,PROT_READ,MAP_SHARED,fd,0);
if (buffer==NULL) exit(EXIT_FAILURE);

This ridiculously long piece of code creates a buffer buffer of length fd_stat->st_size that contains the file. You probably won't use C for code-golfing anyway..

Nothing wrong with using C for code-golfing in general. Maybe not with this particular problem, though.

Scala
In Scala, you can get a iterator easily:
scala> io.Source.fromFile("Cg6367.scala").getLines
res274: Iterator[String] = non-empty iterator

then you can iterate over a collection of lines with a for loop, or use one of the other 200 methods, usable on iterators, like map, forall, filter, first, head, last, drop, groupBy, sortBy, ... - you name it. Simply outputting the content would be:
val ls = io.Source.fromFile("Cg6367.scala").getLines
println (ls.mkString ("\n"))

+1. Use iter to get Iterator[Char]. so is io.Source.fromFile("Cg6367.scala")iter

@PrinceJohnWesley: More interesting: How to use it in concise way from Java. I tried, but implicits don't work on Java, so I have to pass an Encoding as second parameter to the ctor, then I can't call getLines/iter for some reason ('iter has private access), transforming with JavaConversions isn't trivial too - I fear the scala-java-conversion will be as much Code, as nesting the Buffers/Streams and new File calls in pure Java.

The workaround is to construct interface in Java that define all the types that will be passed between
Java and Scala. If we ignore the checked exception, java.nio.file.Files.readAllLines(new java.io.File(".").toPath(), java.nio.charset.Charset.defaultCharset()) is what i come up with in java 7.

J
a=.1!:1<'filename.txt'

a now contains a string representing the contents of filename.txt.

C, 135 chars
Though 40 of those 135 chars are just because there are some #includes that you just can't skip:
#include<sys/mman.h>
#include<sys/stat.h>

(Add fcntl.h and unistd.h for non-golfing completeness.) Then in the place where the file contents are desired, it's as simple as:
struct stat s;char*p;int f=open("filename.txt",0);fstat(f,&s);
p=mmap(0,s.st_size,1,2,f,0);close(f);

The file is closed and p contains a pointer to the file contents. (Don't forget to call munmap() when you're done.)

Actually, you shouldn't really need the includes. C code compiles just fine if the function you call is not prototyped.

Which is why I was able to omit fcntl.h and unistd.h. But you can't omit the definition of struct stat, thus sys/stat.h. You might think that you can omit sys/mman.h, but on my tests I was unable to avoid getting a segfault without it.

The problem is that there is some casting going on. If you manually cast the st_size and suffix the integer literals, it should work...

Yes, that's what I guessed too. But then I tested it and learned that I was wrong.

that is interesting... I have to investigate that.

C
There's already a C answer, but this one uses nothing more than the absolute basics. It's also rather odd, and doesn't handle errors, because if users are going to give bad inputs really they deserve to have the program crash on them.
#include <stdlib.h>
#include <stdio.h>

**b,**m;main(l){
  FILE*f=fopen("foo.txt","r");
  for(m=b=malloc(64);~(l=fgetc(f));){
    *b++=&l;
    b=malloc(64);
  }
  return fclose(f);
}

Dumps the file into a linked list of chars, which if it's good enough for Haskell, it's good enough for C. Assumes a pointer is 32 bits and EOF is -1.
Clearly a linked list of ints is the most

Ruby

a=File.open('foo.txt', 'r') { |f| f.read }
a=IO.read('foo.txt')

Clojure's slurp overload that doesn't take the encoding is deprecated (for good reason):
(slurp "a.txt")

Here's the way to specify the encoding
(slurp "a.txt" :encoding "UTF-8")

Groovy, 9 bytes, or 19
Closure expecting a File object:
{it.text}

Closure expecting a String filepath:
{new File(it).text}

F#
let a = System.IO.File.ReadAllText("filename.txt")

a is a System.String that will contain the contents of filename.txt
.NET family <3

Java 7, 108 bytes (Method, Byte[])
public byte[] r(String p)throws Exception{return java.nio.file.Files.readAllBytes(new java.io.File(p).toPath());}

Java 7, 125 Bytes (Method, String)
public String r(String p)throws Exception{return new String(java.nio.file.Files.readAllBytes(new java.io.File(p).toPath()));}

Java, 193 bytes (Method, Lines)
Here's a java method that reads an entire file as a List of strings, one line means 1 string. Linebreaks are detected as defined here.
Boiler-plate:
public class A {
    public static void main(String[] args) throws Exception {
        List<String> lines = readLines(args[0]);
    }
}

Method:
import java.util.*;public List readLines(String path)throws Exception{List l=new ArrayList();Scanner s=new Scanner(new java.io.File(path));while(l.add(s.nextLine())&&s.hasNextLine());return l;}

Ungolfed:
public List readLines(String path)throws Exception{
    List l = new ArrayList();
    Scanner s = new Scanner(new java.io.File(path));
    while(l.add(s.nextLine())&&s.hasNextLine());
    return l;
}

Ungolfed (With Best-Practices):
public static List<String> readLines(String path) throws FileNotFoundException {
    List<String> l = new ArrayList<String>();
    Scanner s = new Scanner(new java.io.File(path));
    while(l.add(s.nextLine())&&s.hasNextLine());
    s.close();
    return l;
}

Swift
import Foundation

let contents = try! String(contentsOfFile: "filename.txt")

Perl 5, 26 bytes
sub{local(@ARGV,$/)=@_;<>}

Try it online!

C, 110 bytes without filename
Another C answer. This one is very inefficient, but at least it is short. First is the header:
#import<stdio.h>

And then the code (N is the filename):
char*r,c;FILE*F=fopen(N,"r");for(int i=r=0;~(c=fgetc(F));r[i-1]=c)r=realloc(r,++i);fclose(F);

Assumes EOF is -1. r will be a pointer to the result block. (If N is empty file, then it will be a null pointer)

q/kdb+, 9 bytes + filename
Solution:
a:read0`:filename.txt

a is now a list of lists; a list of chars for each line in filename.txt.
Explanation:
a:read0`:filename.txt / solution
       `:filename.txt / path to the file, in this case filename.txt
  read0               / read file as characters
a:                    / assign to variable a

Or we could drop to the k prompt we can do if we wanted to conserve some bytes:
\
  a:0:`:filename.txt

AutoHotkey
FileRead,a,foo.txt

a is a variable that now contains all the contents of the file foo.txt so long as that file is less than 1 GB. If file size or available memory is a problem, then you can loop through each line of a file instead using Loop,Read,foo.txt.
It has some options available such as limiting the read to the first n bytes or reading the file using a different file encoding so long as it's from a standard list.

Tcl
set t [read [open file.txt]]


text:
Generating combinations without recursion
Given a list of strings and a length, give all combinations of that list with the given length. The problem is: your code must not be recursive. Yes, it can be done. I have done it myself, when I had no clue what this "recursion" was.
Input: A list of strings of an undefined length, and an integer defining the length of the combination. The strings will be at least one character long, and will only contain letters or numbers. The way of input will be specified by you, the programmer.
Output: A list of possible combinations as strings, not necessarily distinct (although you can make it that way, if you like). You do not have to sort the list.
Test Cases:
As said before, the method of input will be specified by you.
[a,b] 3 -> Nothing
[1,0,0] 2 -> 10 10 00, or 00 10 if distinct.
[abc,bcd,cde] 2 -> abcbcd abccde bcdcde
If you even manage to do this, I will commend you. As always, shortest code wins. Good luck.

what does "without recursion" mean in this context? can you use a while loop? for loop? context would be helpful here...

If I look at your third test case, it seems that you care about the order. Is cdeabc a valid combination?

Yes it is. Why not?

@beary605 Because your test case says it is not.

Are we permitted to assume that none of the input strings are empty or contain newlines?

Yep. Hehe, how would you input newlines?

@rhymingorange Ehehe, recursion is when you call a function in itself.

@beary605 I understand what recursion is. it's just that you can do the equivalent of recursion using a while loop with very little difficulty. Just trying to tease out the "spirit" of the problem.

@rhymingorange It depends on the recursive algorithm, but yeah, that's true.

To howards question: Shall we ignore the order of elements? So for example 3: abc-bcd = bcd-abc?

Yep, whatever goes. As long as you have them all in there.

Not all languages have to offer looping constructs other than explicit recursion.

GolfScript (44 42 32 chars)
n%){\,=}+[[]]@1/{`{1$+}+%}%;\,n*

This takes input on stdin as a list of newline-separated strings followed by a line containing the desired subset size. It assumes that none of the input strings is empty. It takes some inspiration from Howard's solution, and can be shortened by two chars if using his input format:
~{\,=}+[[]]@1/{`{1$+}+%}%;\,n*

Output is a newline separated list of concatenations.
E.g.
$ golfscript.rb subcombo.gs <<END
> a
> b
> c
> 2
> END
ab
ac
bc

Note: this uses a horribly inefficient algorithm. A much nicer implementation in terms of performance is (62 61 chars)
n%)~\:S;2\?({2S,?<}{:s.~)&.s+.s^@4*/|}/{:x;S{;x.2/:x;1&},}%n*

which uses Gosper's hack.

How do you even stumble across such obscure programming nuggets?

@Gareth, I was taught this one by Arthur Norman. It's part of a collection of interesting titbits called HAKMEM.

Answer to you! You are pretty much the only answerer, other than the other GolfScript, that didn't use a built-in combo generator.

GolfScript, 33 35 34 characters
~[[]]@{\{.[2$]+.,4$={puts}*}%\}%];

Assumes that the input is list of strings and number in GolfScript compatible format (on STDIN). Example:
> ["abc" "bcd" "cde"] 2
abcbcd
bcdcde
abccde

You can also test this version online.
Edit: The first version was broken.

puts? Seriously?

@PeterTaylor Maybe I don't understand you correctly, but why not? Btw I just noticed that we can save a char and get rid of the dot.

It's so long that I think its only purpose is debugging. You can save two more chars by ditching puts and just filtering the list to ones of the right length: ~[[]]@{\{.[2$]+}%\}%;{,1$=},\;n*

Mathematica, 21
""<>##&@@@Subsets@##&

Usage:
""<>##&@@@Subsets@##&[{"a", "b", "c", "d"}, {3}]

{"abc", "abd", "acd", "bcd"}

My goodness, that's really compact.

Mathematica, 34 30 24 characters
StringJoin@@@Subsets@@#&

where i is input consisting of a list of the strings and the length of combinations.
For example,
k = {{"abc", "bcd", "cde"},{2}};
StringJoin@@@Subsets@@#&[k]

(* out *)
{"abcbcd", "abccde", "bcdcde"}

Additional examples:
d = {"a", "b", "cd", "e", "fgh"}
m = {d, {2}}
n = {d, {3}}
p = {d, {4}}

StringJoin@@@Subsets@@#&[m]
StringJoin@@@Subsets@@#&[n]
StringJoin@@@Subsets@@#&[p]
(* out *)
{"ab", "acd", "ae", "afgh", "bcd", "be", "bfgh", "cde", "cdfgh", "efgh"}
{"abcd", "abe", "abfgh", "acde", "acdfgh", "aefgh", "bcde", "bcdfgh", "befgh", "cdefgh"}
{"abcde", "abcdfgh", "abefgh", "acdefgh", "bcdefgh"}

Ha! Mma beating golfscript and J ... :D

J, 50 48 46 44 43 41 35 characters
;"1(>@{:{."1(i.@!@#A.])@}:)".1!:1[1

Takes input from the keyboard. I've changed the input format from previous answers. Strings should come first, single-quoted, and separated by semi-colons, followed by the integer.
   ;"1(>@{:{."1(i.@!@#A.])@}:)".1!:1[1
'hello';'mr';'wibble';2
hellomr
hellowibble
mrhello
mrwibble
wibblehello
wibblemr

Entering a number larger than the largest possible combination just gives the largest possible combination:
   ;"1(>@{:{."1(i.@!@#A.])@}:)".1!:1[1
hello mr wibble 8
hellomrwibble
hellowibblemr
mrhellowibble
mrwibblehello
wibblehellomr
wibblemrhello

Scala 52
Not a challenge - know your API:
def c(l:Seq[_],n:Int)=l combinations n mkString "\n"

invocation sample:
scala> c(Seq("foo", "bar", "foobar"), 2)
res199: String =
List(foo, bar)
List(foo, foobar)
List(bar, foobar)

Now beary605 observes that he didn't thought about library methods combinations, so I come up with this one, which doesn't use  combinations, but maybe he now will come up with a permutation prohibition.
Scala 63 (without literal combinations method):
def c(l:Seq[_],n:Int)=l.permutations.map(_.take(2).toSet).toSet

Hehe, I should have added "no using built-in combo functions", but oh well.

@beary605: Posted an alternative solution. Now you prohibit permutation, :) then map, then println?

Hahaha. Very clever. ;)

Java, 208 characters
No imports, two method calls,
so it should be pretty guaranteed that there are no implisit recursive calls neither.
class S{public static void main(String[]a){int n=a.length-1,k=Integer.parseInt(a[0]),i=0,j;while(++i<1<<n)if(Integer.bitCount(i)==k){String s="";for(j=0;j<n;)if((i&1<<j++)!=0)s+=a[j];System.out.println(s);}}}

Slightly more readable:
class S{
    public static void main(String[]a){
        int n=a.length-1,k=Integer.parseInt(a[0]),i=0,j;
        while(++i<1<<n)
            if(Integer.bitCount(i)==k){
                String s="";
                for(j=0;j<n;)
                    if((i&1<<j++)!=0)
                        s+=a[j];
                System.out.println(s);
            }
    }
}

Takes input from command line arguments. First arg is the length and the rest is the strings. Outputs each combination on a separate line:
$ java S 3 A B C D
ABC
ABD
ACD
BCD


text:
All non-empty finite sets of positive integers
The challenge is to create an iterator(/generator) which iterates (in any order so as to reach all of them... ie no set should occur at infinity) over all possible non-empty finite sets(/tuples/lists) of positive integers (hence demonstrating their countability).
Since the problem of verifying the correctness of a solution is undecidable in some cases, an accompanying explanation of how your program works and what order the sets are returned in would be helpful
Each finite set should occur exactly once.  So if left running long enough, the iterator should eventually hit each of {1}, {3,5}, {17,29,306} etc. exactly once

I realize now that simply counting upwards from 1 and listing the set bits in each number gives exactly this.  I had an altogether more complex and pointless solution in mind.  Perhaps I should post another problem for all non-empty finite "lists" of positive integers (ie ordered and with repeats) or perhaps sets with multiplicities (unordered, but with repeats)

Problem fixed with extra credit;  For lists, you can simply add a 0 onto all the sets in the original problem and then take the differences between successive terms.
For multiplicities, just filter the lists for ones which are non-descending

Please do not change the challange after it was posted. Instead you should post it here and discuss it before it becomes an open puzzle.

Thank you.  If you don't mind, I will delete this question, post it there and get help with it and then repost it when I'm ready.

I'd leave it as it is. It is a valid challenge and maybe others are already working on a solution. You may of course create a new question with different scope and then discuss it in sandbox.

But I'll get rid of the extra credit line and make it part of the new question?

GolfScript, 21 characters
;]]0{)\{.2$+.p}%\1}do

A GolfScript version which prints all generated sets. It basically does the same as my Python version although not by recursion but instead collecting all possible sets in an array.
;        // clear the stack
]]       // put [[]] on the stack - the array of generated sets
            (initially an array with only the empty set)
0        // counter starts with zero
{        // start of infinite loop
  )      // increase counter
  \{     // map for each item of the array
    .    // duplicate item (i.e. this is a set)
    2$+  // append counter
    .p   // print the newly generated set
  }%\    // end of map => now the array contains all sets with max. up to counter
1} do    // end of infinite loop

Sorry I keep changing the rules on you.  I'm experimenting with how to make the problem more interesting.  Good solution though.

Why mess with iterators and suchlike if we can just return an infinite (lazy) list?
Haskell, 40
s(α:η)=[α]:(s η>>=(\κ->[κ,α:κ]))
c=s[1..]

Works thusly:
s(α:η)                    --the nonempty subsets of the list beginning with α, followed by η
   =[α]                   --  are: the singleton set [α]
      :(s η               --       and all nonempty subsets of η,
          >>=(\κ->[ κ     --         once on their own
                  , α:κ ] --         and once with α prepended to each of them.
                         ))
c=s[1..]       --c is the list of all nonempty subsets of the naturals.

Demonstration:
Prelude> take 16 c
[[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4],[5]]

Python
Note: I wrote this version before the challenge became code-golf. I'll leave it here until I have a new one.
def allsets():

  def setswithmax(n):
    yield [n]

    for m in range(1,n):
      for s in setswithmax(m):
        yield s+[n]

  n = 1
  while n:
    for s in setswithmax(n):
      yield s
    n = n+1

It enumerates the sets with increasing maximum element, i.e. first of all it will generate all sets where max element is 1, then 2, ...
It does so by calling the generator setswithmax for increasing argument, which recursively builds these sets, i.e. a set with maximum n is obtained by iterating all sets with arbitrary max <n and then appending n to these sets.
You can see it in action on ideone.

Scala 265:
object C extends Iterator[Set[Int]]{
var c=1
var M=1
var s=(1 to M)
var i:Iterator[Seq[Int]]=_
def n{i=s.combinations(c)}
def hasNext=true
n
def next:Set[Int]={
if(!i.hasNext)
if(c<M){
c+=1
n}else{c=1
M+=1
s=(1 to M)
n}
val r=i.next
if(r.max<M)next else r.toSet
}
}

Iterator is a well defined type in Scala, which means you have to declare what it returns (Set[Int]) in our case) and implement a method next and hasNext. For infinite Sets, hasNext trivially just returns true.
Here is code for testing:
object Cg6394IteratorTest extends App {
  val ci = C
  println (ci.take (1000).mkString ("\n"))
}

output:
Set(1)
Set(2)
Set(1, 2)
Set(3)
Set(1, 3)
Set(2, 3)
Set(1, 2, 3)
Set(4)
Set(1, 4)
Set(2, 4)
Set(3, 4)
Set(1, 2, 4)
Set(1, 3, 4)
Set(2, 3, 4)
Set(1, 2, 3, 4)

ungolfed:
object Cg6394Iterator extends Iterator [Set[Int]] {

  var curLength = 1
  var MAX = 1
  var source = (1 to MAX)
  var iter: Iterator [Seq[Int]] = _

  def init { iter = source.combinations (curLength)}
  def hasNext: Boolean = true

  init

  def next : Set[Int] = {
    if (! iter.hasNext)
      if (curLength < MAX) {
        curLength += 1
        init
       } else {
         curLength = 1
         MAX = MAX + 1
         source = (1 to MAX)
         init
       }
     val coll = iter.next ()
     if (coll.max < MAX) next else coll.toSet
  }
}

Perhaps I didn't clarify, when I said integers I wasn't talking about the type "int", I was talking about actual mathematical integers (the kind that can grow infinitely large).  If your program uses MAX as you did, then you missed the point of the problem

@dspyz: I missed that point initially, but luckily, my first solution could easily be widened to work for Sets of random size.

Python, 88
Simple implementation, like mentioned, counter and checking for bits in binary representation.
def P():
 i=1
 while 1:yield [n+1 for n,x in enumerate(bin(i)[2:][::-1])if x=='1'];i+=1

Stax, 7 bytes
âe¢-ï♂~

The link below adds a footer to output the generated sets
Run and debug online!
Explanation
Uses ASCII representation to explain:
zWiRSca-
z           Empty set
 W          Loop forever
  iR        Range [1..current loop index]
    S       Powerset (*)
     ca-    Remove the powerset of [1..(current loop index-1)] from (*)

The footer is mJ, which outputs every generated set on a line, with the element separated by spaces.