5
\$\begingroup\$

With a twist; your algorithm has to be less complex than O(X2) where X is the Nth prime. Your solution post should include the character count and the theoretical complexity in terms of X (or N, which ~= X/ln(X) and so will usually be more efficient)

Here's a hint solution in C# (O(Xln(sqrt(X))), 137 chars):

public List<int> P(int n){var r = new List<int>{2}; int i=3; while(r.Count<n) if(!r.TakeWhile(x=>x<Math.Sqrt(i)).Any(x=>i%x==0)) r.Add(i++); else i++; }

\$\endgroup\$
  • 2
    \$\begingroup\$ I fail to see how the sample is O(n*ln(sqrt(n))). O(n*sqrt(n)) maybe, but there's nothing hints to why it would have an ln in there. Please correct me if I'm wrong. \$\endgroup\$ – Mr. Llama Mar 8 '12 at 23:07
  • \$\begingroup\$ For each value tested, it's checked against all prime numbers less than the square root of the number. If you haven't found a prime factor by then you won't find one. There are on the order of ln(i) primes between 0 and any i. So, in finding prime X which is the Nth prime, you will have run checks equal to ln(sqrt(X)) against each number up to and including X. Or, simply, O(X*ln(sqrt(X))). \$\endgroup\$ – KeithS Mar 8 '12 at 23:41
  • \$\begingroup\$ By the way, O(ln(sqrt(x)) == O(ln(x)) \$\endgroup\$ – Keith Randall Mar 11 '12 at 4:48
  • \$\begingroup\$ @KeithS actully, π(i) ~ i/ln(i). So, sqrt(X)/ln(sqrt(X)) ~ sqrt(X)/ln(X) and overall complexity of producing N ~= X/ln(X) primes is O(X^1.5 / (ln(X))^2 ), not counting the testing of composites, most of which are multiples of 2 or 3, so will be weeded out with very few tests. \$\endgroup\$ – Will Ness Aug 8 '12 at 18:04
  • \$\begingroup\$ @KeithS or in terms of N: X ~= N*log(N), it is O(N^1.5/sqrt(ln(N))). Or in practical terms N^1.4 .. 1.45. So you might want to amend your spec to "below N^1.5" (or at least "below X^1.5") or all kinds of solutions will have to be admitted. \$\endgroup\$ – Will Ness Aug 9 '12 at 12:36
8
\$\begingroup\$

J, 4 characters

p:i.

Usage:

   p:i.10
2 3 5 7 11 13 17 19 23 29

The problem with using J here is that I don't really know how efficient it is. I'd assume that as a language specialising in "mathematical, statistical, and logical analysis of data", that the algorithm used to generate the primes is pretty good.

I did look at the C source for clues, but it turns out that the C source for J is almost as unreadable as J itself. :-)

(The file is called v2.c for anyone who wants to have a look)

\$\endgroup\$
  • 1
    \$\begingroup\$ Haha, that C code is crazy, looks like someone tried to codegolf it. \$\endgroup\$ – Scott Logan Mar 9 '12 at 17:54
  • \$\begingroup\$ My lord! The source looks as if it has been compiled already. \$\endgroup\$ – MrZander Mar 11 '12 at 21:01
  • \$\begingroup\$ You could do some timing, like I did, couldn't you? \$\endgroup\$ – user unknown Mar 15 '12 at 3:28
  • \$\begingroup\$ My goodness, is it how thinking in J affects one's coding style?:-) \$\endgroup\$ – defhlt Aug 10 '12 at 7:55
  • \$\begingroup\$ I mean the J source code... \$\endgroup\$ – defhlt Aug 10 '12 at 9:40
1
\$\begingroup\$

C, 98 characters

The good old sieve method.
We assume the first N primes are among the first N*24 integers. this works up to 2^32, because ln(2^32)<24. A general solution would need to estimate prime density, but since I use 32bit integers, I saw no need to generalize.
Complexity analysis (which I may do later) should use a formula instead of the constant 24.

i,j,m,*p;
f(n){
    p=calloc(m=n*24,4);
    for(i=2;n;i++)
        if(!p[i])for(n--,printf("%d\n",j=i);p[j+=i]=j<m;);
}
\$\endgroup\$
  • \$\begingroup\$ Nice work, very nice. Note: The expression p[j+=i]=j<m walks off the end of the array and corrupts memory. On my system, it corrupts printf and produces '\0' characters in the output (visible with | less or with | hexdump -C). To fix, instead say p[j]=j<m,j+=i, or maybe there is a way to write it with while(j<m)p[j]=1,j+=i; ? \$\endgroup\$ – Todd Lehman Jul 28 '14 at 4:19
  • \$\begingroup\$ @ToddLehman, you're right, I'm writing out of bounds. The easy fix is changing calloc's 2nd parameter to 8. I can't seem to do it, because of my employer's upload policy. \$\endgroup\$ – ugoren Jul 28 '14 at 12:17
1
\$\begingroup\$

Haskell, 47 46

Since the problem definition demands less than O(X^2) complexity, where X ~= N*log(N), the following solution is acceptable. Its theoretical complexity is below O(X^2), testing each number below X by all its preceding numbers until a divisor is found. For primes only, having ~ X/log(X) primes overall, the complexity is thus O(X^2/log(X)). Most of the composites are multiples of small primes so are only divided few times, so they don't count.

p n=take n[n|n<-[2..],all((>0).rem n)[2..n-1]]

Prelude> last $ p 500
3571    (1.60 secs)
Prelude> last $ p 700
5279    (3.31 secs)
Prelude> logBase (5279/3571) (3.31/1.60)  -- in X
1.8597116027280054
Prelude> logBase (7/5) (3.31/1.60)        -- in N
2.1604889825177507

Prelude> last $ p 900
6997    (5.69 secs)
Prelude> logBase (6997/5279) (5.69/3.31)
1.9228821930296973                        -- in X
Prelude> logBase (9/7) (5.69/3.31)
2.155714108637307                         -- in N

If the complexity constraint in the problem definition will be amended to below O(N^1.5) (as I believe it should) then this solution will not be acceptable. That is why I post it in addition to another Haskell solution which is indeed better than O(N^1.5).

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

scala 191

Not the shortest one...

object P extends App{
def c(M:Int)={
val p=(false::false::true::List.range(3,M+1).map(_%2!=0)).toArray
for(i<-List.range(3,M)
if(p(i))){
var j=2*i;
while(j<M){
if(p(j))p(j)=false
j+=i}
}
(1 to M).filter(x=>p(x))
}
println(c(args(0).toInt))
}

Just measuring the method c, like the others do.

But how to prove, that it fulfills the Big-O requierement?

Well, I feed it with numbers, each twice as big as the number before. If it was of O(x²) complexity, it should need about 4 times as long, shouldn't it?

So I just measure it:

for p in {10..22}
do
  /usr/bin/time scala P $((2**p))> /dev/null
  echo "N="$((2**p))
done 2>&1 | tee primes.log 

and then it's just a grep:

egrep -o "(^.*user|N=.*|#)" primes.log | tr "\n" "\t" | tr "#" "\n"
0.57user    N=1024  
0.54user    N=2048  
0.56user    N=4096  
0.59user    N=8192  
0.62user    N=16384 
0.66user    N=32768 
0.70user    N=65536 
0.77user    N=131072    
0.99user    N=262144    
1.48user    N=524288    
2.59user    N=1048576   
5.68user    N=2097152   
10.79user   N=4194304   

So in the beginning there is only a startup overhead of about .55s - later it is a linear growth. For N'=2*N, t(N') ≈ 2*t(N).

\$\endgroup\$
  • \$\begingroup\$ you can assume growth of the order n^a, and estimate a as log( t2/t1 ) / log( n2/n1 ). Optimal trial division should run at about ~ n^1.30 .. 1.45. Sieve of Eratosthenes can be n^1.0 .. 1.1. A priority-queue based s. of E. runs at about n^1.2 (it has an additional log factor compared with SoE). \$\endgroup\$ – Will Ness Aug 8 '12 at 18:35
0
\$\begingroup\$

Perl: 249 chars

The sieve certainly would have been shorter, but here is an implementation of the Miller-Rabin test:

sub p{
  $n=shift;
  $m=$n-1;
  return$n==2||$n==3if$n<=3or!($n&1);
  $s=unpack"%32b*",pack"L",($m&-$m)-1;
  for(1..5){
    next if($x=(int(rand($n-3))+2)**($n>>$s)%$n)==1||$x==$m;
    map{($x=$x**2%$n)==1&&last;$x==$m&&next}(1..$s-1);
  0}
1}
p($_)&&print"$_\n"for(1..$ARGV[0]);

Wikipedia says the runtime is O((log(X))^3)

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

Ruby (91)

Almost same as the example, so should have similar complexity. Unless I'm still missing something obvious (almost used select instead of take_while to save a few chars)

q=->n{k=[2];p=3;while k.size<n;k<<p if !k.take_while{|x|x*x<=p}.any?{|x|p%x<1};p+=2;end;k}

and with some whitespace:

q=->n{
  k=[2];
  p=3;
  while k.size<n;
    k<<p if !k.take_while{|x| x*x <= p }.any?{|x| p%x < 1};
    p+=2;
  end;
  k
}
\$\endgroup\$
-1
\$\begingroup\$

PYTHON

Just for fun:

import urllib2, collections
def primos(tamanho):
    f = urllib2.urlopen('http://primes.utm.edu/lists/small/10000.txt')
    for x in xrange(4): f.readline()
    for line in f:
        line = collections.deque(line.split())
        while line:
            if not tamanho:
                return
            tamanho -= 1
            yield line.popleft()


for primo in primos(9):
    print primo
\$\endgroup\$
  • \$\begingroup\$ Can you elaborate on the Big-O of your approach? \$\endgroup\$ – user unknown Mar 15 '12 at 3:28
-1
\$\begingroup\$

Ruby 37

require 'prime'
p Prime.take gets.to_i
\$\endgroup\$
  • \$\begingroup\$ Can you elaborate on the Big-O of your approach? \$\endgroup\$ – user unknown Mar 15 '12 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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