Prime Numbers Between Two Numbers

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

!@:"^&<=upper:than->lower**&%$$%??{}{[]}::1&;

Answer 7

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

Answer 8

#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();
}