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.

Fastest code that print all prime numbers between two given numbers ?

Not necessary shortest.

Range may be any two numbers between 1 & 1000000000

Time limit: 6s

Source limit: 50000B

share|improve this question
    
fastest is not a easy to measure metric, also in what range should we consider this, up to 2^31 or arbitrarily large –  ratchet freak Jan 10 '12 at 19:04
    
possible duplicate of Sum of primes between given range –  mellamokb Jan 10 '12 at 20:08
    
I want the fastest one... –  Arya Jan 10 '12 at 20:16
1  
Since your winning criteria is fastest please remove the code-golf tag. What OS are you going to run the speed tests on? How much ram and what cpu? Are you able to accept any language when you run the tests or should we limit ourselves to certain ones? How will you generate the test cases? (I assume you will run multiple tests for multiple ranges, correct?) –  Steven Rumbalski Jan 10 '12 at 20:22
1  
@PaulR, the reason is easy to fathom: it's to stop someone hard-coding an array of all the primes and then using searches (binary chop with initial values determined using the known distribution of primes). –  Peter Taylor Jan 10 '12 at 21:56
show 4 more comments

8 Answers

J

n=.".1!:1]3
p:>:^:(_1 p:{.n)i.(_1 p:{:n)-(_1 p:{.n)

I was surprised how quickly this worked when I gave it 10 1000000000 as an input. I guess it's heavily optimized for this kind of thing.

share|improve this answer
    
how long did it took for your code? –  Ali.S Jan 11 '12 at 9:41
    
A few seconds. I don't have a J console installed on my work computer so I'll have to wait until later to give a more precise answer. –  Gareth Jan 11 '12 at 10:13
    
I think I'll need to learn J (no easy task!) just to blow my co-workers minds. –  Steven Rumbalski Jan 11 '12 at 16:09
    
@StevenRumbalski I'm only just learning myself - got fed up of losing at code golf with my Scala answers. :-) –  Gareth Jan 11 '12 at 16:21
    
@Gadjet About 10 seconds (measured unscientifically - "1 mississippi, 2 mississippi ..."). –  Gareth Jan 11 '12 at 19:51
show 1 more comment

C++

This code comes in at under 14 seconds worst-case (min=0, max=1e9, with disabling the printf. Add an extra 10 seconds for printf piped to /dev/null). I'm not sure 6 seconds is achievable (except maybe with multiple threads).

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define LOG_WORDBITS 6
#define WORDBITS 64
#define WORDMASK 63
typedef uint64_t word;

int main(int argc, char *argv[]) {
  int min = atoi(argv[1]);
  int max = atoi(argv[2]);
  if (min <= 2) { printf("2\n"); min = 3; }
  if (!(min & 1)) min++;
  if (!(max & 1)) max--;

  // bit i in word array is set iff 2*i+3 is composite                                                                                                                   

  int nbits = (max - 3) / 2 + 1;
  int words = (nbits + WORDBITS - 1) / WORDBITS;
  word *array = (word*)calloc(words, WORDBITS / 8);
  for (int i = 0; i < nbits; i++) {
    if (!((array[i >> LOG_WORDBITS] >> (i & WORDMASK)) & 1)) {
      int p = 2 * i + 3;
      if (p >= min) printf("%d\n", p);
      if (p < 32768 && p * p <= max) {
        if (p < 64) {
          // dense sieving                                                                                                                                               

          // precompute pattern                                                                                                                                          
          word *x = (word*)calloc(p, WORDBITS / 8);
          for (int j = 0; j < WORDBITS * p; j++) {
            if ((2*j+3)%p == 0) x[j >> LOG_WORDBITS] |= 1LL << (j & WORDMASK);
          }

          // apply pattern                                                                                                                                               
          int z = 0;
          for (int j = 0; j < words; j++) {
            array[j] |= x[z];
            z++;
            if (z == p) z = 0;
          }
          free(x);
        } else {
          // sparse sieving                                                                                                                                              
          for (int j = 2 * i * i + 6 * i + 3; j < nbits; j += 2 * i + 3) {
            array[j >> LOG_WORDBITS] |= 1LL << (j & WORDMASK);
          }
        }
      }
    }
  }
}
share|improve this answer
    
try optimizing your code using VC, gcc couldn't optimize my code, but using VC I achieved 6s without printing results. –  Ali.S Jan 13 '12 at 15:27
add comment

C

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char *argv[])
{
    int i,j;
    int from=atoi(argv[1]);
    int to=atoi(argv[2]);
    int *sieve=(int *)calloc(to+1,sizeof(int));
    for(i=2;i<=to;i++)
    {
        if(sieve[i]==0)
        {
            if(i>=from)
            {
                printf("%d ",i);
            }
            if(i*i<=to)
            {
                for(j=i;j<=to;j+=i)
                {
                    sieve[j]=1;
                }
            }
        }
    }
    printf("\n");
    free(sieve);
    return 0;
}

Uses the Sieve of Eratosthenes to generate the primes and outputs them as it's doing so. Will fare worse against cleverer algorithms when the start number is very large.

Edit: I should note that I came up with this answer before the 6 second time limit appeared. My program meets that limit for max numbers up to around 100000000 but goes into a period of deep contemplation when you try 1000000000. :-S

share|improve this answer
    
I think it needs more than 1 day to give results for numbers as big as stated! –  Ali.S Jan 10 '12 at 21:27
    
those conditions were added at "2012-01-10 20:26:25z" while you answered at "2012-01-10 20:33:47z", they were their while you posted your answer. but those are some impossible conditions, so don't worry about that! –  Ali.S Jan 10 '12 at 21:37
    
You really need 64 bit ints for this if you're going to support the required range of up to 10000000000 (1e10). –  Paul R Jan 10 '12 at 21:49
    
I think you also have some indexing problems - you need to correct for the from offset when accessing sieve[]. Also make sure that you're not attempting to access sieve[] outside its bounds. –  Paul R Jan 10 '12 at 21:53
    
@Gajet I read the question, then came up with an answer, then posted it, then saw that the question had changed. But I'm relatively happy with my answer and won't be attempting to make it faster - like you say, the new conditions are a bit stringent. :-) –  Gareth Jan 10 '12 at 21:54
show 5 more comments

tested my code on a windows machine powered by intel 720QM, I've only timed preprocessing, since writing (to console) it self takes large amount of time.

c++ : 110s 9-10s 6-7s & 611MB 61MB ram

    #include <stdio.h>
#include <time.h>
#include <math.h>
#include <memory.h>

#define isprime(X) ((X)&1?(!(bank[(X)>>6]&(1<<(((X)&63)>>1)))):(X)==2)
#define sqr(X) ((X)*(X))
#define maxpossible     (1000000000L)

unsigned int bank[maxpossible/64];

int main()
{
    int beg = time(0);
    unsigned long i,k,a,b;
    unsigned long d,x,maxpossible_2 = maxpossible>>1;
    unsigned long maxpossiblesqrt = sqrt((double)maxpossible)+1;
    memset(bank,0,sizeof(bank));
    bank[0] ^= 1; 
    for(i=0;i<maxpossiblesqrt/64;i++)
        for(k=0;k<32;k++)
            if(!(bank[i]&(1<<k)))
            {
                d = (((i<<5)|k)<<1)+1;
                for(x=sqr(d)>>1;x<maxpossible_2;x+=d)
                    bank[x>>5]|=(1<<(x&31));
            }
    printf("preprocessing needed %d seconds\n" ,time(0) - beg);
    printf("enter two positive number lower than %d\n" ,maxpossible ); 
    scanf("%d %d" ,&a ,&b);
    if (a<2)
        a=2;
    if (!(a&1))
        printf(a++==2?"2\n":"");
    int p=0;
    for(i=a;i<=b;i+=2)
    {
        if(isprime(i))
        {
            printf(" %d",i);
            p++;
            if(p==8)
            {
                printf(" \n");
                p=0;
            }
        }
    }
}

my code now compiles both in C++ and C (i've used c++ compiler myself), also fixed a small bug! some explaination:

to save if a number is prime or not you only need 1 bit, so you can easily reduce size of data needed to store if a number is prime by 8 if you use all 8 bits in each byte.

and besides the only even number which is prime is 2, so I can omit all the even numbers and only save if odd numbers are prime.

now how isprime works:

it first checks if a number is odd by computing ((X)&1), if a number is odd the result is 1 otherwise it's zero (note that odd numbers have 1 in their last bit).

  • in case of even number I can easily check if (X)==2 and it's the same as checking if an even number is prime

  • in case of odd number I have to look into my table, first I need to find out which cell contains data for (X), and then which bit is telling if my number is prime. as I explained each cell contains 8 bits so 8 numbers and even numbers are completely off my list. so (X)>>4 meaning (X) without it's 4 first bits generates cell number.
    then to find out bit location I use (1<<(((X)&14)>>1)) which means : only keep bit 2,3 and 4 of my number, shift right 1 place and put data in bits 1,2 and 3 respectively. so far (((X)&14)>>1) it generates bit number the next step is to create a mask that checks only for that specific bit (1<<(((X)&14)>>1)) it means shift a number with single first bit as true (((X)&14)>>1) places to left. in the end it's only checking if that specific mask applied to chosen data cell is true or false, which is done by only applying the mask by bitwise & operator (c++ itself checks if result is none-zero)

if you got how isprime works the rest is easy, it's using Sieve of Eratosthenes method to eliminate all none-prime numbers. the only thing I can mention is if p is a prime number, it starts from p^2 with step of size 2*p and eliminates all none-prime numbers to increase performance.

share|improve this answer
    
Could I get an explanation on how isprime(X) ((X)&1?(bank[(X)>>4]&(1<<(((X)&14)>>1))):(X)==2) works? –  GigaWatt Jan 10 '12 at 21:01
add comment

Q (91)

d:{s where 0<>s:{if[2=x;:x];$[0=x mod 2;0;0=min x mod 2+til floor sqrt x;0;x]}each x+til y}

Sample Usage:

q)d[1;100]
1 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
share|improve this answer
add comment
!@:"^&<=upper:than->lower**&%$$%??{}{[]}::1&;
share|improve this answer
3  
I've formatted your code (just put four spaces before each line of code to create a code block), but I couldn't label it with the correct language name as I can't figure out what it is... –  Gareth Jan 5 '13 at 17:33
add comment

C++, 3.3 seconds

Ok, this version can make the 6 second limit by a good margin. By default it computes the sum of the indicated primes, just uncomment the printfs for the actual primes.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <vector>
using namespace std;

#define SIEVEBITS 17
#define SIEVESIZE (1<<SIEVEBITS)

uint8_t sieve[SIEVESIZE];

int main(int argc, char *argv[]) {
  int low = atoi(argv[1]);
  int high = atoi(argv[2]);
  uint64_t sum = 0;

  // handle 2 separately                                                                                           
  if (low <= 2 && 2 <= high) {
    //printf("2\n");                                                                                               
    sum += 2;
  }

  // generate odd primes up to sqrt(1e9) = 31622                                                                   
  vector<int> oddprimes;
  for (int p = 3; p < 31622; p += 2) {
    bool prime = true;
    for (int i = 3; i * i <= p; i += 2) {
      if (p % i == 0) {
        prime = false;
        break;
      }
    }
    if (prime) {
      oddprimes.push_back(p);
      if (low <= p && p <= high) {
        //printf("%d\n", p);                                                                                       
        sum += p;
      }
    }
  }
  if (low < 31622) low = 31622;

  // sieve for remaining primes.  The entry at index i in the sieve                                                
  // represents the odd number 2 * (base + i) + 1.                                                                 
  for (int base = low / 2; base <= high / 2; base += SIEVESIZE) {
    memset(sieve, 0, SIEVESIZE);
    for (vector<int>::const_iterator i = oddprimes.begin(); i != oddprimes.end(); ++i) {
      int p = *i;
      int offset = (2 * base + 1) % p;
      if (offset != 0) {
        if (offset & 1) {
          offset = (p - offset) >> 1;
        } else {
          offset = p - (offset >> 1);
        }
      }
      for (int j = offset; j < SIEVESIZE; j += p) sieve[j] = 1;
    }
    for (int i = 0; i < SIEVESIZE; i++) {
      int p = 2 * (base + i) + 1;
      if (!sieve[i] && p <= high) {
        //printf("%d\n", p);                                                                                       
        sum += p;
      }
    }
  }
  printf("sum %llu\n", sum);
}
share|improve this answer
add comment
#include<stdio.h>
#include<conio.h>


void main()
{

int start,end,i=0;
clrscr();

printf("Enter the range");
scanf("%d%d",&start,&end);

while(start<=end)
{
    i=3;
    if(start==2)
    printf("%d",start);

    while(i<=start)
    {
    if(start%i==0)
    break;
    i++;
    }
    if(i==start)
    printf("%d",start);
    start++;
}
getch();
}
share|improve this answer
1  
Hi and welcome! Could you please add the language and in this case the average time your code needs to solve the problem? –  air_blob Feb 19 '13 at 10:58
add comment

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.