Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
4  
This is very similar to codegolf.stackexchange.com/questions/5977/… . –  Gareth Jun 10 '12 at 17:12
2  
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. –  Gareth Jun 10 '12 at 17:23
1  
@Optimus: You could do a md5sum of the primes file and print the handful of bytes, instead of uploading 8M. –  user unknown Jun 10 '12 at 17:36
1  
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. –  Howard Jun 10 '12 at 17:57
1  
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. –  ugoren Jun 11 '12 at 6:35

9 Answers 9

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.

share|improve this answer
    
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. –  Howard Jun 11 '12 at 5:13
    
Upper bound n? What's that? –  beary605 Jun 11 '12 at 5:35
    
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). –  ugoren Jun 11 '12 at 6:31
    
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 Jun 11 '12 at 6:39
    
@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)) –  Optimus Jun 11 '12 at 6:44

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.

share|improve this answer
    
•primes cannot be generated by an inbuilt functon or through a library –  beary605 Jun 11 '12 at 5:11
    
@walpen I'am sorry I modified the rules without notification, please make the changes as you see fit –  Optimus Jun 11 '12 at 8:21
    
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) –  Peter Taylor Jun 11 '12 at 11:50
    
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. –  walpen Jun 11 '12 at 20:01
    
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. –  Peter Taylor Jun 11 '12 at 22:11

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

share|improve this answer

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:
share|improve this answer
    
I've modified the problem statement a bit, its now find first 'n' primes, I am sorry for no notification –  Optimus Jun 11 '12 at 8:46
    
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. –  r.e.s. Jun 17 '12 at 18:54

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.

share|improve this answer
    
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) –  Optimus Jun 11 '12 at 8:44
    
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). –  Peter Taylor Jun 13 '12 at 6:44
    
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. –  user unknown Jun 13 '12 at 8:18

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
share|improve this answer

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.

share|improve this answer

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
share|improve this answer

(This is not an answer, but may offer empirical support for some of the answers, and is too long for a comment.)

Following a suggestion in the section "How Not to Abuse O-Notation" of this article, I looked at the actual running times T(n) of various programs to see their scaling behavior. For many programs, the ratio T(2n)/T(n) appears to show approximate convergence to 2^d (d being the "scaling exponent") within a quite feasible range of n values. Such a result is consistent with a complexity bound of form O(n^d f(n)), where f(n) may be any function whose scaling exponent is 0 (such as various logarithmic functions), among which this method does not distinguish.

Here are the results for five programs, the first three of which appear among the answers to the present question, the last two being from a question posted elsewhere. The approximation for d is D(n) = log_2( T(2n)/T(n) ).

(P1) Golfscript program by "Peter Taylor" (scaling exponent ≈ 2):

n/10^3  T(n)/sec    T(2n)/T(n)  D(n)
1           4.4     3.89        2.00
2          17.1     3.95        2.00
4          67.6     3.99        2.00
8         270.      4.00        2.00
16       1080.      

(P2) Python program by "beary605" (scaling exponent ≈ 1.5):

n/10^5  T(n)/sec    T(2n)/T(n)  D(n)
1        11.0       2.91        1.54
2        32.0       2.93        1.55
4        93.7       2.84        1.51
8       266.        

(P3) QBasic program by "Kibbee" (scaling exponent ≈ 1.5):

n/400  T(n)/sec     T(2n)/T(n)  D(n)
1        17.3       2.71        1.44
2        46.9       2.71        1.44
4       127.        2.92        1.55
8       371.        2.86        1.52
16     1060.        

(P4) Ruby program by "Howard" (scaling exponent ≈ 3):

n/400   T(n)/sec    T(2n)/T(n)  D(n)
1         0.265     7.89        2.98
2         2.09      8.05        3.01
4        16.9       8.11        3.02
8       137.        

(P5) C program by "breadbox" (Scaling exponent ≈ 1):

n/10^5  T(n)/sec    T(2n)/T(n)  D(n)
1        1.71       2.23        1.16
2        3.81       2.20        1.14
4        8.38       2.20        1.14
8       18.4        2.16        1.11
16      39.8        

What I'm really curious about is the degree to which the scaling exponent of a given program may be independent of its operating environment (OS, CPU, choice of compiler/interpreter, etc.), and to what degree it may be invariant under translations into other programming languages.

share|improve this answer
    
this is empirical order of growth: given n^a power rule, a is estimated as a = log( t2/t1 ) / log( n2/n1 ) == log_in_base_(n2/n1) (t2/t1). n*log(n) is usually ~ n^1.1: log_2 ( 200000*log(200000) / (100000*log(100000)) ) = 1.0843; n*log(n)*log(log n) ~ n^1.12 at 200k/100k; etc. –  Will Ness Aug 10 '12 at 16:41
    
I can tell you that, as the answer implies, my GolfScript solution's asymptotic performance depends on the version of Ruby used by the interpreter. –  Peter Taylor Aug 10 '12 at 18:07
    
@PeterTaylor btw this answer shows n^2 order of growth for your program; n*log(n) would produce n^2.1 . And even with 2.1, your score should be 45**2.1 = 2963, IMO. –  Will Ness Aug 10 '12 at 18:24
    
@PeterTaylor for instance, let g n = n*(log n)**2 * log(log n). This is much better than n^1.5. But, for 100 chars, g(100)=3239 while 100^1.5=1000. This is clearly wrong. But, logBase 2 (g 200000 / g 100000) = 1.2. So true score for g on 100 chars should be then 100**1.2 = 251. –  Will Ness Aug 10 '12 at 18:29
    
@PeterTaylor lastly, in such low ranges as for less than 1 mln primes, smaller than 16 million in value, I think we should count divisions just as O(1). –  Will Ness Aug 10 '12 at 18:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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